Vibe Engines Learn
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
  1. You need two things per key: its value and its frequency. And per frequency, the keys at that frequency in use order (oldest first).
  2. An ordered dict (Python OrderedDict) or a Map (JS preserves insertion order) makes each frequency bucket an O(1) LRU queue.
  3. 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.
  4. 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

Explore the topic

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

Caching & Performance Algorithms & DSA