Designing an O(1) LRU Cache: HashMap + Doubly Linked List, Thread-Safety, and Pluggable Eviction

Why This Problem Is Really About Two Data Structures Cooperating

“Design an LRU cache” is the most common machine-coding warm-up at SSE level, and the trap is that it looks like a data-structures puzzle when it is actually an LLD design problem. The interviewer is watching three things: can you get true O(1) for both get and put, can you keep your invariants straight under mutation, and — the part most candidates skip — can you make it thread-safe and extensible without rewriting the core.

An LRU (Least Recently Used) cache holds at most capacity entries. On every access (get or put) the touched key becomes the most recently used. When you put a new key into a full cache, you evict the least recently used key. So we need two operations to be cheap:

1. Lookup by key → screams hashmap, O(1) average.
2. Maintain a recency ordering with cheap “move to front” and “remove from back” → screams a structure with O(1) splice.

A plain array gives O(1) lookup if you also keep a hashmap, but “move to most-recent” is O(n) because you shift elements. A singly linked list can’t unlink a node in O(1) because you can’t reach its predecessor. The answer is a doubly linked list (DLL): given a node pointer you can unlink it in O(1) by rewiring prev and next. The hashmap stores key → node pointer, so lookup also hands you the node to splice. That coupling — map values are list nodes — is the whole trick.

In an interview, say this out loud early: “I’ll combine a hashmap for O(1) lookup with a doubly linked list for O(1) recency reordering; the map values are the list nodes so I never scan.” That one sentence tells the interviewer you already know the answer and lets you skip the dead-ends.

The Shape of the Solution

          HASHMAP                       DOUBLY LINKED LIST
   key ─────────────► Node              (head = MRU, tail = LRU)
   ┌──────┬────────┐                ┌──────┐   ┌──────┐   ┌──────┐
   │ "a"  │  ●─────────────────────▶│ a    │◀─▶│ c    │◀─▶│ b    │
   │ "b"  │  ●──────────┐           │ key  │   │ key  │   │ key  │
   │ "c"  │  ●─────┐    │           │ val  │   │ val  │   │ val  │
   └──────┴────────┘    │           └──────┘   └──────┘   └──────┘
                        │              ▲                      ▲
                        └──────────────┘                      │
                                       evict from here (tail) ┘

We use two sentinel nodes — a dummy head and a dummy tail — so that the list is never empty and we never special-case “inserting into an empty list” or “removing the only node.” This single decision removes the majority of off-by-one bugs candidates hit live.

[head] ⇄ MRU ⇄ ... ⇄ LRU ⇄ [tail]
   ▲                          ▲
 sentinel                  sentinel

• get(key): map miss → return null. Map hit → unlink node, splice right after head, return value. O(1).
• put(key, val): key exists → update value, move node to front. Key absent → create node, insert after head, store in map; if size > capacity, remove the node before tail (the LRU) and delete it from the map. O(1).

The two structures must be mutated together and consistently: every node in the list has exactly one map entry and vice versa. Treat “map and list agree” as your loop invariant.

Single-Threaded Implementation

Below is the full implementation. Note the sentinel nodes, the private removeNode / addToFront helpers, and how eviction reads the node just before the tail sentinel.

class DNode<K, V> {
prev: DNode<K, V> | null = null;
next: DNode<K, V> | null = null;
constructor(public key: K, public value: V) {}
}

