Skip to main content

23. LFU Cache

hardAsked at Rappi

Implement a least-frequently-used cache with O(1) get and put — Rappi frames this as caching hot pickup-zone lookups in dispatch where stale low-traffic zones must be evicted first.

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

Problem

Design LFUCache(capacity) with get(key) and put(key, value) both running in O(1) average time. On overflow evict the least-frequently used key, tie-broken by least-recently used.

Constraints

  • 1 <= capacity <= 10^4
  • 0 <= key, value <= 10^9

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
get(3); put(4,4); get(1); get(3); get(4)
Output
3, -1, 3, 4

Approaches

1. Scan-on-evict

Store (key, value, freq, ts) per entry; on overflow scan all entries to find the min-freq min-ts victim.

Time
O(n) put on eviction
Space
O(n)
// map of key -> {value, freq, ts}; eviction = linear scan to find min(freq, ts).

Tradeoff:

2. freq-buckets of doubly-linked lists

Keep map key->node, map freq->DLL of nodes at that freq, and a minFreq pointer; on get bump the node up one bucket, on overflow evict tail of minFreq bucket.

Time
O(1) amortized
Space
O(n)
// Sketch:
class LFUCache {
  constructor(cap) { this.cap = cap; this.size = 0; this.minF = 0; this.kv = new Map(); this.freqList = new Map(); }
  get(k) { const n = this.kv.get(k); if (!n) return -1; this._bump(n); return n.v; }
  put(k, v) {
    if (this.cap === 0) return;
    if (this.kv.has(k)) { const n = this.kv.get(k); n.v = v; this._bump(n); return; }
    if (this.size === this.cap) { this._evictMinFreqLRU(); this.size--; }
    const node = { k, v, f: 1 };
    this.kv.set(k, node);
    this._appendToFreq(node, 1);
    this.minF = 1; this.size++;
  }
  // _bump / _evict / _appendToFreq use DLL splicing on freqList — see full impl.
}

Tradeoff:

Rappi-specific tips

Rappi expects the freq-bucket DLL design — they explicitly counter LRU-only or naive freq-only answers because their pickup-zone cache must respect both axes under sustained spike traffic.

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

Practice these live with InterviewChamp.AI →