Skip to main content

25. LFU Cache

hardAsked at Activision

Design a cache that evicts least-frequently-used entries with O(1) get and put — Activision uses this to gauge multi-map design before anti-cheat telemetry hot-key eviction questions.

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

Problem

Implement LFUCache with O(1) get(key) and put(key, value). When capacity is exceeded, evict the least frequently used key. Ties are broken by least-recently-used.

Constraints

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

Examples

Example 1

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

Example 2

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

Approaches

1. Hash + sort on eviction

Store (value, freq, lastUsed) per key; on eviction, scan for min freq.

Time
O(n) per eviction
Space
O(n)
// works but eviction is linear — fails large input

Tradeoff:

2. Two hash maps + freq buckets of doubly linked lists

keyMap maps key → node; freqMap maps freq → DLL of nodes with that freq. Track minFreq pointer; every get/put bumps node freq and moves it to the next bucket.

Time
O(1) per op
Space
O(n)
class LFUCache {
  constructor(cap) {
    this.cap = cap;
    this.minFreq = 0;
    this.keyToNode = new Map();
    this.freqToList = new Map();
  }
  _bump(node) {
    this.freqToList.get(node.freq).remove(node);
    if (this.freqToList.get(node.freq).empty() && node.freq === this.minFreq) this.minFreq++;
    node.freq++;
    if (!this.freqToList.has(node.freq)) this.freqToList.set(node.freq, new DLL());
    this.freqToList.get(node.freq).pushFront(node);
  }
  get(k) {
    const n = this.keyToNode.get(k);
    if (!n) return -1;
    this._bump(n);
    return n.val;
  }
  put(k, v) {
    if (!this.cap) return;
    if (this.keyToNode.has(k)) {
      const n = this.keyToNode.get(k);
      n.val = v;
      this._bump(n);
      return;
    }
    if (this.keyToNode.size >= this.cap) {
      const evict = this.freqToList.get(this.minFreq).popBack();
      this.keyToNode.delete(evict.key);
    }
    const node = { key: k, val: v, freq: 1 };
    this.keyToNode.set(k, node);
    if (!this.freqToList.has(1)) this.freqToList.set(1, new DLL());
    this.freqToList.get(1).pushFront(node);
    this.minFreq = 1;
  }
}

Tradeoff:

Activision-specific tips

Activision values clean state diagrams before code here — same hot-key eviction shape powers anti-cheat telemetry caches that bias toward retaining repeat-offender signatures.

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 LFU 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 →