Dependency Graphs
Asked of: Software Engineer
Last updated

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_cellsandrevDeps[cell] -> dependents; update both whensetFormula(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
setValueorsetFormula, traverserevDepsfrom the changed cell and recompute in dependency order. -
Lazy vs eager evaluation: eager updates make
get(cell)O(1)but updates costO(affected); lazy evaluation shifts work toget. -
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), notO(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.
Featured in interview prep guides
Practice questions
Related concepts
- Graph Algorithms For Relations And RoutingCoding & Algorithms
- Graphs, Grids, And Connected ComponentsCoding & Algorithms
- Graph Algorithms, Dependency Resolution And ConnectivityCoding & Algorithms
- Graph Versioning And Path DiscoveryCoding & Algorithms
- Tree And Graph ConnectivityCoding & Algorithms
- Tree And Graph Modeling AlgorithmsCoding & Algorithms