Expression Parsing

What's being tested

These problems test expression parsing plus stateful dependency management: parse formulas, resolve cell references, maintain a dependency graph, and recompute affected cells correctly. Interviewers are probing whether you can turn a spreadsheet-like API into clean data structures with cycle detection and incremental evaluation.

Patterns & templates

• Recursive descent parsing for formulas like =A1+B2*3; implement parseExpr, parseTerm, parseFactor to enforce precedence.

• Tokenization separates numbers, operators, parentheses, and cell refs; keep it O(L) per formula length and reject malformed tokens early.

• Dependency graph maps cell -> dependencies and reverse cell -> dependents; updates need both directions for efficient invalidation.

• DFS cycle detection with visiting/visited states; run before committing a formula to catch A1 -> B1 -> A1.

• Incremental recomputation uses reverse graph traversal from changed cells; topologically evaluate dirty dependents in O(V+E) over impacted subgraph.

• Memoized evaluation via eval(cell) avoids repeated recomputation inside one update; invalidate cache entries reachable from changed cells.

• Stateful API design separates setValue(cell, n), setFormula(cell, expr), and getValue(cell); define behavior for missing cells, self-references, and errors.

Common pitfalls

Pitfall: Only evaluating formulas on getValue without invalidation can return stale values after upstream cells change.

Pitfall: Detecting cycles only during evaluation often leaves the spreadsheet in a partially corrupted state; validate before committing updates.

Pitfall: Forgetting to remove old dependencies when replacing a formula causes phantom updates and incorrect graph edges.

Practice these

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