LRU Cache

Design LRUCache(capacity), a cache with a fixed positive capacity. get(key) returns the cached value, or -1 if the key is absent. put(key, value) inserts or…

Design LRUCache(capacity), a cache with a fixed positive capacity. get(key) returns the cached value, or -1 if the key is absent. put(key, value) inserts or updates the key. A successful get or any put makes that key most recently used. When inserting a new key into a full cache, evict the least recently used key. A missing get does not change recency. Implement get and put in O(1) average time. The driver supplies aligned operations and arguments arrays with the constructor first. It records null for construction and every put, and the integer return value for every get. Implement the class methods; do not print or return the whole transcript.

Positive capacity: 1..1000. Keys: strict integers 0..10000. Values: strict integers 0..100000. At most 100000 get/put calls after construction (1..100001 records total). Arrays must align; exactly one constructor appears first. get takes one key; put takes key and value. No separate target. Teaching playback accepts at most 12 records and capacity at most 4; coding retains all bounds above.

Example 1: input operations = ["LRUCache","put","put","get","put","get","put","get","get","get"], arguments = [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]; output [null,null,null,1,null,-1,null,-1,3,4]. After get(1), key 2 is least recent, so put(3,3) evicts key 2. Inserting key 4 later evicts key 1; the final reads of keys 3 and 4 return 3 and 4.

Example 2: input operations = ["LRUCache","put","put","get","put","get","put","get"], arguments = [[1],[1,1],[2,2],[1],[3,3],[2],[4,4],[3]]; output [null,null,null,-1,null,-1,null,-1]. Capacity 1 retains only one key. Each new put evicts the previous key. The reads of keys 1, 2 and 3 occur after their eviction, so all three return -1.

Category: Arrays & Hashing. Topic: arrays. Difficulty: Medium. Patterns: hashing, linked-list-traversal.