CODING CHALLENGE · N°32

LFU Cache

Hard DesignCachingHash Map

The cache that evicts what you use least often — and, on ties, least recently. Harder than LRU because you must track frequency and recency together, yet still hit O(1) per operation. Replay a sequence of get/put ops and return the outputs. Solve it in Python or TypeScript, with hidden tests.

The problem

Design an LFU (least-frequently-used) cache with a fixed capacity. On get(key), return the value (and bump its use count) or -1 if absent. On put(key, value), insert/update it; if the cache is full, evict the least-frequently-used key, breaking ties by evicting the least-recently-used among those. You are given a list of ops like ["put",1,1] and ["get",1]; return the list of outputs from every get, in order. Every operation must be O(1).

EXAMPLE 1

Input cap = 2, ops = [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["get",3]]

Output [1, -1, 3]

put 3 evicts key 2 (freq 1) not key 1 (freq 2); get 2 → -1

CONSTRAINTS

1 ≤ capacity; a get and a put of an existing key both count as a use (raise its frequency).
Ties in frequency are broken by recency: evict the least-recently-used key among those with the minimum frequency.
All operations must be O(1) — track a per-frequency ordered bucket and the current minimum frequency; do not scan.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement lfu_ops(cap, ops): keep value/frequency maps plus, for each frequency, an insertion-ordered bucket of keys. Track min_freq. A use moves a key up one bucket; eviction pops the oldest key from the min_freq bucket. Return the outputs of every get.

HINTS — 4 IDEAS

You need two things per key: its value and its frequency. And per frequency, the keys at that frequency in use order (oldest first).
An ordered dict (Python OrderedDict) or a Map (JS preserves insertion order) makes each frequency bucket an O(1) LRU queue.
On a use: remove the key from its current frequency bucket, add it to the (freq+1) bucket. If you just emptied the min_freq bucket, increment min_freq.
On eviction (cache full, inserting a new key): pop the oldest key from the min_freq bucket, then insert the new key at frequency 1 and set min_freq = 1.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Evict the entry with the lowest access frequency; break ties by evicting the least-recently-used among them. Keep a per-key frequency count and, crucially, frequency buckets — one list per count, each ordered by recency — plus a pointer to the minimum non-empty bucket, so get, put, and eviction all stay O(1) instead of scanning for the minimum.

Complexity

Time O(1) for get, put, and eviction with the frequency-bucket structure; space O(capacity).

Common mistakes

Scanning the whole cache for the least-frequent victim — O(n) per eviction.
Not breaking frequency ties by recency, so eviction is ambiguous.
Forgetting to bump the frequency (and move the entry to the next bucket) on a read.

Where this shows up

LFU suits caches where popularity is stable — a hot set that stays hot, like CDN edges or some database buffer pools. The choice between LFU (frequency) and LRU (recency) comes down to which better predicts the next access for your workload; getting O(1) on either is the textbook data-structure win.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Caching & Performance Algorithms & DSA