DescriptionQ884
Q884DVDesignASIC interview problem
Verify a longest rising-trend accelerator
TechniquesDVDesignDynamic programmingSigned arithmeticTie-breaking
DifficultyMedium
TopicReference Models
LanguageSystemVerilog
Requirements5 checkpoints
01
Problem
Write an independent dynamic-programming oracle for the longest strictly increasing subsequence of signed samples and the lowest end index attaining that length.
Example input and output
Use this case to check your interpretationInput
signed samples=[3,1,2,5,4]Output
LIS length=3; lowest attaining end_index=3Explanation
Both [1,2,5] and [1,2,4] have length three, but the former ends at the lower index 3.
02
Requirements (5)
- 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.