Skip to question
asic.fyi

Hardware interview practice

Retire out-of-order completions in order

HardReference ModelsPYTHON

Model transactions issued with increasing IDs, completed out of order, and retired strictly in order through a 16-entry completion window.

Reorder-window timeline showing completions arriving out of order and retirement advancing only through a contiguous completed prefix.
Completion can arrive out of order; retirement advances only from the current head through contiguous completed entries.
Reviewed example

Work through one case

Input
issue IDs 0,1,2,3; complete in order 2,0,1,3
Expected output
retired after each completion: [], [0], [1,2], [3]

Completion 2 waits in the 16-entry window until IDs 0 and 1 form a contiguous completed prefix.

What to cover

Requirements

  1. Issue monotonically increasing IDs starting at zero.
  2. Accept completion only for an issued, not-yet-retired, not-already-completed ID.
  3. Define the 16 legal slots as next_retire through next_retire + 15.
  4. After each completion, retire the longest contiguous completed prefix and return those retired IDs.