Recover an Interrupted Agent From Its Last Checkpoint
The problem, from first principles
Checkpointing (see Checkpoint an Agent So It Can Resume After Failure) is only useful if recovery actually finds the right checkpoint — not the first one saved, not the last one saved regardless of when the crash happened, but the most recent one that existed before the crash. Pick the wrong one and recovery either redoes more work than necessary (picking an earlier checkpoint than it needed to) or, worse, tries to resume from a state that didn't actually exist yet at the time of the crash.
From theory to code
You're given every checkpoint ever saved, as (step_number, state_snapshot) pairs — not necessarily given in step order — and the crash_step the run was on when it failed. Implement find_recovery_checkpoint(checkpoints, crash_step). Return the state_snapshot of the checkpoint with the largest step_number that is still <= crash_step — the most recent valid recovery point at or before the crash. Return None if no checkpoint qualifies (every saved checkpoint happens to be after crash_step).
Constraints
- 0 to 500 checkpoints; step numbers within the log may repeat or arrive in any order.
Hints
Hint 1
Track a running "best so far" (the checkpoint with the largest qualifying step number seen), updated as you scan — you don't need to sort the checkpoints first, since a single linear scan tracking the best qualifying candidate is both simpler and doesn't depend on input order at all.
Hint 2
A checkpoint saved exactly at crash_step still counts — the boundary is inclusive (<=), not strict (<). The run was still valid at that exact step before the crash happened.
Keywords
No results yet
Run your code to check it against the examples, or submit to run every test.