LRU Cache
Doubly linked list plus hashmap. One gives you O(1) lookups, the other gives you O(1) eviction ordering. Together they solve the cache problem.
Key Abstractions
Public API for get and put, enforces capacity limits
Strategy interface so you can swap LRU for LFU or FIFO
Maintains access ordering with O(1) move-to-front
Wraps key-value pairs with prev/next pointers
Class Diagram
The Key Insight
A cache has two jobs: find things fast and decide what to throw away when it's full. HashMap handles the first part with O(1) lookups. A doubly linked list handles the second by letting you reorder nodes and pop the tail in O(1). Point the hashmap directly at list nodes and both problems solve each other.
Where most people stop is hardcoding LRU logic right inside the cache class. Works fine until someone asks "now make it LFU" and you're rewriting half the code. Pull the eviction logic behind a Strategy interface and swapping algorithms becomes a one-line change. The cache itself never knows the difference.
Requirements
Functional
put(key, value)stores or updates a key-value pairget(key)returns the value or null/None if missing- When capacity is exceeded, evict the least recently used entry
- Both
getandputcount as "usage" and refresh the entry's recency
Non-Functional
- O(1) time for both
getandput - Thread-safe for concurrent access
- Eviction policy should be swappable without modifying cache internals
Design Decisions
Why sentinel nodes in the DLL?
Without sentinels you need null-checks on every insert and remove because head and tail are special cases. Sentinel (dummy) nodes at both ends mean every real node always has valid prev and next pointers. Half the branching logic disappears and those tricky edge-case bugs go away.
Why Strategy pattern and not just a switch statement?
A switch on policyType couples the cache to every eviction algorithm you'll ever write. When the team adds LFU next quarter, they're modifying cache internals. With Strategy, you hand the cache any EvictionPolicy implementer. LRU today, LFU tomorrow, FIFO for testing. The cache class stays untouched.
Why ReentrantLock over synchronized?
synchronized works fine for simple cases. ReentrantLock gives you tryLock() for non-blocking attempts, lockInterruptibly() for cancellation, and fair ordering if you need it. In a high-throughput cache, those options matter.
Interview Follow-ups
- "How would you add TTL-based expiry?" Wrap values with a timestamp, add a lazy-eviction check on
get(), and optionally run a background reaper thread. - "What changes for LFU instead of LRU?" New policy implementation with a frequency map and min-frequency tracking. Cache code stays exactly the same.
- "How would you make this distributed?" Consistent hashing to shard keys across nodes, with local LRU per shard. Or use a write-through/write-behind strategy with a shared backing store.
- "What about cache stampede?" Lock-per-key pattern or probabilistic early refresh to prevent thundering herd on popular keys.
Code Implementation
1 from __future__ import annotations
2 from abc import ABC, abstractmethod
3 from threading import Lock
4
5
6 class DLLNode:
7 """Doubly-linked list node wrapping a cache key-value pair."""
8
9 __slots__ = ("key", "value", "prev", "next")
10
11 def __init__(self, key: str = "", value: object = None):
12 self.key = key
13 self.value = value
14 self.prev: "DLLNode | None" = None
15 self.next: "DLLNode | None" = None
16
17
18 class DoublyLinkedList:
19 """Sentinel-based DLL. Eliminates null checks at head/tail."""
20
21 def __init__(self):
22 self._head = DLLNode() # dummy head
23 self._tail = DLLNode() # dummy tail
24 self._head.next = self._tail
25 self._tail.prev = self._head
26
27 def add_first(self, node: DLLNode) -> None:
28 node.next = self._head.next
29 node.prev = self._head
30 self._head.next.prev = node
31 self._head.next = node
32
33 def remove(self, node: DLLNode) -> None:
34 node.prev.next = node.next
35 node.next.prev = node.prev
36
37 def remove_last(self) -> DLLNode:
38 if self._tail.prev == self._head:
39 raise IndexError("remove from empty list")
40 node = self._tail.prev
41 self.remove(node)
42 return node
43
44 def move_to_front(self, node: DLLNode) -> None:
45 self.remove(node)
46 self.add_first(node)
47
48
49 class EvictionPolicy(ABC):
50 """Strategy interface. Swap LRU for LFU/FIFO without touching Cache."""
51
52 @abstractmethod
53 def on_access(self, key: str, node: DLLNode) -> None: ...
54
55 @abstractmethod
56 def evict(self) -> str: ...
57
58 @abstractmethod
59 def remove(self, key: str) -> None: ...
60
61
62 class LRUPolicy(EvictionPolicy):
63 def __init__(self):
64 self._dll = DoublyLinkedList()
65 self._nodes: dict[str, DLLNode] = {}
66
67 def on_access(self, key: str, node: DLLNode) -> None:
68 if key in self._nodes:
69 self._dll.move_to_front(self._nodes[key])
70 else:
71 self._dll.add_first(node)
72 self._nodes[key] = node
73
74 def evict(self) -> str:
75 victim = self._dll.remove_last()
76 del self._nodes[victim.key]
77 return victim.key
78
79 def remove(self, key: str) -> None:
80 if key in self._nodes:
81 self._dll.remove(self._nodes.pop(key))
82
83
84 class Cache:
85 """Thread-safe cache with pluggable eviction strategy."""
86
87 def __init__(self, capacity: int, policy: EvictionPolicy | None = None):
88 if capacity <= 0:
89 raise ValueError("capacity must be positive")
90 self._capacity = capacity
91 self._store: dict[str, DLLNode] = {}
92 self._policy = policy or LRUPolicy()
93 self._lock = Lock()
94
95 def get(self, key: str) -> object | None:
96 with self._lock:
97 node = self._store.get(key)
98 if node is None:
99 return None
100 self._policy.on_access(key, node)
101 return node.value
102
103 def put(self, key: str, value: object) -> None:
104 with self._lock:
105 if key in self._store:
106 node = self._store[key]
107 node.value = value
108 self._policy.on_access(key, node)
109 return
110
111 if len(self._store) >= self._capacity:
112 evicted_key = self._policy.evict()
113 del self._store[evicted_key]
114
115 node = DLLNode(key, value)
116 self._store[key] = node
117 self._policy.on_access(key, node)
118
119
120 if __name__ == "__main__":
121 cache = Cache(capacity=3)
122 cache.put("a", 1)
123 cache.put("b", 2)
124 cache.put("c", 3)
125 print(f"get('a') = {cache.get('a')}") # 1, touches "a" so it's now most recent
126 cache.put("d", 4) # evicts "b" (least recently used)
127 print(f"get('b') = {cache.get('b')}") # None, was evicted
128 print(f"get('d') = {cache.get('d')}") # 4
129 assert cache.get("b") is None
130 assert cache.get("a") == 1
131 print("All assertions passed.")Common Mistakes
- ✗Forgetting to update node position on get(), not just put(). Stale ordering breaks LRU correctness.
- ✗Not removing the evicted key from the hashmap after DLL removal. That's a silent memory leak.
- ✗Skipping thread safety. Production caches need locks or concurrent structures around both the map and list.
- ✗Ignoring capacity=0 edge case. Should reject all puts gracefully.
Key Points
- ✓HashMap for O(1) lookup, DLL for O(1) eviction ordering. Together they cover both needs.
- ✓Strategy pattern makes the eviction policy swappable without touching cache internals
- ✓The DLL tail is always the eviction candidate. No scanning required.
- ✓Move-to-front on both get() and put() keeps the ordering correct