Step 2 of 4

Throw out the oldest when you run out of room

You start from the build so far — your own work where you have written it, the reference build where you have not. Either way this step stands on its own.

Now honour capacity. When a put would take the cache past it, remove one entry first — for this step, whichever key was inserted longest ago.

capacity 2
put(1, 1)   put(2, 2)   put(3, 3)
get(1)  ->  -1          // 1 was inserted first, so 1 went
get(2)  ->  2

size() must never exceed capacity, including when capacity is 1.

This is not yet a least recently used cache — it is a least recently written one. Reads still count for nothing. That is the next step; get the eviction machinery right first.

Your build

Running is free — Submit is what records the step. Or press ⌘↩

Tests

4 cases, 1 hidden
calltypeexpectedresult
runOps(2, [["put",1,1],["put",2,2],["put",3,3],["get",1],["get",2],["get",3]])the oldest key is the one evicted[null,null,null,-1,2,3]—
runOps(2, [["put",1,1],["put",2,2],["put",3,3],["size"]])size never exceeds capacity[null,null,null,2]—
runOps(1, [["put",1,1],["put",2,2],["get",1],["get",2]])a cache of capacity 1 holds only the newest[null,null,-1,2]—
withheldhiddenwithheld—

Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.

Hints

Stuck? Hints open one at a time, each giving a little more away.

3 hints left