Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Evict the least recently used key: The Recent Cache.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when LRU cache design matches the clues
- 2Keep this true after every move: the order runs from least recently used to most recently used
- 3Reach the result within O(1) average per operation
Rules and pressure
- Target cost: O(1) average per operation
- State rule: the order runs from least recently used to most recently used
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
LRU cache design
Complete execution1 of 5
0
put 1
op
1
put 2
2
get 1
3
put 3
4
get 2
Insert key 1 as the newest entry.
1
map key to value and order node2
on get, move key to newest3
on put, update or append newest4
if size exceeds capacity5
evict the oldest key6
return recorded getsorder = 1
Truth to preserve / Cost target
Truth to preserve
the order runs from least recently used to most recently used
Cost target
O(1) average per operation
A hash map finds keys, while recency order identifies the eviction victim. Reading or writing a key moves it to the most-recent end.
Your call · What should guide every step of this algorithm?