Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Break frequency ties by recency: The Frequency Cache.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when LFU cache design matches the clues
- 2Keep this true after every move: each key belongs to exactly one recency-ordered frequency bucket
- 3Reach the result within O(1) average per operation
Rules and pressure
- Target cost: O(1) average per operation
- State rule: each key belongs to exactly one recency-ordered frequency bucket
New words in this mission
Open a term for a plain-language explanation.cache+
A fast copy of frequently needed data. It reduces repeated work, but the system must decide how stale that copy may become.
Lesson 1 of 3
Live algorithm trace
LFU cache design
Complete execution1 of 5
0
put 1
1
put 2
op
2
get 1
3
put 3
4
get 2
Both new keys enter frequency bucket one in recency order.
1
store value and frequency per key2
on access, remove from old bucket3
increment frequency and append newest4
track the minimum nonempty frequency5
evict oldest key in minimum bucket6
return recorded getsfreq1 = 1,2minFreq = 1
Truth to preserve / Cost target
Truth to preserve
each key belongs to exactly one recency-ordered frequency bucket
Cost target
O(1) average per operation
LFU eviction needs two orders: minimum access frequency first, then least recent among keys tied at that frequency.
Your call · What should guide every step of this algorithm?