Skip to question

Q026FreeDesign Verification

Retire out-of-order completions in order

Difficulty
Hard
Topic
Reference Models
Language
PYTHON
Interview prompt

Question

Model transactions issued with consecutive integer IDs starting at 0, completed out of order, and retired strictly in order. The completion window defaults to 16 entries and may be configured to any positive integer size. complete() receives integer IDs. Issuing an ID and admitting its completion are separate operations; the window limits completion eligibility, not how many IDs can be issued.

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.
Candidate starting point

Implementation scaffold

class RetirementModel:

    def __init__(self, window=16):
        """TODO: implement this method."""
        pass

    def issue(self):
        """TODO: implement this method."""
        pass

    def complete(self, transaction_id):
        """TODO: implement this method."""
        pass
Reviewed example

Trace 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 IDs in strictly increasing order, 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.
Continue practicing
Q811 · Reference ModelsCheck out-of-order completion and in-order ROB retirementMediumPQ1130 · Memory SystemsKeep exceptions precise in an out-of-order CPUMediumP