How Would You Design an LRU Cache?
Learn to design an O(1) LRU cache using a hash map and doubly linked list for this common coding interview question.
Expected Interview Answer
An LRU (Least Recently Used) cache is designed by combining a hash map for O(1) key lookup with a doubly linked list that keeps items ordered by recency, so that both get and put operations run in O(1) time while the list's tail always identifies the item to evict when the cache is full.
The hash map stores each key mapped directly to its node in the doubly linked list, giving instant access to any entry without scanning. The doubly linked list keeps the most recently used item at the head and the least recently used item at the tail; on every get or put, the accessed node is unlinked from its current position and moved to the head in O(1) using the node's prev/next pointers, no traversal required. When put would exceed capacity, the tail node is removed in O(1) and its key is deleted from the hash map as well, keeping both structures in sync. Using a plain array or singly linked list instead would force an O(n) scan to find or reorder the least-recently-used item, which is why the combination of hash map plus doubly linked list is the standard answer — the doubly linked list specifically (not singly linked) is required because removing a node needs O(1) access to its predecessor to patch the surrounding links. Some languages provide this pattern built in, like Python's OrderedDict with move_to_end, but understanding the underlying hash-map-plus-linked-list mechanics is what interviewers are testing.
- O(1) get and O(1) put, both amortized
- Hash map gives instant key-to-node lookup
- Doubly linked list gives O(1) reordering and eviction
- Widely used pattern in real caching systems (databases, CDNs, OS page tables)
AI Mentor Explanation
A franchise's playing squad has a fixed number of slots, and coaches want to instantly find any player's current form record while also knowing exactly who to drop first if a new signing is needed. They keep a lookup card per player name pointing directly to that player's spot in a line-up ranked by recent selection, and a physical line-up where the most recently selected player sits at the front and the least recently selected sits at the back. Selecting a player for a match pulls their card, jumps straight to their spot in the line-up, and moves them to the front instantly using the neighbors on either side, no scanning required. When a new signing forces a slot cut, the player at the very back of the line-up is dropped and their lookup card is removed at the same time, keeping both records in sync.
Step-by-Step Explanation
Step 1
Combine a hash map with a doubly linked list
Hash map: key to node reference. Doubly linked list: nodes ordered by recency, head = most recent, tail = least recent.
Step 2
On get(key)
Look up the node in O(1) via the hash map, unlink it, and move it to the head to mark it as most recently used.
Step 3
On put(key, value)
If the key exists, update its value and move its node to the head; otherwise create a new node at the head and add it to the map.
Step 4
Evict on overflow
If capacity is exceeded, remove the tail node in O(1) and delete its key from the hash map.
What Interviewer Expects
- Correctly identify hash map + doubly linked list as the combination needed
- Explain why O(1) get AND O(1) put both require this combination, not just one structure
- Explain why the linked list must be doubly (not singly) linked for O(1) removal
- Walk through get/put/evict operations concretely, including keeping both structures in sync
Common Mistakes
- Proposing only an array or only a hash map, which forces O(n) reordering or eviction
- Using a singly linked list, which cannot delete a node in O(1) without a predecessor pointer
- Forgetting to update the hash map when evicting the tail node, leaving stale entries
- Not moving a node to the head on a get() call, only on put(), breaking the recency invariant
Best Answer (HR Friendly)
“An LRU cache needs to answer 'do I have this?' instantly and also know exactly which item to remove when it is full. I solve that by pairing a hash map, which gives instant lookup by key, with a doubly linked list that keeps items ordered by how recently they were used, so the newest item is always at the front and the item to evict is always sitting right at the back, both in constant time.”
Code Example
class Node:
def __init__(self, key, value):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.map = {}
self.head = Node(0, 0) # dummy head (most recent side)
self.tail = Node(0, 0) # dummy tail (least recent side)
self.head.next, self.tail.prev = self.tail, self.head
def _remove(self, node):
node.prev.next, node.next.prev = node.next, node.prev
def _add_to_front(self, node):
node.next, node.prev = self.head.next, self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key not in self.map:
return -1
node = self.map[key]
self._remove(node)
self._add_to_front(node)
return node.value
def put(self, key, value):
if key in self.map:
self._remove(self.map[key])
node = Node(key, value)
self.map[key] = node
self._add_to_front(node)
if len(self.map) > self.capacity:
lru = self.tail.prev
self._remove(lru)
del self.map[lru.key]Follow-up Questions
- How would you make this LRU cache thread-safe under concurrent access?
- How would you implement an LFU (Least Frequently Used) cache instead?
- Why does Python's OrderedDict make this easier to implement, and how does move_to_end work?
- How would you add TTL-based expiration on top of this LRU design?
MCQ Practice
1. What two data structures does a standard O(1) LRU cache combine?
The hash map gives O(1) key lookup, and the doubly linked list gives O(1) reordering and eviction.
2. Why must the linked list in an LRU cache be doubly, not singly, linked?
Deleting a node requires patching its predecessor and successor pointers; a singly linked list has no O(1) way to reach the predecessor.
3. When an LRU cache exceeds capacity on put(), which item is evicted?
The tail of the doubly linked list always holds the least recently used item, which is evicted in O(1).
Flash Cards
What two structures make up a standard LRU cache? — A hash map (key to node) and a doubly linked list (ordered by recency).
What is the time complexity of get() and put() in an LRU cache? — Both O(1).
Where does the least recently used item live in the linked list? — At the tail of the list.
Why not use a singly linked list for an LRU cache? — Because O(1) node removal needs a predecessor pointer, which only a doubly linked list provides.