Skip to main content

24. LFU Cache

hardAsked at Riot Games

Design an O(1) least-frequently-used cache — Riot favors LFU over LRU when caching match-history queries that exhibit heavy-tail access patterns.

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

Problem

Design an LFU cache supporting get(key) and put(key, value) in O(1). On overflow, evict the least-frequently-used key; break ties with least-recently-used among the same frequency.

Constraints

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

Examples

Example 1

Input
capacity=2, ops=[put(1,1),put(2,2),get(1),put(3,3),get(2),get(3)]
Output
[null,null,null,1,null,-1,3]

Example 2

Input
capacity=0, ops=[put(0,0),get(0)]
Output
[null,null,-1]

Approaches

1. Min-heap by frequency

Track frequency and tie-break with insertion order in a heap; pop on eviction.

Time
O(log n) per op
Space
O(n)
// Heap keyed by (frequency, recency)
// Push on every access — old stale entries need lazy invalidation
// log-factor per get/put fails Riot's hot-path requirement

Tradeoff:

2. Frequency-bucketed doubly linked lists

Maintain a map of key -> node and a map of frequency -> ordered linked list of nodes; bump frequency by moving the node to the next bucket and track the current minimum frequency. Same constant-time eviction Riot needs when match-history caches must handle heavy-tail hot keys without log overhead.

Time
O(1) per op
Space
O(capacity)
class LFUCache {
  constructor(cap) {
    this.cap = cap;
    this.size = 0;
    this.minFreq = 0;
    this.keyToVal = new Map();
    this.keyToFreq = new Map();
    this.freqToKeys = new Map(); // freq -> Set (insertion-ordered)
  }
  _touch(k) {
    const f = this.keyToFreq.get(k);
    this.freqToKeys.get(f).delete(k);
    if (this.freqToKeys.get(f).size === 0) {
      this.freqToKeys.delete(f);
      if (this.minFreq === f) this.minFreq++;
    }
    this.keyToFreq.set(k, f+1);
    if (!this.freqToKeys.has(f+1)) this.freqToKeys.set(f+1, new Set());
    this.freqToKeys.get(f+1).add(k);
  }
  get(k) {
    if (!this.keyToVal.has(k)) return -1;
    this._touch(k);
    return this.keyToVal.get(k);
  }
  put(k, v) {
    if (this.cap <= 0) return;
    if (this.keyToVal.has(k)) { this.keyToVal.set(k, v); this._touch(k); return; }
    if (this.size === this.cap) {
      const bucket = this.freqToKeys.get(this.minFreq);
      const evict = bucket.values().next().value;
      bucket.delete(evict);
      if (bucket.size === 0) this.freqToKeys.delete(this.minFreq);
      this.keyToVal.delete(evict);
      this.keyToFreq.delete(evict);
      this.size--;
    }
    this.keyToVal.set(k, v);
    this.keyToFreq.set(k, 1);
    if (!this.freqToKeys.has(1)) this.freqToKeys.set(1, new Set());
    this.freqToKeys.get(1).add(k);
    this.minFreq = 1;
    this.size++;
  }
}

Tradeoff:

Riot Games-specific tips

Riot grades whether you maintain the minFreq pointer correctly across edge cases — the same invariant their match-history cache relies on to evict in O(1) under heavy-tail player query patterns without busting the server tick budget.

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

Practice these live with InterviewChamp.AI →