0) Problem Restatement
Build a cache that holds at most N items. It supports get(key) and put(key, value), both in O(1) time. When the cache is full and a new item comes in, it removes the Least Recently Used (LRU) item, meaning the one that has not been read or written for the longest time.
Interviewers then add follow-ups:
- Make it safe when many threads use it at the same time.
- Make it survive a crash, so the cache is not empty after a restart.
1) Requirements
1.1 Functional
get(key): return the value, ornullif missing. Mark the key as "just used".put(key, value): insert or update. Mark it as "just used". If the cache is over capacity, remove the least recently used key.- Fixed capacity
N, set when the cache is created.
1.2 Constraints
getandputmust be O(1).- Must be correct when called from many threads.
- (Follow-up) After a restart, the cache should come back with (most of) its data.
2) Core Idea
We need two things at once:
- Find any key fast → a hash map from key to node.
- Know the usage order and move items quickly → a doubly linked list. The most recently used item sits at the head, the least recently used at the tail.
Why a doubly linked list? To remove a node from the middle in O(1), we need its previous node too. A singly linked list would need an O(N) walk to find it.
We also use two dummy nodes, head and tail, so we never have to check for empty lists or null neighbors.
2.1 Class Diagram
Architecture Diagram
classDiagram
class LRUCache {
-int capacity
-HashMap map
-Node head
-Node tail
+get(key) V
+put(key, value) void
-moveToFront(node) void
-removeNode(node) void
-evictLRU() void
}
class Node {
+K key
+V value
+Node prev
+Node next
}
LRUCache "1" --> "*" Node3) Code (Python)
class Node:
def __init__(self, key=None, value=None):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.map = {}
self.head, self.tail = Node(), Node() # dummy nodes
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_front(self, node):
node.prev, node.next = self.head, self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key):
node = self.map.get(key)
if node is None:
return None
self._remove(node)
self._add_front(node) # mark as most recently used
return node.value
def put(self, key, value):
if key in self.map:
node = self.map[key]
node.value = value
self._remove(node)
self._add_front(node)
return
if len(self.map) == self.capacity:
lru = self.tail.prev # least recently used
self._remove(lru)
del self.map[lru.key] # this is why the node stores its key
node = Node(key, value)
self.map[key] = node
self._add_front(node)A small detail interviewers like: each node stores its key. When we evict the tail node, we need the key to delete it from the map.
4) Follow-up 1 — Thread Safety
The problem: evenget changes the list (it moves the node to the front). If two threads move nodes at the same time, the pointers can end up broken, and the list may lose nodes or loop forever.
Option A — one lock around every operation. Simple and correct. The downside is that only one thread can use the cache at a time, which becomes a bottleneck with many threads.
Option B — sharded cache. Split the cache into, say, 16 smaller LRU caches. Pick a shard by hash(key) % 16, and give each shard its own lock and capacity N/16. Threads working on different shards do not block each other. The trade-off is that eviction is LRU per shard, not across the whole cache. That is usually fine.
Option C — relax exact LRU. Libraries such as Caffeine record reads in a buffer and apply them to the list in batches. This removes most lock contention but makes the order approximate.
For an interview, write Option A in code and explain Option B as the way to scale.
import threading
class ThreadSafeLRU(LRUCache):
def __init__(self, capacity):
super().__init__(capacity)
self.lock = threading.Lock()
def get(self, key):
with self.lock:
return super().get(key)
def put(self, key, value):
with self.lock:
super().put(key, value)5) Follow-up 2 — Surviving a Crash
Memory is lost when the process crashes. Two common ways to save the cache:
- Periodic snapshot: every few minutes, write all key/value pairs (in LRU order) to a file. Write to a temp file, then rename it, so a crash in the middle never leaves a half-written snapshot. On restart, load the file. Downside: changes made since the last snapshot are lost.
- Append-only log (write-ahead log): append every
putand eviction to a log file before changing memory. On restart, replay the log. Downside: the log keeps growing, so we compact it from time to time by writing a fresh snapshot and truncating the log.
The best mix is snapshot + log (like Redis's RDB + AOF): restarts are fast because we load the snapshot and replay only the short log written after it.
We usually do not log every get. That would make reads slow. Instead, we accept that the LRU order after a restart is approximate.
6) Extensions & Follow-ups
- TTL (expiry): store an expiry time on each node. Check it in
get, and run a background sweep to remove expired items. - Size-based capacity: evict until the total bytes are under the limit, not the item count.
- LFU instead of LRU: evict the least frequently used item. This needs frequency buckets (a map from count to a list of nodes) to stay O(1).
- Distributed cache: once one machine is not enough, shard keys across nodes with consistent hashing (see a Redis or Memcached cluster design).
7) Wrap-Up
The core answer is a hash map plus a doubly linked list with dummy head and tail nodes, which gives O(1) get and put. For concurrency, start with one lock, then shard the cache to reduce waiting. For crash safety, combine snapshots with an append-only log and accept an approximate order after a restart.