Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Store only changes between versions: The Snapshot Ledger.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Snapshot array matches the clues
- 2Keep this true after every move: each index log has at most one final value per snapshot id
- 3Reach the result within O(1) set and snap, O(log changes) get
Rules and pressure
- Target cost: O(1) set and snap, O(log changes) get
- State rule: each index log has at most one final value per snapshot id
New words in this mission
Open a term for a plain-language explanation.snapshot+
A saved checkpoint of current state. After a crash or reconnect, the system restores this checkpoint instead of rebuilding everything from the beginning.
Lesson 1 of 3
Live algorithm trace
Snapshot array
Complete execution1 of 5
0
set 0=5
op
1
snap
2
set 0=6
3
get 0@0
4
snap
Record value 5 for the current unsnapped version zero.
1
keep a change log per index2
set writes at current snapshot id3
overwrite a same-snapshot change4
snap returns id then increments it5
get binary searches the index log6
return latest value at or before idcurrentSnap = 0log0 = [(0,5)]
Truth to preserve / Cost target
Truth to preserve
each index log has at most one final value per snapshot id
Cost target
O(1) set and snap, O(log changes) get
Each index keeps a sorted log of value changes by snapshot id. A get uses binary search for the last change at or before the requested snapshot.
Your call · What should guide every step of this algorithm?