Hardware interview practice
Verify a rotated-table minimum finder
Implement legal-by-construction stimulus, a linear oracle, a one-request scoreboard, and exact-latency assertions for a rotated sorted-table minimum finder.
Reviewed example
Work through one case
Input
sorted table=[1,3,5,8,11], randomized rotation=2Expected output
One valid result: rotated=[5,8,11,1,3], minimum_index=3A left rotation by two preserves cyclic order and places the original minimum at index three. Other rotation amounts remain valid stimulus.
What to cover
Requirements
- 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.