Design an LRU cache

1 · Clarifying questions

2 · Why hash map + doubly-linked list

A hash map alone gives O(1) lookup but can't tell you the recency order. A linked list gives recency order but has O(n) lookup. Combine them: the map stores key → node, the list stores node ↔ node. To move a node to the front, unlink it and re-insert at the head — both O(1) given direct pointers.

A singly-linked list would force O(n) unlink (you'd have to find the predecessor). Doubly-linked is what makes the move O(1).

3 · Class diagram

4 · Interface

class LRUCache<K, V>:
  def __init__(capacity: int)
  def get(key: K) -> V | None     # also moves to MRU
  def put(key: K, value: V)       # also moves/inserts at MRU; evicts LRU if full

class Node<K, V>:
  key: K
  value: V
  prev: Node | None
  next: Node | None

The list keeps two sentinel nodes (head and tail) so insertion at the front and deletion at the back never require null-checks. Sentinels are the under-rated trick of linked-list code.

Operations

get(k):
  if k not in map: return None
  node = map[k]
  remove(node)            # unlink from current position
  add_front(node)         # re-insert as MRU
  return node.value

put(k, v):
  if k in map:
    node = map[k]
    node.value = v
    remove(node)
    add_front(node)
    return
  if len(map) == capacity:
    lru = tail.prev
    remove(lru)
    del map[lru.key]
  node = Node(k, v)
  add_front(node)
  map[k] = node

remove(node):
  node.prev.next = node.next
  node.next.prev = node.prev

add_front(node):
  node.next = head.next
  node.prev = head
  head.next.prev = node
  head.next = node

5 · Edge cases

• Capacity 0 or 1. Capacity 0 is degenerate — every put evicts what it just inserted; reasonable to reject in the constructor. Capacity 1 works fine but exercises every remove/insert path.
• Updating an existing key. Must update the value and move to MRU. A common bug is to update the value but forget the move.
• Get on a missing key. Return None (or sentinel, or throw). Don't accidentally insert.
• Eviction during put. Evict first, then insert — otherwise you over-allocate transiently.

6 · Thread-safety

The naive answer: wrap every method in one mutex. Correct, simple, scales poorly.

Better answers, in increasing complexity:

• Shard the cache. N independent LRUCaches, key hashed to a shard. Each shard has its own lock. Locks contend N× less.
• Read-write lock. Doesn't help here — every get mutates the list. RWLock works only for the rare read-only workload.
• Lock-free. Specialised structures (Caffeine in Java) use compare-and-swap on the linked list. Real, but past the bar for an OOD round; mention it as a stretch.

7 · Extensions

• TTL eviction. Each node carries an expiry; eviction checks expiry first, falls back to LRU. A min-heap of expiries gives O(log n) periodic cleanup.
• LFU (least-frequently-used). Each node tracks a counter; eviction picks the lowest. The clean implementation uses a list of frequency buckets, each holding an LRU list.
• Distributed. Hash partition across nodes. Each node runs an LRUCache for its slice. Consistent hashing if you want to add/remove nodes without remapping most keys.
• Persistence. Write-through to disk for survivable cache. put waits on the disk write; trades latency for durability.

8 · What gets graded

• Did you recognise the hash-map-plus-doubly-linked-list pattern fast?
• Did you handle the "update existing key" case correctly?
• Did you use sentinel nodes (or notice why you should)?
• Did you separate remove and add_front as helper methods, or smear the pointer plumbing across get and put?
• Did you talk about thread-safety unprompted?