Step 4 of 4
Count overwrites as uses too
One case is still wrong, and it is the one that bites in production.
Writing to a key that is already in the cache is a use of that key — but a plain assignment updates the value in place and leaves the key exactly where it was in the order. So a key that is written constantly can still be evicted for being old.
capacity 2
put(1, 1) put(2, 2)
put(1, 99) // 1 is used, so 1 should now be the newest
put(3, 3) // 2 is the oldest, so 2 goes
get(1) -> 99
get(2) -> -1Overwriting must also not grow the cache: two keys written three times are still two keys.
With this step done you have a cache whose every operation is O(1), which is the property that makes LRU usable at all — an eviction policy you have to scan for is not a policy, it is a full table scan wearing one.
Your build
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| runOps(2, [["put",1,1],["put",2,2],["put",1,99],["size"],["get",1]]) | overwriting does not grow the cache | [null,null,null,2,99] | — |
| runOps(2, [["put",1,1],["put",2,2],["put",1,99],["put",3,3],["get",1],["get",2],["get",3]]) | an overwrite counts as a use | [null,null,null,null,99,-1,3] | — |
| runOps(3, [["put",1,1],["put",2,2],["put",3,3],["put",1,10],["keys"]]) | keys reflect the overwrite | [null,null,null,null,[2,3,1]] | — |
| 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.
Complexity
- target time
- O(1) per operation
- target space
- O(capacity)
Every operation is a constant number of hash-map lookups, plus one delete-and-reinsert to move a key to the back. Nothing scans the cache — which is the point. A policy that had to search for the least recently used entry would be O(n) per eviction and would cost more than the cache saves.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left