Spreadsheet Class with Formula Cells, Recalculation and Cycle Detection

Implement an in-memory spreadsheet class in stages. The interviewer starts with a simple version and adds requirements after each stage, and the full scope is a fair amount of code for a technical screen, so each stage should be finished and runnable before you move on rather than building the final design in one go. Cells are addressed by labels such as `A1` or `C12`: a column letter followed by a row number. The class exposes two methods: ```python class Spreadsheet: def set_cell(self, label: str, value) -> None: ... def get_cell(self, label: str) -> int | None: ... ``` ### Clarifying Questions - What is the exact label format: single-letter columns only, or also multi-letter columns such as `AA10`? Are labels case-sensitive? - Can a cell be overwritten, including changing a plain number into a formula or the reverse? - Can values be negative? ### Part 1 — Integer cells `set_cell(label, value)` stores an integer `value` in the cell. `get_cell(label)` returns the stored integer. There are no formulas in this stage, so it is meant to be finished quickly. ```hint Plan for the next stage This stage is a thin wrapper around one data structure. Pick a storage layout that will still work once a cell can hold something other than a number. ``` #### What This Part Should Cover - A storage model keyed by label, and what `get_cell` returns for a label that was never set. - Label validation at the level the interviewer asks for. - Finishing fast enough to leave time for the later stages. ### Part 2 — Formula cells `set_cell` now also accepts a formula: a string that starts with `=`. For example: - `set_cell("A1", "=B1+C1+1")`: the value of `A1` is the value of `B1` plus the value of `C1` plus 1; - `set_cell("A1", "=1+2")`: a formula made only of integer literals. `get_cell` returns the computed integer value of a cell. If a cell has never been set, `get_cell` must return `None` or report an error; handle this case explicitly. Circular references such as `A1 -> B1 -> A1` will not occur in this stage, and efficient dependency updates are not required: recomputing every previously set cell on each `set_cell` call, so that `get_cell` is O(1), is an acceptable approach. ```hint Inputs before outputs If `A1` reads `B1` and `B1` reads `C1`, recomputing the cells in the order they were set can read a stale value. Think about how to guarantee that every input of a cell is final before the cell itself is evaluated. ``` ```hint Keep what was typed Store the formula separately from its current value: the formula is needed again every time something it references changes. ``` #### Clarifying Questions for this Part - Which operators can appear in a formula: only `+`, as in the examples, or also `-`, `*` and parentheses? - When a formula references a cell that has never been set, is that cell treated as 0, or is the formula's own value undefined (`None` or an error)? - Can formulas contain whitespace, and how should a malformed formula be reported? #### What This Part Should Cover - Parsing a formula into cell references and integer literals. - Recomputation on every `set_cell` that evaluates cells in a valid order, so that chains of references produce correct values, with O(1) `get_cell`. - One consistent rule for never-set cells, both when read directly and when referenced by a formula. - The cost of recomputing everything on every write. ### Part 3 — Cycle detection and targeted recomputation (follow-up) Formulas may now form circular references, for example `set_cell("A1", "=B1")` followed by `set_cell("B1", "=A1+1")`. Add cycle detection, and optimize updates so that `set_cell` recomputes only the cells that depend, directly or indirectly, on the cell that changed. ```hint Edges in both directions Evaluating a cell needs to know what it reads; propagating a change needs to know who reads it. ``` #### Clarifying Questions for this Part - When a `set_cell` call would create a cycle, should it be rejected with the sheet left unchanged, or accepted with the cells on the cycle reporting an error? - Does a self-reference such as `set_cell("A1", "=A1+1")` count as a cycle? #### What This Part Should Cover - Detecting a cycle introduced by the new formula, including a self-reference, before any state changes, with a defined outcome. - Dependency and reverse-dependency tracking that stays correct when a formula is replaced by another formula or by a number. - Recomputation limited to the transitive dependents of the changed cell, in an order where each cell's inputs are already final. - The cost of `set_cell` and `get_cell` compared with Part 2. ### What a Strong Answer Covers - Working, tested code at the end of every stage instead of one unfinished attempt at the final design. - A data model that grows from Part 1 to Part 3 without a rewrite: the raw input, the parsed references and the cached value of each cell. - Correct evaluation order, and explicit policies for never-set references and for cycles. - Stated complexity for writes and reads, and a reasoned choice between recomputing on write and evaluating on read. ### Follow-up Questions - How would you support deleting or clearing a cell, and what happens to the formulas that reference it? - How would you extend the parser to `-`, `*`, parentheses and range functions such as `SUM(A1:A10)`, and how do ranges change the dependency graph? - If writes far outnumber reads, would you still recompute on `set_cell`, or evaluate lazily on `get_cell`? What would you cache? - How would you make the class safe to use from several threads at once?