Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Search the latest value not after a timestamp: The Time Vault.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Time based key-value store matches the clues
- 2Keep this true after every move: each key's versions remain sorted by timestamp
- 3Reach the result within O(1) append and O(log n) query
Rules and pressure
- Target cost: O(1) append and O(log n) query
- State rule: each key's versions remain sorted by timestamp
New words in this mission
Open a term for a plain-language explanation.O(log n)+
The work grows by one step when the input roughly doubles. Binary search achieves this by discarding half of the remaining search space each time.
Lesson 1 of 3
Live algorithm trace
Time based key-value store
Complete execution1 of 5
0
set bar@1
op
1
get@1
2
get@3
3
set bar2@4
4
get@5
Append the first version of foo at timestamp 1.
1
append (timestamp,value) for each set2
for each get3
binary search this key's versions4
move right when timestamp <= query5
remember the latest valid value6
return empty when no version qualifiesfoo = [(1,bar)]
Truth to preserve / Cost target
Truth to preserve
each key's versions remain sorted by timestamp
Cost target
O(1) append and O(log n) query
Append timestamped versions per key. Because timestamps increase, binary search finds the rightmost version whose timestamp does not exceed the query.
Your call · What should guide every step of this algorithm?