Problem
Practice version: design SaveFrame(sequence, frame) and GetFrame() for frames arriving out of order. Emit only the next expected sequence number. The source describes timestamp ordering but does not define missing-frame behaviour.
Worked examples
Input: SaveFrame(2,B); SaveFrame(1,A); GetFrame(); GetFrame()
Output: A, then B
Frame 2 waits until frame 1 arrives.
Hints
Hint 1
A map can hold pending frames while a counter tracks the next expected frame.
Solution approach
- Define starting sequence number, duplicate policy and behaviour when a frame is missing.
- Save frames by sequence in a map. GetFrame returns and removes the next expected entry only when present, then increments the counter.
- Guard map and counter together if calls may be concurrent; define bounds and timeouts for missing frames.
Complexity
Average O(1) map work per operation; O(pending frames) space.
Report & practice notes
Reconstructed practice contract. The candidate describes ordering by timestamp; sequence-number ordering here makes assumptions explicit. This is not an exact historical statement.
Read the candidate’s source report ↗