export class LRUCache<K, V> {
private map = new Map<K, DNode<K, V>>();
// Sentinels: head.next = MRU, tail.prev = LRU
private readonly head: DNode<K, V>;
private readonly tail: DNode<K, V>;

constructor(private readonly capacity: number) {
  if (capacity <= 0) throw new Error("capacity must be > 0");
  this.head = new DNode<K, V>(null as any, null as any);
  this.tail = new DNode<K, V>(null as any, null as any);
  this.head.next = this.tail;
  this.tail.prev = this.head;
}

private removeNode(n: DNode<K, V>): void {
  n.prev!.next = n.next;
  n.next!.prev = n.prev;
}

private addToFront(n: DNode<K, V>): void {
  n.next = this.head.next;
  n.prev = this.head;
  this.head.next!.prev = n;
  this.head.next = n;
}

get(key: K): V | undefined {
  const n = this.map.get(key);
  if (!n) return undefined;
  this.removeNode(n);
  this.addToFront(n);
  return n.value;
}

put(key: K, value: V): void {
  const existing = this.map.get(key);
  if (existing) {
    existing.value = value;
    this.removeNode(existing);
    this.addToFront(existing);
    return;
  }
  const n = new DNode(key, value);
  this.map.set(key, n);
  this.addToFront(n);
  if (this.map.size > this.capacity) {
    const lru = this.tail.prev!;        // node before tail sentinel
    this.removeNode(lru);
    this.map.delete(lru.key);
  }
}
}

A note on the C++ sentinels. This version constructs sentinels with the default Node() constructor, and stores key/value in std::optional<K>/std::optional<V>. That detail matters: a naive new Node(K{}, V{}) requires both K and V to be default-constructible, and so does a bare Node() = default with non-optional members — a defaulted default constructor is implicitly deleted when a member (K key; V value;) is itself not default-constructible, so new Node() would fail to compile for exactly the value types you wanted to support. The fix is to make the members genuinely optional: std::optional<K>/<V> are default-constructible (empty) regardless of K/V, so the sentinel truly imposes no default-constructibility requirement. Real entries still require K/V to be copy-constructible (we copy into the optionals), which any usable cache type already is. Mention this if asked; “I wrapped the sentinel’s fields in optional so the sentinel imposes nothing on the value type” is a precise, senior-level observation — and notice that a plain default constructor would not have bought you that.

Complexity Analysis

The put Space column says O(1) new entry rather than ”—”: inserting a previously-unseen key allocates exactly one DLL node and one map slot before any eviction, which is O(1) additional space amortized into the O(capacity) total. Overwriting an existing key allocates nothing. A strict interviewer will want that per-insert allocation acknowledged.

The “average” qualifier matters: hashmap operations are O(1) amortized/expected, degrading to O(n) under pathological hash collisions or during a resize. In an interview, state this precisely — say “O(1) expected for the map; the linked-list work is strictly O(1) worst case.” std::unordered_map, JS Map, and Python dict all give expected O(1).

Production stdlib alternatives. Python’s dict is insertion-ordered (3.7+), so you can implement LRU with a plain dict by pop(key) then re-inserting on access and next(iter(d)) to find the oldest — no hand-rolled list. Even cleaner, collections.OrderedDict (with move_to_end and popitem(last=False)) gives LRU almost for free. Mention both as the “I’d reach for stdlib in production” answer, but implement the DLL by hand because that is what’s being tested.

Making It Thread-Safe

A cache is shared mutable state, so concurrent get/put is the realistic scenario. Critically, get is not read-only — it reorders the list — so you cannot use a naive reader-writer lock that lets multiple gets run concurrently without protecting the splice. The simplest correct design is a single mutex guarding every public operation.

The subtle point worth stating in an interview: “Even get mutates the recency list, so it must take the write lock. A shared_mutex only helps if I separate lookup from recency update — e.g. by approximating LRU.” Mentioning this distinction is a strong senior signal.

// JavaScript is single-threaded per event loop, so an in-process LRU needs
// NO lock for purely synchronous get/put — keep LRUCache.get/put synchronous.
// You only need coordination when access becomes async (e.g. load-on-miss
// hits a DB, or you serialize across worker_threads). The wrapper below adds
// an async mutex, which by construction makes get/put return Promises:
// callers MUST 'await' every access. That async conversion is the price of
// serialization here; it changes the public contract, so expose it as a
// separate AsyncLRU type rather than silently making the sync cache async.
class Mutex {
private p: Promise<void> = Promise.resolve();
async run<T>(fn: () => T | Promise<T>): Promise<T> {
  const prev = this.p;
  let release!: () => void;
  this.p = new Promise((res) => (release = res));
  await prev;
  try { return await fn(); }
  finally { release(); }
}
}

