Skip to main content

21. LRU Cache

mediumAsked at Quora

Design a cache that evicts the least-recently-used entry — Quora's answer-caching layer runs this exact doubly-linked-list + hash-map pattern to keep hot Q&A pairs in memory without blowing the cache budget.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Design a data structure that follows the LRU (least recently used) cache policy. Implement the LRUCache class: LRUCache(int capacity) initialises the cache with positive capacity; int get(int key) returns the value or -1 if not found; void put(int key, int value) inserts or updates the key. If capacity is exceeded, evict the LRU key. Both operations must run in O(1).

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • 0 <= value <= 10^5
  • At most 2 * 10^5 calls to get and put

Examples

Example 1

Input
LRUCache(2); put(1,1); put(2,2); get(1) → 1; put(3,3); get(2) → -1; put(4,4); get(1) → -1; get(3) → 3; get(4) → 4
Output
[null,null,null,1,null,-1,null,-1,3,4]

Explanation: Key 2 is evicted when key 3 is inserted because 1 was accessed most recently. Key 1 is evicted when key 4 is inserted.

Approaches

1. Map insertion-order (JS cheat)

JavaScript's Map preserves insertion order. On access, delete and re-insert the key to move it to the 'most recent' end. Evict Map.keys().next().value.

Time
O(1) amortised
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }
  get(key) {
    if (!this.cache.has(key)) return -1;
    const val = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, val);
    return val;
  }
  put(key, value) {
    if (this.cache.has(key)) this.cache.delete(key);
    else if (this.cache.size === this.capacity)
      this.cache.delete(this.cache.keys().next().value);
    this.cache.set(key, value);
  }
}

Tradeoff:

2. Doubly linked list + hash map

Store nodes in a doubly-linked list; a hash map from key → node gives O(1) access. Move-to-head on get/put; evict tail on overflow. The canonical O(1) solution interviewers expect.

Time
O(1)
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = { key: 0, val: 0, prev: null, next: null };
    this.tail = { key: 0, val: 0, prev: null, next: null };
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  _insertFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this._remove(node);
    this._insertFront(node);
    return node.val;
  }
  put(key, value) {
    if (this.map.has(key)) this._remove(this.map.get(key));
    const node = { key, val: value, prev: null, next: null };
    this._insertFront(node);
    this.map.set(key, node);
    if (this.map.size > this.capacity) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.key);
    }
  }
}

Tradeoff:

Quora-specific tips

Quora expects you to implement the doubly-linked-list version even in JS — using Map's insertion order is acceptable for product code but signals you may not understand the underlying mechanism. Walk through the sentinel-node trick; it eliminates null checks in remove and insert.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill LRU Cache and other Quora interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →