Dependency Graphs

What's being tested

These prompts test dependency graph maintenance for spreadsheet formulas: parsing expressions, tracking cell references, detecting cycles, and incrementally recomputing affected cells. A strong solution separates cell state, formula evaluation, and graph propagation instead of recomputing the whole sheet after every update.

Patterns & templates

• Bidirectional graph: maintain deps[cell] -> referenced_cells and revDeps[cell] -> dependents; update both when setFormula(cell, expr) changes references.

• Expression parsing: tokenize formulas like =A1+B2*3; use recursive descent or shunting-yard for precedence, parentheses, literals, and cell references.

• DFS cycle detection: before committing a formula, run hasPath(ref, cell) or color-state DFS; reject formulas creating back edges.

• Topological recomputation: after setValue or setFormula, traverse revDeps from the changed cell and recompute in dependency order.

• Lazy vs eager evaluation: eager updates make get(cell) O(1) but updates cost O(affected); lazy evaluation shifts work to get.

• Transactional updates: parse and validate first, then mutate deps, revDeps, and stored formula/value; rollback is simpler if validation happens before commit.

• Complexity target: update should be O(size of affected subgraph + expression sizes), not O(total cells) unless constraints are tiny.

Common pitfalls

Pitfall: Only storing forward dependencies makes propagation hard; you need reverse edges to find cells invalidated by an update.

Pitfall: Detecting cycles only during evaluation can leave the spreadsheet in a corrupted state; validate before committing the new formula.

Pitfall: Forgetting to remove old formula edges causes stale dependents and incorrect recomputations after overwriting a formula.

Practice these

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