Spreadsheet Class With Set/Get, Cell-Reference Formulas and Cycle-Rejecting Writes

Implement an in-memory spreadsheet. Cells are named by column letters followed by a row number, such as `A1` or `C12`. The interview built the class in three parts, each extending the previous one; the code is substantial, so keep the design simple enough to finish all three. A possible interface (adjust it as you clarify): ```python class Spreadsheet: def set(self, cell: str, value: str) -> None: ... def get(self, cell: str) -> int: ... ``` ### Constraints and Clarifications - The formula syntax was not specified. Unless the interviewer says otherwise, assume a value is either an integer literal such as `"42"`, or a formula: a string starting with `=` that adds integer literals and cell references with `+`, such as `"=A1+B2+5"`. - A formula may reference cells that have not been set yet. ### Clarifying Questions - Which formula syntax must be supported: only `+`, or also `-`, `*`, parentheses, and functions over ranges such as a sum of `A1:A10`? - What does `get` return for a cell that has never been set? - When a referenced cell changes, must the next `get` of a formula cell reflect the new value? - How should a rejected write be reported: an exception, a boolean return value, or an error value stored in the cell? - Are reads much more frequent than writes, or the other way around? ### Part 1 — Set and get values Implement `set` and `get` for plain integer values. ```hint Plan for the next part Decide what a cell stores now, knowing that the next part puts formulas in the same cells. ``` #### What This Part Should Cover - Storage keyed by cell name, and validation of names and values - The value of a cell that was never set ### Part 2 — Support formulas A value that starts with `=` is a formula. `get` on a formula cell returns the formula evaluated with the current values of the cells it references, which may themselves contain formulas. ```hint Two different things in one cell Separate what the user typed into a cell from what the cell is currently worth, and decide when the second one is computed. ``` ```hint Chains of references When one cell changes, think about which other cells may now have a different value, and in what order they would have to be brought up to date. ``` #### What This Part Should Cover - Parsing a formula into references and constants - Correct values through chains of references, including after a referenced cell changes - Updating dependencies when a cell's formula is replaced - The cost of `set` and of `get` ### Part 3 — Reject writes that create a cycle If a `set` would make a cell depend on itself, directly or through other cells, reject the write and leave the spreadsheet exactly as it was before the call. ```hint What the new write adds Model references as a graph. Ask which edges the new formula adds, and what path would already have to exist for one of them to close a cycle. ``` #### What This Part Should Cover - Detecting the cycle before anything is modified - Self-references and indirect cycles - The cost of the check, and whether it can share work with the update from Part 2 ### What a Strong Answer Covers - Clarifies the formula grammar, unset cells, update semantics and error reporting before coding - Keeps the raw input and the computed value of a cell separate, with a reasoned choice between computing on read and propagating on write - Correct dependency tracking, including removing old dependencies when a formula is overwritten - Cycle detection that runs before the write is committed and leaves the sheet unchanged on rejection - Working code for all three parts within the time, with the complexity of `set` and `get` ### Follow-up Questions - Support range functions such as a sum over `A1:B10`. What changes in dependency tracking, and what does a large range cost? - With millions of cells and long chains, how do you avoid recomputing values that nobody reads? - After one cell changes, how do you guarantee that each dependent cell is recomputed exactly once, after all of its inputs? - How would you add undo for the last `set`?