LRU Cache
Implement LRUCache(capacity) with get(key) and put(key,value). get returns -1 when absent. Successful get and every put make that key most recently used; exceeding capacity evicts the least recently used key. Use expected constant time per operation.
Example 1
arg 1 = ["LRUCache","put","put","get","put","get","get"]
arg 2 = [[2],[1,10],[2,20],[1],[3,30],[2],[3]][null,null,null,10,null,-1,30]Explanation
Reading key 1 refreshes recency; putting key 3 evicts key 2 and leaves key 3 available.
Example 2
arg 1 = ["LRUCache","put","put","put","get","get"]
arg 2 = [[1],[5,1],[5,2],[6,3],[5],[6]][null,null,null,null,-1,3]Explanation
Updating key 5 uses no extra slot; inserting key 6 then evicts 5.
Example 3
arg 1 = ["LRUCache","put","put","put","put","get","get"]
arg 2 = [[2],[1,10],[2,20],[1,11],[3,30],[2],[1]][null,null,null,null,null,-1,11]Explanation
Updating key 1 makes it most recent, so putting key 3 evicts key 2 and preserves value 11 for key 1.
Constraints
- 1 <= capacity <= 3000
- At most 200000 operations
- Keys and values are nonnegative integers
Class contract
LRUCacheArguments: json, jsonSolutionRuns on your device
Loading draft…
Run: 3 examples; Submit: 35 cases, on your device.
["LRUCache","put","put","get","put","get","get"][[2],[1,10],[2,20],[1],[3,30],[2],[3]]