DescriptionQ476
Q476DesignASIC interview problem
Find a missing packet sequence ID
TechniquesXORKnown rangeItem count
DifficultyMedium
TopicStreaming RTL
LanguageSystemVerilog
Requirements4 checkpoints
01
Problem
After start, consume n distinct sequence IDs drawn from the inclusive range 0 through n and report the one missing value using constant word-sized state.
Example input and output
Use this case to check your interpretationInput
n=4; accepted distinct sequence IDs=[4,1,0,3]Output
missing_id=2Explanation
XOR or widened-sum constant state compares the complete 0..4 range with exactly four accepted IDs, including boundary values zero and n.
02
Requirements (4)
- Use no bitmap or external memory.
- Complete after exactly n accepted IDs and handle missing zero or missing n.
- For n equal to zero, return zero without waiting for input data.
- Hold the result until accepted and do not advance the count during input stalls.