Dependency Graphs and Cycle Handling

What's being tested

This question tests reasoning over a dependency graph: building and traversing directed edges to compute values in the correct order, detect cycles, and support incremental updates. Interviewers expect familiarity with topological sort, cycle detection, incremental propagation, and clear API/edge-case handling for updates and errors.

Patterns & templates

• DFS with color-marking (white/gray/black) for both topo order and cycle detection; runtime O(V+E), watch recursion depth; implement dfs with explicit stack when large.

• Kahn's algorithm (in-degree queue) to produce a stable topological order and detect cycles when remaining nodes exist; O(V+E) time, O(V) extra space.

• Maintain a reverse-dependency graph (node → dependents) to do incremental propagation: enqueue changed nodes' dependents and recompute breadth-first.

• Memoization / cache with versioning: store computed value + version/token; invalidate dependents on write to avoid full recompute.

• Handle cycles via SCC condensation (Tarjan/Kosaraju) to either error or treat SCC as a strongly connected component with fixed-point iteration.

• For large DAGs prefer iterative algorithms and batched recompute to avoid O(N^2) repeated work; amortized cost per update should be proportional to touched nodes.

• Thread-safety: use fine-grained locks or compare-and-swap on per-cell state; avoid global locks that serialize unrelated updates.

Common pitfalls

Pitfall: Throwing a generic error on any back-edge instead of reporting a useful cycle (list the cycle nodes) makes debugging impossible for users.

Pitfall: Recomputing the entire graph on each update (O(V+E) per write) instead of using a dirty-set/queue leads to unacceptable latency on frequent small updates.

Pitfall: Using recursion without guarding depth causes stack overflow for long chains; prefer iterative stack or tail-call-safe approaches.

Practice these

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