Report exactly which beats of a burst never arrived, whatever order and repeats the arrivals had.
Hardware context: Burst response monitor for a memory or packet engine. Report the beat indices absent from a burst response.
A read burst of 8 beats completed, and the scoreboard counted 8 arrivals, so it passed. In fact beat 2 arrived twice and beat 5 never arrived. Counting arrivals tells you how many beats came, not which ones.
Write missing_indices(length, received, missing). A burst needs beats 0 to length - 1. received lists the beat numbers that arrived, in arrival order, possibly with repeats. Return status 0 and make missing hold every beat number that never arrived, each once, in ascending order.
For length = 6 and received = [4, 0, 4, 2], beats 1, 3 and 5 never arrived, so missing = [1, 3, 5].
length must be 0 to 32. Any other length returns status 1 with an empty missing array, before received is looked at. Every received number is inside the burst.
Signals in the timeline
| Signal | Width | Role |
|---|---|---|
length | 32 | input of each check |
received_count | 8 | input of each check |
Full specification
function automatic int missing_indices(input int length, input int received[], output int missing[]);
received has 0 to 64 elements, each between 0 and length - 1. Do not change or sort received.
Each case reports the status, how many beats are missing, which beats they are, and whether your missing array is in strictly ascending order.
Examples
Example 1
Repeats do not fill holes- Input
length = 6, received = [4, 0, 4, 2]
- Output
status = OK (0), missing_count = 3, missing = {1, 3, 5}, ascending = yes
Beat 4 arrived twice, but beats 1, 3 and 5 never arrived.
Example 2
An empty burst- Input
length = 0, received = []
- Output
status = OK (0), missing_count = 0, missing = {}, ascending = yes
No beat is needed, so none is missing.
Example 3
Order does not matter- Input
length = 4, received = [3, 1, 0, 2]
- Output
status = OK (0), missing_count = 0, missing = {}, ascending = yes
Every beat arrived, in a different order: nothing is missing.
Constraints and contract
- length is a signed int; legal values are 0 to 32.
- missing holds each absent beat exactly once, in ascending order.
- Keep the signature.
Hints
Hint 1
Counting arrivals fails when one beat repeats and another is missing. What could you record for each beat number instead?
Hint 2
Mark each arrival in a small array indexed by beat number; a repeat just marks the same place again.
Hint 3
Walking the beat numbers from 0 to length - 1 and collecting the unmarked ones gives the answer already in order. Size missing before you fill it.
What this judge verifies: Your function is called on directed bursts and 120 seeded ones of 0 to 32 beats with up to 64 arrivals in any order, plus invalid lengths. Passing shows the missing set, its size and its order are right on these inputs.
130 checks on Verilator · local server. Run the examples first, then check the full regression. The suite is local and inspectable. A passing result establishes the tested cases, not a proof for all possible inputs.
See all 5 steps and the final capstone