LRU Cache
Problem Statement
Design an LRUCache with positive capacity. get(key) returns the value for key if it exists, otherwise -1. put(key, value) inserts or updates the key. Whenever the cache exceeds capacity, it must evict the least recently used key. Both operations must run in O(1) average time.
Input
A constructor call LRUCache(capacity) followed by a sequence of get(key) and put(key, value) calls.
Output
For the constructor and put, output null. For get, output the stored value or -1 if the key is missing.
Constraints
- •
1 <= capacity <= 3000 - •
0 <= key <= 10^4 - •
0 <= value <= 10^5 - •
At most 2 * 10^5 calls will be made to get and put
Examples
Example 1
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]]
[null, null, null, 1, null, -1, null, -1, 3, 4]Example 2
operations = [LRUCache, put, put, get, put, put, get], arguments = [[2], [2,1], [2,2], [2], [1,1], [4,1], [2]]
[null, null, null, 2, null, null, -1]Learning Objectives
- Combine a hash map with a doubly linked list to satisfy lookup and recency requirements.
- Maintain most-recent and least-recent positions after every get and put.
- Implement O(1) node removal when given a direct node reference.
- Explain why a singly linked list or queue alone cannot support all operations efficiently.
Intuition
Pattern Recognition
This design has two independent requirements. Finding a key needs a hash map. Evicting the least recently used item and moving an accessed item to most recent need an ordered structure with O(1) removal from the middle. A doubly linked list supplies that second guarantee when the map points directly to list nodes.
The tempting approach is a hash map plus timestamps or a queue. Timestamps make eviction require a scan or heap cleanup, and a queue cannot remove an updated key from the middle in O(1). The pattern is hash map to node plus a recency list: head means most recent, tail means least recent.
Common mistakes
- ×Refreshing recency on put but forgetting to refresh it on get.
- ×Using a singly linked list, then needing O(n) time to remove a middle node.
- ×Evicting after adding without removing the evicted key from the map.
- ×Not handling updates separately, causing duplicate nodes for the same key.
Algorithm Explanation
Key idea
Store each key in a hash map that points to a node in a doubly linked list. Keep dummy head and tail sentinels so insertion and removal do not need edge-case branches. The node after head is most recently used, and the node before tail is least recently used.
Walkthrough
With capacity 2, put(1,1) creates list 1. put(2,2) moves 2 to the front, so recency is 2, 1. get(1) returns 1 and moves key 1 to the front, making 1, 2. put(3,3) adds 3 at the front, temporarily 3, 1, 2, then evicts the tail-side key 2. The map and list now contain keys 3 and 1.
Algorithm
- The constructor creates the map and connects dummy head directly to dummy tail.
- For get(key), look up the node. If absent, return -1.
- If present, detach the node from its current position, insert it after head, and return its value.
- For put(key, value), if the key exists, update the node's value and move it after head.
- If the key is new, create a node, add it to the map, and insert it after head.
- If the map size is now above capacity, remove the node before tail and delete its key from the map.
Solutions
Solution: Hash map plus custom doubly linked list
The map gives direct access to the node for a key. The doubly linked list gives O(1) detach and O(1) insertion at the most-recent end. Dummy sentinels make the list operations uniform.
Step-by-step
- On every successful get, move the accessed node to the front because it is now most recent.
- On put for an existing key, update the value and move that node to the front.
- On put for a new key, insert a new node at the front and store it in the map.
- If capacity is exceeded, remove the node immediately before the tail sentinel.
- Delete the evicted node's key from the map so future lookups correctly miss.
Average O(1) per get and put
O(capacity)
The map and linked list store at most capacity live nodes.
Java implementation
Dry Run
Sample input
Capacity is 2. Operations: put(1,1), put(2,2), get(1), put(3,3), get(2).
| operation | argument | structure state | result |
|---|---|---|---|
| put | 1,1 | recency = [1], map keys = {1} | null |
| put | 2,2 | recency = [2, 1], map keys = {1, 2} | null |
| get | 1 | move 1 to front, recency = [1, 2] | 1 |
| put | 3,3 | insert 3 then evict tail 2, recency = [3, 1] | null |
| get | 2 | 2 is absent from the map | -1 |
The list order changes on reads as well as writes. That is what makes key 2 the least recently used item when key 3 is inserted.
Interview Tips
Name the two invariants before coding: the map points to every live node, and the list is ordered from most recent near head to least recent near tail. Use helper methods for add, remove, and move so the main get and put logic stays small. Interviewers often probe whether get refreshes recency; say yes immediately.
Likely follow-ups
- How would the implementation change with Java **LinkedHashMap** and access order?
- How would you implement LFU eviction instead of LRU eviction?
- How would you make the cache safe for concurrent readers and writers?
- How would you add a time-to-live expiration policy?
Similar Problems
Key Takeaways
- A hash map gives key lookup but not recency order.
- A doubly linked list gives O(1) movement and tail eviction when nodes are known.
- Successful get and put both make a key most recent.
- Capacity overflow evicts the node next to the tail sentinel and removes it from the map.