Skip to main content

13. LRU Cache

mediumAsked at Baidu

Design a fixed-capacity cache that evicts the least-recently-used key when full, supporting get and put in O(1).

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

Problem

Design an LRU cache that supports get(key) and put(key, value) in O(1). When the cache reaches capacity, the least recently used key is evicted before inserting a new one.

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • Up to 2 * 10^5 operations

Examples

Example 1

Input
LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2);
Output
1, -1

Example 2

Input
LRUCache(1); put(1,1); put(2,2); get(1);
Output
-1

Approaches

1. Array + linear scan

Store [key, val] pairs in an array; promote on access by splicing to the end.

Time
O(n) per op
Space
O(capacity)
// get: find index, splice, push, return; put: same plus shift on overflow.
// Too slow for the 2*10^5 op budget but easy to reason about.

Tradeoff:

2. Hash map + JS Map insertion order

JS Map preserves insertion order — delete-then-set on access moves a key to most-recent; the first iterator key is the LRU.

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

Tradeoff:

Baidu-specific tips

Baidu caches hot inverted-index posting lists in an LRU exactly this way, so be ready to argue why JS Map ordering is acceptable in production versus rolling your own doubly-linked list.

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 Baidu interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →