Roll Back the Payload Ledger
Easy About 15 min Free, no account needed
Track staged payload totals while nested checkpoints are opened and rolled back.
The brief
A packet builder stages payload bytes before sending them. It can save a checkpoint, try adding more payload, and roll back that attempt. Checkpoints may be nested.
The ledger starts with a total of zero and no checkpoints. Process each integer in events in order:
- A positive value adds that many bytes to the current total.
0saves a checkpoint containing the current state. It does not change the total.-1restores the most recently saved checkpoint and removes that checkpoint. Any older checkpoint remains available.
Return the total after every event, including checkpoint and rollback events. A rollback always has a checkpoint available. Checkpoints may remain open at the end.
For events = [5, 0, 3, 0, 7, -1, 2, -1], return [5, 5, 8, 8, 15, 8, 10, 5]. The first rollback returns to the inner checkpoint at 8. After adding 2, the second rollback returns to the older checkpoint at 5.
For [0, 4, -1, 6], return [0, 4, 0, 6]. The final addition starts from the restored total.
Implement long[] Solve(int[] events).
0 <= events.Length <= 300_000.- Each event is
-1,0, or a value between1and1_000_000_000. - Inputs contain only valid rollbacks. You do not need to handle a rollback with no open checkpoint.
- An empty input returns an empty array. Do not change
events. - Totals can exceed the range of
int.
The hidden tests include long sequences of additions and deeply nested checkpoints. Recomputing the total from all surviving additions after each event takes too long. Aim for O(n) total time, with space proportional to the output and the number of open checkpoints.
Starter code
using System;
public class Solution
{
public long[] Solve(int[] events)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Stacks
- Use last-in, first-out state for nesting, matching and expression evaluation.
Related katas
- Maximum Bracket Depth Easy Free How deep do the parentheses nest? A counter beats a stack.
- Remove All Adjacent Duplicates Easy Free Keep deleting adjacent equal pairs until none remain.
- Valid Parentheses Easy Free Are the brackets balanced and properly nested?
- Decode String Medium Free Expand k[encoded] patterns, nesting included.