Skip to main content

9. LRU Cache

mediumAsked at Redis

Design a fixed-capacity Least-Recently-Used cache with O(1) get/put; this is the most asked Redis interview question because it mirrors maxmemory-policy allkeys-lru.

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

Problem

Implement an LRUCache class with capacity C. Support get(key) returning -1 if absent and put(key, value) evicting the least-recently-used key when at capacity. Both operations must run in average O(1).

Constraints

  • 1 <= capacity <= 3000
  • Up to 2 * 10^5 calls to get/put

Examples

Example 1

Input
["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
Output
[null,null,null,1,null,-1,null,-1,3,4]

Approaches

1. Array + linear scan

Keep a [key, value] array; on access move to front.

Time
O(n) per op
Space
O(n)
// Walk array to find key, splice, unshift.

Tradeoff:

2. Hash map + doubly linked list

Map key to a node; on get/put unlink the node and re-insert at the head. Evict the tail when over capacity. This is the data structure Redis itself approximates via its sampled-LRU eviction.

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

Tradeoff:

Redis-specific tips

Redis's allkeys-lru policy actually samples 5 keys at random and evicts the LRU among them — bring this up to show you know textbook LRU is too memory-heavy for a production KV store.

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

Practice these live with InterviewChamp.AI →