LRU Cache

Hash Mapsmedium

Design an `LRUCache` class with a fixed `capacity`. `get(key)` returns the value or `-1` if absent; `put(key, value)` inserts or updates. Both count as a use, marking the key most-recently-used. When `put` would exceed capacity, evict the least-recently-used key first. Aim for O(1) per operation. (Asked at Amazon, Microsoft, and Google.)

Examples

Input: new LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4)

Output: [1, -1, -1, 3, 4]

put(3) evicts key 2 (LRU). put(4) evicts key 1. So get(2) and get(1) return -1.

Sample tests

Input: evicts least-recently-used

Output: [1,-1,-1,3,4]

Input: capacity 1

Output: [10,-1,20]

+ 2 hidden tests run on Submit.

Hints

Common pitfalls

Updating an existing key without re-inserting it leaves its recency stale.
Evicting before inserting, or evicting by the wrong end, removes the wrong key.

Learning resources

Wikipedia: Cache replacement policies (LRU)

Approach & explanation (try first)

Backing the cache with a Map gives O(1) lookup plus insertion-order iteration. Re-inserting a touched key moves it to the most-recent position; when size exceeds capacity, the first key from `map.keys()` is the least-recently-used and gets evicted. Production implementations use a hash map plus a doubly linked list for the same O(1) guarantees.

⌘/Ctrl + Enter

Run your code to see results.

← Back to problems