DescriptionQ777
Q777ArchASIC interview problem
Minimize descriptor count for a payload
TechniquesDynamic programmingPacketizationReconstructionTie-breaking
DifficultyMedium
TopicHardware Algorithms
LanguageSystemVerilog
Requirements5 checkpoints
01
Problem
Express a target payload length as an exact sum of supported transfer-block sizes while using the fewest descriptors. Return one count per original size slot, or report that no decomposition exists.
Example input and output
Use this case to check your interpretationInput
target=18; block sizes in original slot order = [6, 4, 9]Output
reachable=1; descriptor_count=2; slot_counts=[0, 0, 2]Explanation
Two 9-byte blocks are an exact decomposition and no one-descriptor block equals 18.
02
Requirements (5)
- Support target lengths from 0 to 64 and one to four unique positive block sizes supplied in any order.
- Treat target zero as a valid zero-descriptor result and represent unreachable totals explicitly.
- On equal descriptor counts, prefer more uses of the largest block size, then the next largest.
- Keep enough fixed-size metadata to return counts in the original input-slot order.
- Hold the response stable under backpressure.