10.3 Design (Cache & Data Structure Composition)

Demo: LRU Cache — LC 146 (Medium — Amazon/Meta/Google High)

Statement (Demo): Design a Least Recently Used cache with get(key) and put(key, value), both O(1). When capacity is exceeded, evict the least recently used key. Example: capacity=2: put(1,1), put(2,2), get(1) → 1, put(3,3) (evicts key 2) | ⚡ at most 2×10⁵ calls

Approach: Conceptually a HashMap + doubly linked list — O(1) lookup plus O(1) reordering. In JS, Map remembers insertion order, so one structure does both: on get, delete and re-set to move the key to the "recent" end; past capacity, delete the first key. (Be ready to explain the DLL version in the interview.)

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // insertion order = recency
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const val = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, val); // mark as most recent
    return val;
  }
  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity)
      this.map.delete(this.map.keys().next().value); // evict least recent
  }
}

Complexity: get/put O(1)