Skip to main content

17. LRU Cache

mediumAsked at Activision

Design a cache with O(1) get and put that evicts least-recently-used entries — Activision uses this to gauge hashmap-plus-doubly-linked-list design before leaderboard hot-cache questions.

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

Problem

Design an LRUCache class supporting get(key) and put(key, value) in O(1). When capacity is exceeded, evict the least recently used key. Get marks the key as most-recently-used.

Constraints

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

Examples

Example 1

Input
ops=["LRUCache","put","put","get","put","get"], args=[[2],[1,1],[2,2],[1],[3,3],[2]]
Output
[null,null,null,1,null,-1]

Example 2

Input
capacity=1; put(1,1); put(2,2); get(1)
Output
-1

Approaches

1. Array scan

Array of [key,value]; linear scan on each op.

Time
O(n) per op
Space
O(n)
// scan list to find/evict — O(n), fails large input

Tradeoff:

2. Hash + doubly linked list

Hash maps key → node; doubly linked list keeps recency order. Move-to-front on access, evict tail when over capacity.

Time
O(1) per op
Space
O(n)
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) {
      this.map.delete(this.map.keys().next().value);
    }
  }
}

Tradeoff:

Activision-specific tips

Activision values when you spell out the eviction invariant before coding — the same hot-cache shape powers leaderboard top-N reads and recent-match lookups.

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

Practice these live with InterviewChamp.AI →