DescriptionQ636
Q636DesignASIC interview problem
Count connected fault regions in a tile map
TechniquesFlood fillVisited bitmapBounded stack
DifficultyMedium
TopicRTL Design
LanguageSystemVerilog
Requirements5 checkpoints
01
Problem
Accept a row-major fault bitmap up to 8 by 8 pixels and report how many 4-connected components contain a one. Diagonal contact alone does not connect regions.
Example input and output
Use this case to check your interpretationInput
width=3,height=3; row-major fault bitmap rows=[110,010,001]Output
component_count=2Explanation
The upper three set cells are four-connected; the bottom-right bit touches only diagonally and therefore forms a second component.
02
Requirements (5)
- Capture a width and height from 1 through 8, followed by exactly width x height pixels.
- Use fixed-size frame storage, a visited bitmap, and a bounded stack or queue; do not use recursion or dynamic allocation.
- Check row and column boundaries before enqueuing each of the four neighbors.
- Mark a cell visited when it enters the work list so it cannot be inserted more than once.
- Hold component_count and result_valid stable under backpressure and complete internal work within 2048 cycles.