DescriptionQ701
Q701DVASIC interview problem
Verify a rotated-table minimum finder
TechniquesUVMLegal-by-constructionExact latencyRotation
DifficultyMedium
TopicConstraints
LanguageSystemVerilog
Requirements5 checkpoints
01
Problem
Implement legal-by-construction stimulus, a linear oracle, a one-request scoreboard, and exact-latency assertions for a rotated sorted-table minimum finder.
Example input and output
Use this case to check your interpretationInput
sorted table=[1,3,5,8,11], randomized rotation=2Output
One valid result: rotated=[5,8,11,1,3], minimum_index=3Explanation
A left rotation by two preserves cyclic order and places the original minimum at index three. Other rotation amounts remain valid stimulus.
02
Requirements (5)
- Generate a strictly increasing base array, choose rotation independently, and copy the rotated values into the request; include count one, unrotated, rotation one, and rotation count minus one.
- Predict the minimum with a linear scan, independent of the DUT's likely binary search, and select the lowest physical index deterministically.
- Counts outside 1 through 16 return bad_count with zeroed results one cycle after acceptance; duplicates or unsorted data are out of contract and must not be overchecked.
- For legal count, assert response exactly 2 + ceil(log2(count)) cycles after acceptance, keep req_ready low until response handshake, and hold the response under stall.
- Reset cancels pending work; identify count, rotation, minimum index, value extrema, stalls, latency, reset phase, and invalid-count classes as follow-up coverage.