System Design Basics/Practice/LRU Cache
LRU Cache - Design Explained Step by Step
Combine two structures: a hash map from key to node for O(1) lookup, and a doubly linked list ordered by recency. get pulls the node to the front; put updates or inserts at the front and evicts from the tail when capacity is exceeded.
Why it works
Each structure covers the other’s weakness: the map finds nodes instantly but cannot order them; the list reorders in O(1) pointer swaps but would take O(n) to search. Together every operation is O(1) - which is why this pairing is the canonical interview answer.
The problem
Design a data structure that follows the LRU (Least Recently Used) cache constraint. Implement get(key) and put(key, value) both in O(1) time. When capacity is exceeded, evict the least recently used key.
Hints
- Hash map gives O(1) key lookup. Doubly linked list gives O(1) insertions and deletions.
- Combine them: map stores key -> node, linked list maintains usage order.
- On access: remove node from its position, re-insert at the front (most recent).
- On eviction: remove node from the back (least recent), delete from map.
- Python's OrderedDict wraps this pattern cleanly.
Test cases
| Input | Expected |
|---|---|
get(1) after put(1,1),put(2,2) | 1 |
get(2) after put(3,3) evicts 2 | -1 |
get(3) after put(4,4) | 3 |
Reference starter code
class LRUCache:
def __init__(self, capacity):
# Need O(1) get and put with LRU eviction
# Hint: combine a hash map with a doubly linked list
pass
def get(self, key):
pass
def put(self, key, value):
pass
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1)) # 1
cache.put(3, 3) # evicts key 2
print(cache.get(2)) # -1 (not found)
cache.put(4, 4) # evicts key 1
print(cache.get(1)) # -1 (not found)
print(cache.get(3)) # 3
print(cache.get(4)) # 4
Try it yourself
Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.