LRU Cache
Part of Practice: Design & Hard Surgery
Design a Least Recently Used (LRU) cache — a fixed-capacity key-value store that, when full, evicts the entry that has gone unused the longest. Implement:
get(key)— return the key's value (and count this as a use), or -1 if absent.put(key, value)— insert or update the key (also a use); if inserting pushes the cache past capacity, evict the least recently used entry first.
Both operations must run in O(1) average time. Capacity is at least 1, and up to 2 * 10^5 operations may be issued.
Examples
- Input:
- 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:
- get(1)=1, get(2)=-1, get(1)=-1, get(3)=3, get(4)=4
get(1) makes key 1 recently used, so put(3,3) evicts key 2 instead. Later, put(4,4) evicts key 1, which had become the least recently used.
- Input:
- LRUCache(1); put(5, 5); put(6, 6); get(5)
- Output:
- get(5)=-1
With capacity 1, inserting 6 evicts 5 immediately.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.