DescriptionQ530
Q530ArchASIC interview problem
Measure latency to the next higher sample
TechniquesMonotonic stackThermal traceOrdered outputBackpressure
DifficultyMedium
TopicStreaming Algorithms
LanguageSystemVerilog
Requirements5 checkpoints
01
Problem
For every accepted temperature in a bounded trace, compute the distance to the first later sample with a strictly greater value, or zero when no such sample exists.
Example input and output
Use this case to check your interpretationInput
temperature frame = [73, 74, 75, 71, 69, 72, 76, 73]Output
distance = [1, 1, 4, 2, 1, 1, 0, 0]Explanation
The decreasing stack resolves each index when its first strictly higher later sample arrives; equal values would remain pending.
02
Requirements (5)
- Support frames of 1 to 32 unsigned eight-bit temperatures; equal values are not greater.
- Use fixed stack and result storage, and serialize multiple pops caused by one new sample.
- Do not accept a new sample until all stack work for the retained sample is complete.
- Emit results in original index order only after the frame ends.
- Hold index, distance, and last stable while output is stalled.