Skip to main content

25. LFU Cache

hardAsked at N26

Design a cache that evicts the least frequently used key, breaking ties by recency, with O(1) get and put. N26 uses this for FX-rate caching, where high-volume corridors (EUR-USD) should stay hot while one-off corridors get evicted.

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

Problem

Design LFUCache with get(key) and put(key, value) running in O(1). When inserting beyond capacity, evict the least frequently used key; if multiple keys tie on frequency, evict the least recently used among them.

Constraints

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

Examples

Example 1

Input
cap=2; put(1,1); put(2,2); get(1); put(3,3); get(2); get(3); put(4,4); get(1); get(3); get(4);
Output
1,-1,3,-1,3,4

Example 2

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

Approaches

1. Count plus scan

Track per-key frequency in a map; on eviction scan all keys to find min count and oldest.

Time
O(n) per evict
Space
O(n)
// store {key: {value, count, t}}.
// On evict: scan all entries to find min(count) then min(t).
// Too slow under 2*10^5 ops.

Tradeoff:

2. Two maps plus per-frequency LRU

Map key -> {value, freq}; map freq -> ordered set of keys at that freq. Track minFreq. On access, move key from its old freq bucket to freq+1. On eviction, drop the oldest key from the minFreq bucket. Every op is O(1).

Time
O(1) per op
Space
O(capacity)
class LFUCache {
  constructor(cap) {
    this.cap = cap;
    this.kv = new Map(); // key -> { value, freq }
    this.freq = new Map(); // freq -> Set of keys (insertion order)
    this.minFreq = 0;
  }
  _touch(k) {
    const e = this.kv.get(k);
    this.freq.get(e.freq).delete(k);
    if (this.freq.get(e.freq).size === 0) {
      this.freq.delete(e.freq);
      if (e.freq === this.minFreq) this.minFreq++;
    }
    e.freq++;
    if (!this.freq.has(e.freq)) this.freq.set(e.freq, new Set());
    this.freq.get(e.freq).add(k);
  }
  get(k) {
    if (!this.kv.has(k)) return -1;
    this._touch(k);
    return this.kv.get(k).value;
  }
  put(k, v) {
    if (this.cap === 0) return;
    if (this.kv.has(k)) { this.kv.get(k).value = v; this._touch(k); return; }
    if (this.kv.size >= this.cap) {
      const set = this.freq.get(this.minFreq);
      const evict = set.values().next().value;
      set.delete(evict);
      if (set.size === 0) this.freq.delete(this.minFreq);
      this.kv.delete(evict);
    }
    this.kv.set(k, { value: v, freq: 1 });
    if (!this.freq.has(1)) this.freq.set(1, new Set());
    this.freq.get(1).add(k);
    this.minFreq = 1;
  }
}

Tradeoff:

N26-specific tips

N26 likes when you note that LFU outperforms LRU on FX-rate caches because high-volume corridors like EUR-USD should never be evicted even after a quiet minute, while LRU would drop them.

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

Practice these live with InterviewChamp.AI →