Problem context and objectives
Mission briefing
Live-ops game engineer · A multiplayer arena is reporting bursts of lag
Find the smallest or strongest contiguous time window: The Narrowing Beam.
Scanning the entire history after every event cannot keep up with live players.
How you win
- 1Recognize when Minimum valid window matches the clues
- 2Keep this true after every move: before each expansion, every shorter window ending earlier has already been tested
- 3Reach the result within O(n)
Rules and pressure
- Target cost: O(n)
- State rule: before each expansion, every shorter window ending earlier has already been tested
Lesson 1 of 3
With positive values, expanding the right edge never lowers the sum. As soon as the target is reached, contract the left edge repeatedly.
Your call · The sum is 8 with target 7. What happens next?