Design and implement a spreadsheet class with the following methods:
set_cell(label, value): Set a cell (identified by an Excel-style label like 'A1', 'B10') to either an integer value or a formula string. Formulas are prefixed with '=' (e.g., '=A1+A2+5') and support addition only (+). Setting a cell may update all cells that depend on it.get_cell(label): Return the current computed integer value of a cell. Must support O(1) retrieval (i.e., cached value).Part 1: Implement basic set_cell/get_cell for integer values only. A cell can be re-set.
Part 2: Extend set_cell to accept formula strings (e.g., set_cell('A1', '=B1+5') or set_cell('A2', 'A1+20')). Formulas can reference multiple cells and be chained (A3 = A1 + A2 + 5). When a cell's value changes, all cells that depend on it must be recomputed and their cached values updated (update-on-write). get_cell must remain O(1).
Part 3 (variant): Instead of updating dependents on write, compute values lazily on read (update-on-read / lazy evaluation). This is preferred when reads are infrequent relative to writes.
Part 4 / Follow-up: Detect circular dependencies (e.g., A1 = B1+1, B1 = A1+1). If setting a cell would create a cycle, raise an exception or report an error and reject the operation.
Candidates are expected to write their own test cases. Edge cases include: updating a cell that other cells reference, nested/chained references, deleting a reference, and cells with repeated references.
Now set_cell can accept a formula string (e.g., '=A1+A2+5', addition only). get_cell must still be O(1). How do you handle updates when a referenced cell changes?
What if get_cell is called very infrequently compared to set_cell? How would you change your design?
How do you detect and handle circular dependencies? E.g., A1 = B1+1, B1 = A1+1.
Write your own test cases for these operations.
| Approach | Notes |
|---|---|
| Post-order DFS (lazy / read-time evaluation) | Compute cell values only when get_cell is called by recursively resolving dependencies. Simpler write path but get_cell is no longer O(1) unless combined with memoization/invalidation. Preferred when writes are far more frequent than reads. |
| Topological sort (Kahn's algorithm / in-degree) | Process cells in dependency order using in-degree counting. Naturally detects cycles (cells left with non-zero in-degree after sort). Slightly more complex to implement incrementally than DFS but cleanly handles the full DAG. |
Common mistakes: Spending too much time talking or asking clarifying questions, leaving insufficient time to implement Part 2 or reach Part 3.; Writing a bug in the Part 2 update logic and spending a long time debugging it, which prevented reaching Part 3.; Mentioning cycle detection too early (before the interviewer asked), causing the interviewer to redirect focus and consuming planning time.; Not finishing the implementation — one candidate was one line away from completion when time was called.
Interviewer hints: When a candidate raised cycle detection before being asked, the interviewer said 'let's not do that yet' and redirected to completing Part 2 first.; The interviewer in Part 1 explicitly asked candidates to think carefully about what data structure to use to store cells.; The problem statement explicitly states that get_cell must be O(1) (cached value), and that updates to dependents must happen at write time — this is a stated constraint, not something to infer.; After candidates wrote their own test cases, the interviewer added additional test cases and ran them, so the solution needed to handle edge cases beyond what the candidate tested.; The formula prefix '=' may or may not be present (one report showed 'A1+20' without '='), so parsing should handle both forms.
What passers do: Completing Part 2 fully — with formula parsing, cached values updated on write, and the reverse-dependency map — was sufficient to pass the phone screen even without reaching Part 3 (cycle detection).; Storing the formula separately from the cached integer value per cell, so formulas can be re-evaluated whenever any upstream cell changes.; Using DFS (post-order or otherwise) to propagate updates through the reverse-dependency graph when a cell is set.; Putting all computation logic inside set_cell rather than get_cell, keeping get_cell a plain O(1) cache lookup.