Skip to main content

25. LFU Cache

hardAsked at Baidu

Design a fixed-capacity cache that evicts the least-frequently-used key (ties broken by least-recent) in O(1) per op.

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

Problem

Design an LFU cache supporting get(key) and put(key, value) in O(1). When at capacity, evict the key with the lowest use count; on a tie, evict the least recently used among them.

Constraints

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

Examples

Example 1

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

Example 2

Input
LFUCache(0); put(0,0); get(0);
Output
-1

Approaches

1. Min-heap by (freq, timestamp)

Store entries in a min-heap keyed by frequency then timestamp; on eviction pop the heap top.

Time
O(log n) per op
Space
O(n)
// Works but loses the O(1) guarantee; interviewer will explicitly ask for O(1).

Tradeoff:

2. Hash map of keys + freq-bucketed ordered maps

Keep key->{val, freq}; for each freq keep an insertion-ordered Map of keys. Maintain minFreq pointer for O(1) eviction.

Time
O(1) per op
Space
O(capacity)
class LFUCache {
  constructor(capacity) {
    this.cap = capacity; this.size = 0; this.minFreq = 0;
    this.keyToVal = new Map();   // key -> [val, freq]
    this.freqToKeys = new Map(); // freq -> Map(key->1) insertion-ordered
  }
  _touch(key) {
    const [val, freq] = this.keyToVal.get(key);
    this.freqToKeys.get(freq).delete(key);
    if (this.freqToKeys.get(freq).size === 0) {
      this.freqToKeys.delete(freq);
      if (this.minFreq === freq) this.minFreq++;
    }
    const nf = freq + 1;
    if (!this.freqToKeys.has(nf)) this.freqToKeys.set(nf, new Map());
    this.freqToKeys.get(nf).set(key, 1);
    this.keyToVal.set(key, [val, nf]);
  }
  get(key) {
    if (!this.keyToVal.has(key)) return -1;
    this._touch(key);
    return this.keyToVal.get(key)[0];
  }
  put(key, value) {
    if (this.cap === 0) return;
    if (this.keyToVal.has(key)) {
      this.keyToVal.set(key, [value, this.keyToVal.get(key)[1]]);
      this._touch(key);
      return;
    }
    if (this.size === this.cap) {
      const bucket = this.freqToKeys.get(this.minFreq);
      const evictKey = bucket.keys().next().value;
      bucket.delete(evictKey);
      if (bucket.size === 0) this.freqToKeys.delete(this.minFreq);
      this.keyToVal.delete(evictKey);
      this.size--;
    }
    this.keyToVal.set(key, [value, 1]);
    if (!this.freqToKeys.has(1)) this.freqToKeys.set(1, new Map());
    this.freqToKeys.get(1).set(key, 1);
    this.minFreq = 1;
    this.size++;
  }
}

Tradeoff:

Baidu-specific tips

Baidu uses LFU eviction on the hottest cells of their inverted index because hits are highly skewed and LRU thrashes under bursty crawler frontiers, so they grade hard on whether you remember to update minFreq correctly on the empty-bucket case.

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

Practice these live with InterviewChamp.AI →