class AsyncLRU<K, V> {
private inner: LRUCache<K, V>;
private mu = new Mutex();
constructor(capacity: number) { this.inner = new LRUCache(capacity); }
// Note the Promise return types: serialization made these async.
get(key: K): Promise<V | undefined> {
  return this.mu.run(() => this.inner.get(key));
}
put(key: K, value: V): Promise<void> {
  return this.mu.run(() => this.inner.put(key, value));
}
}

C++ mutable correction. An earlier draft declared mutable std::mutex mu_ “so a const-correct get can lock.” That justification is wrong here: get mutates the recency list and therefore cannot be const, so the mutex does not need to be mutable. mutable on a mutex is only warranted when you genuinely have a const method (e.g. a true read that doesn’t reorder). Don’t carry the comment over by reflex. Also note V out{} in the wrapper’s get requires V to be default-constructible; if you want to support non-default-constructible values, return std::optional<V> populated directly on hit (copy the engaged Node::value into the result) rather than into a pre-default-constructed out.

Concurrency Trade-offs You Should Volunteer

• Single global mutex (above): trivially correct, but the lock is held for every access, so it becomes the throughput ceiling under contention. Fine as a baseline and the right thing to write first.
• shared_mutex / reader-writer lock: tempting, but wrong for strict LRU because get writes the recency list. It only helps if you relax correctness (see next bullet).
• Sharded / striped locking: partition keys into N independent sub-caches by hash(key) % N, each with its own lock and its own capacity (capacity/N). Cuts contention ~N-fold; the cost is that eviction is now per-shard, so the global eviction order is only approximately LRU. This is what real caches (e.g. Guava, Caffeine-style designs) do.
• Lock-free / sampled LRU: production caches often approximate LRU to avoid the per-get write. A common trick: keep a cheap per-entry “last accessed” timestamp updated without touching the recency list (so get can be a true read under a shared lock), and only reorder lazily or evict by sampling. Caffeine uses TinyLFU with ring buffers that batch the recency updates off the hot path. Mention this as the “how production differs” coda.

Generalizing Eviction: From LRU to LFU with Strategy

The interviewer’s natural follow-up is: “Now make it LFU” (Least Frequently Used) — evict the entry with the fewest accesses, breaking ties by recency. If your LRU logic is welded into put, you rewrite everything. The clean answer is the Strategy pattern: the cache delegates which entry to evict and how to record an access to a pluggable EvictionPolicy.

        ┌─────────────────────────┐
        │        Cache<K,V>       │
        │  - map: K -> V          │
        │  - policy ──────────────┼───────┐
        │  + get(k) / put(k,v)    │       │ delegates
        └─────────────────────────┘       ▼
                              ┌──────────────────────────┐
                              │  «interface»             │
                              │   EvictionPolicy<K>      │
                              │  + recordAccess(k)       │
                              │  + recordInsert(k)       │
                              │  + evictKey(): K | null  │
                              │  + remove(k)             │
                              └──────────────────────────┘
                                   ▲              ▲
                       ┌───────────┘              └───────────┐
              ┌──────────────────┐          ┌──────────────────┐
              │ LRUPolicy<K>     │          │ LFUPolicy<K>     │
              │ (DLL + index)    │          │ (freq buckets)   │
              └──────────────────┘          └──────────────────┘

The cache owns map: K → V; the policy owns the bookkeeping needed to pick a victim. On get, the cache calls policy.recordAccess(k). On put of a new key past capacity, it calls policy.evictKey(), drops that key from map, then policy.recordInsert(newKey).

The O(1) LFU policy

The naive LFU keeps a frequency counter per key and scans for the min on eviction — that is O(n). The O(1) LFU (the well-known design) keeps:

• values: K → (value, freq)
• buckets: freq → insertion-ordered list of keys at that frequency (a DLL or insertion-ordered map). Each bucket records keys in the order they entered the bucket, so the oldest entry in the bucket is the LRU-tiebreak victim.
• minFreq: the smallest non-empty frequency, maintained incrementally

