Implement an LRU Cache in JavaScript

The problem

Implement LRUCache(capacity) with get(key) and put(key, value), both O(1). When a put exceeds capacity, evict the least recently used entry — where both get and put count as "use."

This is the single most cross-cutting interview question in the catalog: it's LeetCode 146, it's a systems question (every cache tier evicts somehow), and it's a JavaScript-specific trivia check — because JS has a one-data-structure cheat that most languages don't: Map preserves insertion order, and you're allowed to exploit it.

Where you see it in production

Eviction is what separates a cache from a memory leak — the missing piece flagged in both memoize and API-call caching. Real sightings: React Query and SWR cap cached queries, image/asset caches in infinite feeds, LRU packages (lru-cache on npm is a top-100 dependency), V8's own inline caches, HTTP caches, and virtualized-list row pools. "An unbounded Map plus LRU equals a production cache" is the framing sentence.

The JavaScript answer: one Map

Map iterates in insertion order, and delete + set moves a key to the "newest" end. That makes recency tracking free:

class LRUCache {
  #capacity;
  #map = new Map(); // insertion order IS the recency order: oldest → newest
 
  constructor(capacity) {
    if (!Number.isInteger(capacity) || capacity <= 0) {
      throw new RangeError("capacity must be a positive integer");
    }
    this.#capacity = capacity;
  }
 
  get(key) {
    if (!this.#map.has(key)) return undefined;
    const value = this.#map.get(key);
    // touch: delete + re-set moves the key to the newest position
    this.#map.delete(key);
    this.#map.set(key, value);
    return value;
  }
 
  put(key, value) {
    if (this.#map.has(key)) {
      this.#map.delete(key); // updating also counts as a touch
    } else if (this.#map.size >= this.#capacity) {
      // oldest = first key in iteration order — O(1) via the iterator
      const oldest = this.#map.keys().next().value;
      this.#map.delete(oldest);
    }
    this.#map.set(key, value);
  }
 
  get size() {
    return this.#map.size;
  }
}

Dry run (capacity 2)

const cache = new LRUCache(2);
cache.put("a", 1);      // map: a
cache.put("b", 2);      // map: a, b
cache.get("a");         // 1 → touch → map: b, a
cache.put("c", 3);      // full → evict oldest = "b" → map: a, c
cache.get("b");         // undefined — evicted
cache.get("c");         // 3 → map: a, c → touch → a, c... → c newest

The step interviewers watch: after get("a"), the eviction victim changed from a to b. If your get doesn't touch, you've built a FIFO cache wearing an LRU nametag — the #1 planted bug.

Two Map details worth saying aloud: keys().next().value reads the oldest key in O(1) (it's the first step of the iterator, not a scan), and Map keys use SameValueZero — objects by reference, NaN works as a key (the equality-algorithms tie-in).

The language-agnostic answer: hash map + doubly-linked list

The classic version — and the follow-up you must expect: "pretend Map doesn't order — now what?"

• Hash map: key → list node, for O(1) lookup.
• Doubly-linked list: nodes in recency order; head = most recent, tail = eviction victim. Doubly-linked because unlinking a node in O(1) needs prev — with a singly-linked list, finding the predecessor is O(n).

class LRUCache {
  #capacity;
  #nodes = new Map(); // key → node (used ONLY as a hash map here)
  // Sentinel head/tail avoid every edge-case null check
  #head = { prev: null, next: null };
  #tail = { prev: null, next: null };
 
  constructor(capacity) {
    this.#capacity = capacity;
    this.#head.next = this.#tail;
    this.#tail.prev = this.#head;
  }
 
  #unlink(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
 
  #pushFront(node) {
    node.next = this.#head.next;
    node.prev = this.#head;
    this.#head.next.prev = node;
    this.#head.next = node;
  }
 
  get(key) {
    const node = this.#nodes.get(key);
    if (!node) return undefined;
    this.#unlink(node);      // touch = move to front
    this.#pushFront(node);
    return node.value;
  }
 
  put(key, value) {
    const existing = this.#nodes.get(key);
    if (existing) {
      existing.value = value;
      this.#unlink(existing);
      this.#pushFront(existing);
      return;
    }
    if (this.#nodes.size >= this.#capacity) {
      const victim = this.#tail.prev;   // least recently used
      this.#unlink(victim);
      this.#nodes.delete(victim.key);
    }
    const node = { key, value, prev: null, next: null };
    this.#nodes.set(key, node);
    this.#pushFront(node);
  }
}

The sentinel nodes are the craft signal: dummy head/tail mean "empty list," "single node," and "front/back" all use the same four pointer updates — no if (this.head === null) forest. And the victim node stores its key so eviction can delete the map entry — the detail everyone forgets, leaving a map full of pointers to unlinked nodes (a leak inside the cache again).

Which to lead with in an interview? The Map version, stated as a JS-specific trick, then offer the list version unprompted. That sequencing shows you know both the platform and the fundamentals.

Edge cases interviewers probe

• get must touch (the FIFO trap above); and updating an existing key via put also touches.
• Capacity 1 — every new key evicts the old one; a good smoke test for off-by-ones in both versions.
• Storing undefined values — get returning undefined is ambiguous (miss or stored undefined?). Options: forbid undefined, expose has(), or return a sentinel. Same flag-vs-value lesson as once; pick a policy out loud.
• Object keys — both versions support them via Map; note that a cached object key keeps the key object alive (a WeakMap can't work here — it's unordered and non-iterable, so it can't pick a victim; recognizing why WeakMap doesn't fit is a nice inversion of the memoize-by-ref discussion).
• Eviction callbacks — real caches (lru-cache's dispose) notify on eviction so resources can be released; one optional constructor hook, big API-design credit.

Common mistakes

• Forgetting the touch in get.
• Array-based recency (indexOf + splice) — O(n) per operation; the question says O(1) for a reason.
• Singly-linked list ("I'll just walk to the predecessor") — O(n) unlink defeats the design.
• Evicting after inserting, briefly exceeding capacity — usually harmless, occasionally asserted against in tests; evict-then-insert is the clean order.
• Not deleting the map entry on eviction in the list version.

Follow-up questions

• "Add TTL per entry." — store expiresAt; check lazily on get (expired = miss + delete). Combining TTL and LRU is exactly what API-call memoization needed — the two questions merge into a production cache.
• "LFU instead of LRU?" — least frequently used: count-buckets of doubly-linked lists (O(1) LFU is a genuinely hard follow-up); knowing LFU beats LRU for scan-resistant workloads (one pass over N items evicts your whole hot set under LRU) is the systems-level answer.
• "Make it a memoize decorator." — wrap memoize with this cache as the storage: memoize(fn, { cache: new LRUCache(100) }) — cache policy and cache use as separate concerns.
• "Thread safety?" — single-threaded JS makes operations atomic between awaits; the real hazard is async: two in-flight fills for the same key — the in-flight dedupe problem, not a locking problem.
• "How does Map keep insertion order O(1)?" — hash table + insertion-ordered entry list maintained together — the engine implements precisely the two-structure design of your linked-list version. That's why the Map cheat works: someone already built the hard version for you.