1,000+ ASIC Interview Questions: SystemVerilog, UVM & RTL

DescriptionQ414

Q414FWArchASIC interview problem

Find device-tree depth without recursion

TechniquesFWTreesFixed memoryCycle detectionBounds

DifficultyEasy

TopicFirmware Algorithms

LanguageSystemVerilog

Requirements4 checkpoints

Problem

Find the maximum depth of a device-node pool with fixed storage while rejecting out-of-range children, cycles, and shared children.

Type declarationSystemVerilog

typedef struct { uint8_t left, right; } node_t;
typedef enum { DEPTH_OK, DEPTH_EINVAL, DEPTH_ECORRUPT } depth_rc_t;
depth_rc_t tree_depth(const node_t *pool, uint8_t count,
                      uint8_t root, uint8_t *depth);
enum { NO_NODE = 0xFF, MAX_NODES = 31 };

Example input and output

Use this case to check your interpretation

Input

nodes: 0->{1,2}, 1->{3}, 2->{}, 3->{}; root=0

Output

maximum_depth=3

Explanation

The fixed work queue visits depths 1, 2, and 3; each reachable child appears exactly once and every index is in range.

Requirements (4)

Validate pointers, count at most 31, and the root index before the empty-tree case.
Use a fixed stack or queue carrying node depth; do not recurse or allocate.
Reject every reachable node encountered twice, including cycles and shared children.
Check each child index before reading it and leave the output unchanged on every error.