On access, move the key from bucket f to bucket f+1 (O(1) splice); if bucket f becomes empty and f == minFreq, bump minFreq. On eviction, drop the oldest entry of buckets[minFreq] (least-recently-used among the least-frequently-used), which gives correct LFU-with-LRU-tiebreak. New inserts go to bucket 1 and reset minFreq = 1. (In the code below the “oldest entry” is reached as the first element of the insertion-ordered bucket: TS b.values().next().value, Python popitem(last=False), and C++ back() after push_front.)

interface EvictionPolicy<K> {
recordAccess(key: K): void;
recordInsert(key: K): void;
remove(key: K): void;
evictKey(): K | null;     // returns the victim, or null if empty
}

// O(1) LFU: freq -> insertion-ordered set of keys; victim = oldest in minFreq.
class LFUPolicy<K> implements EvictionPolicy<K> {
private freqOf = new Map<K, number>();
private buckets = new Map<number, Set<K>>(); // Set preserves insertion order
private minFreq = 0;

private bucket(f: number): Set<K> {
  let b = this.buckets.get(f);
  if (!b) { b = new Set<K>(); this.buckets.set(f, b); }
  return b;
}

recordInsert(key: K): void {
  this.freqOf.set(key, 1);
  this.bucket(1).add(key);
  this.minFreq = 1;
}

recordAccess(key: K): void {
  const f = this.freqOf.get(key)!;
  const b = this.buckets.get(f)!;
  b.delete(key);
  if (b.size === 0) {
    this.buckets.delete(f);
    if (this.minFreq === f) this.minFreq = f + 1;
  }
  this.freqOf.set(key, f + 1);
  this.bucket(f + 1).add(key);
}

remove(key: K): void {
  const f = this.freqOf.get(key);
  if (f === undefined) return;
  const b = this.buckets.get(f)!;
  b.delete(key);
  if (b.size === 0) this.buckets.delete(f);
  this.freqOf.delete(key);
}

evictKey(): K | null {
  const b = this.buckets.get(this.minFreq);
  if (!b || b.size === 0) return null;
  const victim = b.values().next().value as K; // oldest insertion = LRU tiebreak
  b.delete(victim);
  if (b.size === 0) this.buckets.delete(this.minFreq);
  this.freqOf.delete(victim);
  return victim;
}
}

// The shell: identical for any policy.
class Cache<K, V> {
private map = new Map<K, V>();
constructor(
  private readonly capacity: number,
  private readonly policy: EvictionPolicy<K>,
) {
  if (capacity <= 0) throw new Error("capacity must be > 0");
}
get(key: K): V | undefined {
  if (!this.map.has(key)) return undefined;
  this.policy.recordAccess(key);
  return this.map.get(key);
}
put(key: K, value: V): void {
  if (this.map.has(key)) {
    this.map.set(key, value);
    this.policy.recordAccess(key);
    return;
  }
  if (this.map.size >= this.capacity) {
    const victim = this.policy.evictKey();
    if (victim !== null) this.map.delete(victim);
  }
  this.map.set(key, value);
  this.policy.recordInsert(key);
}
}

To get LRU back, write an LRUPolicy that wraps the DLL+index from the first section behind the same interface — recordAccess moves to front, evictKey returns the tail key. The Cache shell is untouched. That is the payoff of Strategy: the eviction decision is the one axis that varies, so it is the one thing you make pluggable.

LFU complexity and the tie-break subtlety

The only correctness subtlety is maintaining minFreq: it only ever increases on access (when the min bucket empties), and resets to 1 on every insert. Get that wrong and eviction picks the wrong victim. The tie-break — oldest entry within the lowest-frequency bucket — requires the per-bucket structure to preserve insertion order (a DLL, std::list, JS Set, or Python OrderedDict), which is why a plain unordered_set per bucket is insufficient.

For thread-safety, wrap Cache exactly as you wrapped LRUCache: one mutex around get/put, since recordAccess mutates policy state on every read. The same “even reads write” caveat applies — LFU get updates frequencies, so it cannot run under a shared read lock either.