Design an LRU Cache
You'll learn to
- -Combine a hash map and doubly linked list to get O(1) get/put with correct eviction order
- -Extend the design to thread-safety and a pluggable eviction Strategy (LRU vs. LFU) as realistic follow-ups
An LRU (Least Recently Used) Cache is as much a data-structures problem as an OOP-design problem, which is exactly what makes it a favorite: it tests whether you can combine two data structures to hit a specific complexity target, then wrap that combination in a clean class interface.
The Complexity Requirement That Drives the Design
Both get(key) and put(key, value) need to run in O(1) time. A hash map alone gives O(1) lookup but has no notion of "recency order" for eviction. A linked list alone gives O(1) reordering (move a node to the front) but O(n) lookup by key. Combining them - a hash map from key to a node, plus a doubly linked list maintaining recency order - gives O(1) for both, because the hash map provides instant access to exactly the node the linked list needs to move.
The Combined Structure
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.prev: "Node | None" = None
self.next: "Node | None" = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self._map: dict = {}
self._head = Node(None, None) # dummy head (most recently used side)
self._tail = Node(None, None) # dummy tail (least recently used side)
self._head.next, self._tail.prev = self._tail, self._head
def _remove(self, node: Node) -> None:
node.prev.next, node.next.prev = node.next, node.prev
def _add_to_front(self, node: Node) -> None:
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) # touched - now most recently used
return node.value
def put(self, key, value) -> None:
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 # least recently used - right before dummy tail
self._remove(lru)
del self._map[lru.key]Why Dummy Head/Tail Nodes
The dummy (sentinel) head and tail nodes exist purely to eliminate edge-case branching - without them, adding to an empty list or removing the only remaining node requires special-casing null-checks for head/tail. With permanent sentinels, _remove() and _add_to_front() work identically whether the list has 0, 1, or 1000 real nodes, which is exactly the kind of edge-case elimination interviewers notice as a sign of experience.
Follow-Up: Thread-Safety
Both get() and put() mutate shared state (the map and the linked list pointers), so under concurrent access this needs the same coarse-grained lock treatment from the Concurrency module - a single lock around both methods is the simple, correct starting point, since get() being "just a read" is deceptive here: it still mutates recency order.
Follow-Up: Pluggable Eviction Policy (LRU vs. LFU)
If asked to also support LFU (Least Frequently Used) eviction, the strong move is recognizing this as a Strategy opportunity: extract an EvictionPolicy interface with an on_access() and evict() contract, and let LRUPolicy and LFUPolicy each maintain whatever internal bookkeeping they need (the linked list for LRU; a frequency count plus tie-breaking structure for LFU), with Cache depending only on the interface.
Say explicitly that get() is not a pure read, since it mutates recency order - flagging that nuance unprompted is a strong signal you understand why coarse-grained locking is required on both methods, not just put().
Interview Signal is part of Pro
See a real weak answer next to a real strong one for this exact topic.
Quiz is part of Pro
Test what you just read with a short quiz, and bank the XP.