Machine coding · HashMap + DLL · O(1)

LRU cache

You have forty-five minutes to build a cache that can hold only N entries. A get or put must finish without scanning the store. The interviewer will ask you to evict the key that has sat unused the longest. A finds a key instantly but cannot tell you which one is oldest.

That is the whole problem this page solves. An cache is a fixed-capacity key-value store. The usual structure is a HashMap for lookup plus a for recency, so both operations stay . Callers must never see or mutate list nodes: keep private. This is one in-process object, not shards, invalidation, or replication (those live on the Distributed cache System Design note).

Safe O(1) path

Map each key to its list node so lookup never walks the store.

Move a used node to the front; the tail side stays least recently used.

Evict the tail

When size exceeds capacity, unlink and drop the node before the tail.

Return Optional from get. Callers must never see or relink list nodes.

What actually happens on get and put

The forty-five-minute story above is the default machine-coding prompt. means you can find a key instantly and also know which key is least recently used without scanning. The finds the node. The stores recency: on every successful get and put you move that node to the front (most recently used), and when capacity is exceeded you remove from the tail (least recently used).

Both structures stay private inside one object. Capacity is a constructor argument. get returns Optional (empty when the key is missing). put may evict. Do not return or expose the list. Keep the public API tiny; see API design and collections ownership. Encapsulation is part of the design goal, not only big-O runtime.

Simple rule of thumb

Before you draw classes, you need a fast way to reject the design that looks like a cache but is not .

A plus "sort by timestamp" is not O(1) eviction, because finding the oldest entry requires a scan or a heap. The list exists so the least-recent node is always at the tail. A swappable is useful later if they ask for , but start with a correct list. An empty policy interface with no working list does not prove the design.

How to explain this in an interview

Say: two private structures, move to front on use, evict the tail side, never leak Node. One lock first when two threads can get-and-move and put-and-evict at once.

Two structures, one object

The rule of thumb names the pair; this is how they sit in one LruCache. The finds the node by key. The stores recency. Dummy at head and tail simplify link updates: head is most recently used, tail.prev is least recently used.

Diagram text: the exact Mermaid definition below preserves the nodes, labels, and connections. Enable JavaScript to view the rendered diagram.

Read the diagram definition

flowchart LR
    subgraph list [Recency list]
      H[head MRU] --- N1[A] --- N2[B] --- N3[C] --- T[tail LRU]
    end
    subgraph map [HashMap]
      KA[A] --> N1
      KB[B] --> N2
      KC[C] --> N3
    end

Who owns what

01
Cache<K,V>
The port: get and put (maybe delete). Callers never iterate nodes.
02
LruCache
Owns the map and sentinel nodes. moveToHead and evictTail stay private.
03
Package-private or inner class, never part of the public API.
04
Lock (first answer)
One cache lock first, because get-move and put-evict are compound.

Java API sketch

The diagram above is the same object the sketch implements: a private index, sentinels, one lock, and a tiny port.

java

interface Cache<K, V> {
  Optional<V> get(K key);
  void put(K key, V value);
}

class Node<K, V> {
  K key;
  V value;
  Node<K, V> prev;
  Node<K, V> next;
  static <K, V> Node<K, V> sentinel() { return new Node<>(); }
}

class LruCache<K, V> implements Cache<K, V> {
  private final int capacity;
  private final Map<K, Node<K, V>> index = new HashMap<>();
  private final Node<K, V> head = Node.sentinel();
  private final Node<K, V> tail = Node.sentinel();
  private final Object lock = new Object();

  LruCache(int capacity) {
    this.capacity = capacity;
    head.next = tail;
    tail.prev = head;
  }

  public Optional<V> get(K key) {
    synchronized (lock) {
      Node<K, V> n = index.get(key);
      if (n == null) return Optional.empty();
      moveToHead(n);
      return Optional.of(n.value);
    }
  }

  public void put(K key, V value) {
    synchronized (lock) {
      Node<K, V> n = index.get(key);
      if (n != null) {
        n.value = value;
        moveToHead(n);
        return;
      }
      Node<K, V> created = new Node<>();
      created.key = key;
      created.value = value;
      index.put(key, created);
      attachAfterHead(created);
      if (index.size() > capacity) evictTail();
    }
  }
}

Worked example: capacity 2

Walk the list from the sketch with capacity 2 so you can see which end is which. put A, put B, get A (A becomes most recently used), put C. B must leave because it is least recently used. If C evicted A, you removed from the wrong end of the list.

put A again with a new value updates in place and moves to front; size stays 2. get on a missing key returns empty and does not invent a . That walk is the seam the test at the bottom of the page asserts.

Numbers to know

Capacity is a constructor argument; reject 0 or negative there, not on first put.
get returns Optional; a miss is empty and must not create a node.
Evict tail.prev, never the head (head is most recently used).
One lock on the whole cache is the first concurrency answer; segmented locks can wait.

Invalid cases, and what still breaks

The capacity-2 walk fails in interviews for a short list of mistakes. Each one either breaks order, leaks , or lets two threads corrupt the list.

Invalid cases

Capacity 0 or negative: reject in the constructor, not on the first put.
get that does not move: a successful read must update recency or it is not LRU.
put of an existing key as a second node: update in place and move; size must not grow.
Evict from the head: head is most recently used; evict tail.prev instead.
Return Node from get: the caller can mutate links and break the list.

Concurrency

A is several pointer updates that must look atomic. get that moves a node and put that evicts are compound actions. One lock on the whole cache is an honest first answer. Segmenting the lock is a follow-up, not a minute-five requirement. Visibility still matters: a write from thread A must be visible to thread B. See thread safety.

Still fails when…

Two threads: get unlinks while put evicts the same node and corrupts the list.
You evict the head, so the most-recent entry is the one that leaves.
get returns Node, so a caller relinks the list and LRU order breaks silently.

Trade-offs

One lock is honest and simple; segmented locks are a later throughput follow-up.
A working LRU list beats an empty EvictionPolicy that never evicts correctly.
TTL and LFU wait until the recency list and the private Node are correct.

What the follow-up changes

Once the list and the lock in the failure card are honest, interviewers stretch the same object. Do not rebuild it as a cluster.

. Add an once LRU works. Frequency counting needs its own representation; do not fake LFU by sorting timestamps.
. Store an Instant on the node and compare against an injected Clock on get. Dead entries leave the same way capacity overflow does. The in-memory KV page is a cousin with expiry and a smaller API.
Distributed cache. Related System Design note (see the hero link). Do not draw Redis Cluster inside LruCache.

Wrap-up

You have the structures, the capacity-2 walk, and the invalid cases. Use the forty-five-minute plan, then the seam test, then the related notes.

Forty-five minutes

0–8Build sentinels and the HashMap. Put two keys, get one, put a third, assert eviction.
8–20Support update-in-place put. A missing get returns empty Optional.
20–32Wrap get and put with one lock and explain why the actions are compound.
32–40Keep Node off the public API so callers cannot break links.
40–45Treat LFU, TTL, and distributed cache as follow-ups, not minute-five work.

Tests that prove the seams