Cycle Detection

What's being tested

These problems test cycle detection in a dynamic dependency graph (cells referencing cells) plus related techniques: expression parsing, incremental evaluation, and state management for updates. Interviewers probe correctness (no false-negatives/positives for cycles), performance (incremental vs full recompute), and clear API/state reasoning.

Patterns & templates

• DFS with coloring (white/gray/black) for online cycle detection — O(V+E) time, stack traces give cycle path for error messages.

• Kahn's algorithm / topological sort to compute evaluation order for acyclic graphs; detect leftover nodes as cycles.

• Adjacency list graph representation: map cell -> set(dependents) and reverse map cell -> set(dependees) for update propagation.

• Incremental evaluation via change propagation: BFS/queue from changed node through dependents, memoize values to avoid re-eval.

• Expression parsing + AST: tokenize formulas, build AST with node types (literal, ref, op), evaluate AST using resolved references. Use parseExpression then evalAST.

• Cycle prevention strategies: pre-insert tentative edge, run DFS/Kahn to validate before committing; rollback on failure.

• Complexity framing: initial parse/build O(F) per formula; full sheet recompute O(V+E); incremental updates average proportional to affected subgraph size.

Common pitfalls

Pitfall: Failing to update reverse dependency map causes stale propagation or missed re-evaluations.

Pitfall: Detecting cycles only at evaluation time (not on update) lets invalid state be visible; validate on write.

Pitfall: Using recursion without recursion-depth safeguards crashes on deep chains — prefer iterative DFS or explicit stack.

Practice these

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