Step 3 of 4
Count reads as uses, not just writes
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.
Here is the step that makes it an LRU cache.
Right now a key you read a thousand times is evicted the moment something newer
arrives, because only writes move it. Fix that: a successful get should make
its key the most recently used one.
capacity 2
put(1, 1) put(2, 2)
get(1) -> 1 // 1 is now the newest, 2 is the oldest
put(3, 3) // so 2 is evicted, not 1
get(1) -> 1
get(2) -> -1A get that misses must change nothing — no reordering, no insertion.
keys() reports the order you are maintaining, oldest first. Use it while you
work: if it does not read the way you expect, the order is wrong before the
eviction is.
Your build
Running is free — Submit is what records the step. Or press ⌘↩
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| runOps(2, [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",1],["get",2]]) | a read protects a key from the next eviction | [null,null,1,null,1,-1] | — |
| runOps(3, [["put",1,1],["put",2,2],["put",3,3],["get",1],["keys"]]) | keys report least recently used first | [null,null,null,1,[2,3,1]] | — |
| runOps(2, [["put",1,1],["put",2,2],["get",9],["keys"]]) | a read that misses changes nothing | [null,null,-1,[1,2]] | — |
| withheld | hidden | withheld | — |
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