146. LRU Cache

Practice LRU Cache for free on NudgeCode: Medium, Linked List pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Design a cache with a fixed capacity that evicts the least recently used key when it is full.

• get(key) returns the value for key, or -1 if it is not cached. A successful get counts as a use.
• put(key, value) inserts or updates key (also a use). If this pushes the size over capacity, remove the key that was used longest ago.

Both operations should run in O(1) average time.

Each test is a list of operations and their arguments; the expected output lists what each call returns (null for the constructor and for calls that return nothing).

Example

["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
->  [null,null,null,1,null,-1,null,-1,3,4]

Constraints

• 1 <= capacity <= 3000
• 0 <= key <= 10^4
• 0 <= value <= 10^5
• Up to 2 * 10^5 calls in total