22. LFU Cache

hardAsked at Confluent

Design an O(1) get/put cache with least-frequently-used eviction — Confluent uses it because LFU + recency-within-frequency mirrors the partition-pinning logic in a sticky consumer assignor.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Problem

Design an LFUCache with O(1) get and put. When the cache is full, evict the least frequently used key; on ties, evict the least recently used among those.

Constraints

1 <= capacity <= 10^4
0 <= key, value <= 10^9
At most 2*10^5 calls

Examples

Example 1

Input

cap=2; put(1,1); put(2,2); get(1); put(3,3)

Output

evicts key 2 (LFU)

Example 2

Input

cap=2; put(1,1); put(2,2); get(1); get(1); put(3,3); get(2)

Output

get(2) = -1

Approaches

1. Map plus scan

Track frequency and last-used time; on eviction scan all entries to find the worst.

Time: O(n) per put
Space: O(n)

// entries: {k: {v, f, lastUsed}}; on full, scan all for min f then min lastUsed

Tradeoff:

2. Frequency map of ordered key lists

Hold key->node, key->freq, and freq->ordered list (Map preserves insertion order). On access, bump the freq and move the key. On eviction, drop the front of the minFreq list.

Time: O(1) per op
Space: O(n)

class LFUCache {
  constructor(cap) {
    this.cap = cap; this.size = 0; this.min = 0;
    this.kv = new Map(); this.kf = new Map(); this.fl = new Map();
  }
  _bump(k) {
    const f = this.kf.get(k);
    this.fl.get(f).delete(k);
    if (f === this.min && this.fl.get(f).size === 0) this.min++;
    this.kf.set(k, f + 1);
    if (!this.fl.has(f + 1)) this.fl.set(f + 1, new Map());
    this.fl.get(f + 1).set(k, true);
  }
  get(k) {
    if (!this.kv.has(k)) return -1;
    this._bump(k);
    return this.kv.get(k);
  }
  put(k, v) {
    if (this.cap === 0) return;
    if (this.kv.has(k)) { this.kv.set(k, v); this._bump(k); return; }
    if (this.size === this.cap) {
      const minList = this.fl.get(this.min);
      const evict = minList.keys().next().value;
      minList.delete(evict); this.kv.delete(evict); this.kf.delete(evict);
      this.size--;
    }
    this.kv.set(k, v); this.kf.set(k, 1);
    if (!this.fl.has(1)) this.fl.set(1, new Map());
    this.fl.get(1).set(k, true);
    this.min = 1; this.size++;
  }
}

Tradeoff:

Confluent-specific tips

Confluent treats LFU as a stand-in for partition pinning — bonus signal if you tie the freq+recency tiebreaker to sticky consumer-group rebalance keeping hot partitions on warm consumers.

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

Practice these live with InterviewChamp.AI →