Frontend Beauty
ESC

Type to search the knowledge base.

LRU Cache

Design an LRU cache with O(1) get and put — Map + doubly linked list, Map insertion-order approach, and interview tradeoffs.

advanced4 min read
  • dsa
  • design
  • hashmap
  • linked-list
  • Google
  • Meta
  • Amazon
  • Uber

The problem

Design a data structure that follows Least Recently Used eviction:

  • get(key) → return value or -1 if missing; counts as use (moves to most-recent).
  • put(key, value) → insert or update; counts as use; if capacity exceeded, evict the least recently used key.

Both operations should be O(1) average time.

capacity = 2
put(1, 1)
put(2, 2)
get(1)       // 1  (1 is now most recent)
put(3, 3)    // evicts key 2
get(2)       // -1
put(4, 4)    // evicts key 1
get(1)       // -1
get(3)       // 3
get(4)       // 4

Why interviewers love this: hash map alone is O(1) lookup but not O(1) “find oldest”; list alone is ordered but slow lookup. You need both.

Frontend cousins: in-memory request caches, image decode caches, editor undo windows with capped size.

Approach A — Map insertion order (practical JS)

JavaScript Map iterates in insertion order. If you delete + re-set on every access, the key moves to the end (most recent). The first key is least recent.

class LRUCache {
  private capacity: number;
  private map = new Map<number, number>();

  constructor(capacity: number) {
    this.capacity = capacity;
  }

  get(key: number): number {
    if (!this.map.has(key)) return -1;
    const value = this.map.get(key)!;
    this.map.delete(key);
    this.map.set(key, value); // move to most-recent
    return value;
  }

  put(key: number, value: number): void {
    if (this.map.has(key)) {
      this.map.delete(key);
    } else if (this.map.size >= this.capacity) {
      // first key = least recently used
      const lruKey = this.map.keys().next().value as number;
      this.map.delete(lruKey);
    }
    this.map.set(key, value);
  }
}
Time O(1) amortized per op (engine Map)
Space O(capacity)

Interview note: This is valid in JS/TS interviews when you explain why order updates work. Some interviewers still want the classic DLL for language-agnostic design.

Approach B — Hash map + doubly linked list (classic)

  • Map: key → node
  • DLL: head = dummy before MRU, tail = dummy after LRU (or the reverse — pick one and stick to it)

On get/put hit: splice node out, insert after head (MRU).
On capacity overflow: remove node before tail (LRU), delete from map.

class Node {
  key: number;
  value: number;
  prev: Node | null = null;
  next: Node | null = null;
  constructor(key = 0, value = 0) {
    this.key = key;
    this.value = value;
  }
}

class LRUCache {
  private capacity: number;
  private map = new Map<number, Node>();
  private head = new Node(); // MRU side
  private tail = new Node(); // LRU side

  constructor(capacity: number) {
    this.capacity = capacity;
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  private remove(node: Node): void {
    const p = node.prev!;
    const n = node.next!;
    p.next = n;
    n.prev = p;
  }

  private insertAfterHead(node: Node): void {
    const first = this.head.next!;
    node.prev = this.head;
    node.next = first;
    this.head.next = node;
    first.prev = node;
  }

  get(key: number): number {
    const node = this.map.get(key);
    if (!node) return -1;
    this.remove(node);
    this.insertAfterHead(node);
    return node.value;
  }

  put(key: number, value: number): void {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.remove(existing);
      this.insertAfterHead(existing);
      return;
    }

    const node = new Node(key, value);
    this.map.set(key, node);
    this.insertAfterHead(node);

    if (this.map.size > this.capacity) {
      const lru = this.tail.prev!; // real LRU node
      this.remove(lru);
      this.map.delete(lru.key);
    }
  }
}
Time O(1) per get/put
Space O(capacity)

Dummy head/tail avoid null checks on edges. Practice drawing the pointers once; the code is mechanical after that.

Complexity proof points (say them)

  • Hash map get/set/delete → O(1) average
  • DLL remove/insert given a node pointer → O(1)
  • Finding LRU without a list would be O(n) scan of timestamps — that’s the fail path

Edge cases

  • capacity = 1 — every new key evicts the old
  • put same key — update value + refresh recency, no eviction
  • get miss — must not mutate order
  • Negative keys/values — fine unless constraints say otherwise

Common mistakes

  • Updating value without moving the node to MRU
  • Evicting MRU instead of LRU (pointer confusion)
  • Forgetting to delete from both map and list
  • Using an array + indexOf (O(n)) and calling it O(1)
  • In Map version: set without delete first — does not refresh order in JS Map

Follow-ups

  • LFU (least frequently used) — harder; needs freq buckets
  • TTL + LRU — real caches; eviction by time and recency
  • Thread safety — locks / concurrent maps (backend interviews)
  • size in bytes not count — weight-based eviction

Interview delivery

  1. Clarify capacity ≥ 1, return -1 on miss, update refreshes recency.
  2. Reject array-only design.
  3. Propose map + DLL or JS Map order; implement one fully.
  4. Trace the sample.
  5. State complexities.

Ship working code over perfect abstraction. Interviewers watch pointer bugs more than class naming.

Further reading