Hardware interview practice
Validate micro-operation dependencies
Build a bounded dependency validator for a programmable accelerator. Load directed edges u -> v, where u must issue before v, report whether the graph is acyclic, and emit the legal node order when it is.
Reviewed example
Work through one case
Input
nodes=4; edges = [0->2, 1->2, 2->3]Expected output
acyclic=1; emitted order = [0, 1, 2, 3]Nodes 0 and 1 are initially eligible, so the lower-index rule emits 0 first; node 2 becomes eligible only after both incoming edges retire.
What to cover
Requirements
- Support 1 to 8 nodes and 0 to 16 nonduplicate directed edges; a self-edge is a cycle.
- Accept the declared edge count before start, and allow a zero-edge graph to start immediately after configuration.
- Always choose the lowest-numbered eligible node and update every affected indegree exactly once.
- Buffer the complete order until acyclicity is known so a cyclic graph emits no order tokens.
- Hold the result and each order token stable under backpressure.