Hardware interview practice
Verify a longest rising-trend accelerator
Write an independent dynamic-programming oracle for the longest strictly increasing subsequence of signed samples and the lowest end index attaining that length.
Reviewed example
Work through one case
Input
signed samples=[3,1,2,5,4]Expected output
LIS length=3; lowest attaining end_index=3Both [1,2,5] and [1,2,4] have length three, but the former ends at the lower index 3.
What to cover
Requirements
- Use an independent O(n squared) dynamic-programming oracle with signed comparisons and one-based DP initialization for every nonempty element.
- Choose the lowest end index when multiple positions attain the same maximum length; empty input returns zero length and zero index.
- Explain why increasing, decreasing, constant, duplicate-heavy, sawtooth, alternating-extreme, and planted-subsequence arrays are useful tests.
- Return a complete prediction record so a separate tagged scoreboard can compare bad-count, length, and end index independently.
- Treat ID matching, ready/valid behavior, reset epochs, and coverage as follow-up verification architecture.