Intermediate Representations, DAGs, And Test Workflow Compilation

What's being tested

These prompts test compiler-style graph modeling: turning shader or test-workflow inputs into an intermediate representation, validating dependencies, then applying graph algorithms and scheduling heuristics. Interviewers look for clean APIs, correct O(V + E) traversals, and practical tradeoffs around caching, side effects, heterogeneous executors, and memory layout.

Patterns & templates

• Topological sort with in_degree + queue — O(V + E) time; detects cycles when emitted count is less than V.

• DFS coloring for cycle detection — states WHITE/GRAY/BLACK; report the back edge path, not just “cycle exists.”

• DAG scheduling via ready queue — choose next node by critical path length, estimated duration, resource type, or priority metadata.

• IR node design — represent op, inputs, outputs, metadata, side effects, cache key, target executor, and deterministic serialization.

• Adjacency list vs CSR — lists are flexible for construction; CSR improves locality and parallel traversal for large static graphs.

• Compiler pipeline template — lex/parse → AST → semantic checks → SSA-like IR → optimization passes → register allocation → codegen → validation.

• Shortest path template — use Dijkstra with heap for nonnegative edge weights, O((V + E) log V); avoid it for pure DAG ordering.

Common pitfalls

Pitfall: Treating every workflow node as pure; tests with filesystem, GPU state, random seeds, or external devices need explicit side-effect and isolation modeling.

Pitfall: Giving only a high-level compiler answer; NVIDIA interviewers expect concrete passes like constant folding, dead-code elimination, SSA, register allocation, and target-specific lowering.

Pitfall: Ignoring scale; an unordered_map<vector<Node>> graph may be fine for thousands of nodes, but millions require compact IDs, CSR, and memory-aware traversal.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.