Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Expire calls outside the live window: The Recent Gate.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Recent call queue matches the clues
- 2Keep this true after every move: the queue contains exactly the calls in [t-3000,t]
- 3Reach the result within O(1) amortized per ping
Rules and pressure
- Target cost: O(1) amortized per ping
- State rule: the queue contains exactly the calls in [t-3000,t]
New words in this mission
Open a term for a plain-language explanation.durable queue+
A waiting line that keeps work until a consumer finishes it. It absorbs bursts and lets failed work be retried.
Lesson 1 of 3
Live algorithm trace
Recent call queue
Complete execution1 of 5
0
1
ping
1
100
2
3001
3
3002
4
6002
The first call is inside its own window.
1
append the new timestamp2
compute cutoff = t - 30003
while oldest < cutoff4
remove the oldest timestamp5
record queue sizet = 1queue = [1]count = 1
Truth to preserve / Cost target
Truth to preserve
the queue contains exactly the calls in [t-3000,t]
Cost target
O(1) amortized per ping
Increasing timestamps enter a queue. Before answering, remove every timestamp older than the inclusive 3000 millisecond window.
Your call · What should guide every step of this algorithm?