Mini Spreadsheet with Formulas Evaluated in set_cell and Cycle Rejection

Build a small in-memory spreadsheet with two operations: `set_cell(label, value)` stores a value in a cell, and `get_cell(label)` returns a cell's value. A label is letters followed by digits, such as `"A1"`. The exercise has three parts, and the interview expects all three to be finished within the session, so budget your time. ### Constraints and Clarifications - Formulas support only `+`; there is no `-`, `*` or `/`. - A cell's value must be computed when `set_cell` is called, not when `get_cell` is called: `get_cell` returns a stored value without evaluating anything. - Assume plain values and the constants inside formulas are integers. ### Clarifying Questions - What does `get_cell` return for a cell that was never set, and what value does a formula use when it references such a cell? - Are labels case-sensitive: is `"a1"` the same cell as `"A1"`? - Can a formula contain spaces, such as `"= A1 + 5"`? - When a value is rejected, should `set_cell` raise an error or return a status, and must the cell keep its previous content? ### Part 1 — Plain values Implement `set_cell(label, value)` and `get_cell(label)` for plain integer values. ```hint Leave room for formulas Store enough per cell that a later part can tell a constant from a formula and recompute the cell when something it depends on changes. ``` #### What This Part Should Cover - Validation and normalization of labels - Storage of values, and the behavior for cells that were never set - A representation that extends to formulas without a rewrite ### Part 2 — Formulas computed in set_cell A value that begins with `=` is a formula: a sum of integer constants and cell references, such as `"=B1+5"` or `"=A1+A2+5"`. For example, after `set_cell("A1", 10)` and `set_cell("A2", "=A1+20")`, `get_cell("A2")` returns `30`. The value must be computed during `set_cell`, not during `get_cell`. Assume standard spreadsheet behavior: a formula always reflects the current values of the cells it references, so when a referenced cell changes, every cell that depends on it, directly or through other cells, is updated within that `set_cell` call. After `set_cell("A1", 1)` in the example, `get_cell("A2")` returns `21`. ```hint Who needs to know When a cell changes, think about how you find every cell whose value depends on it, directly or through other cells. ``` ```hint Order of recomputation If A3 depends on both A1 and A2, and A2 depends on A1, decide which cell must be recomputed first after A1 changes. ``` #### Clarifying Questions for this Part - Can a formula reference a cell that has not been set yet? #### What This Part Should Cover - Parsing a formula into constants and references - Tracking dependencies in both directions - Recomputing every affected cell in a correct order during `set_cell` - The cost of `set_cell` and of `get_cell` ### Part 3 — Cycle detection Detect and reject circular dependencies. For example, after `set_cell("A1", "=B1+1")`, the call `set_cell("B1", "=A1+1")` must be rejected; likewise, after `set_cell("A1", "=B1+C1")`, the call `set_cell("C1", "=A1")` must be rejected. ```hint Check before you commit A rejected formula must leave no trace. Decide what you can check before you change any state. ``` ```hint Where a cycle can close A new formula for a cell can only create a cycle that passes through that cell. Think about what you need to search to find one. ``` #### What This Part Should Cover - Detecting whether a new formula would create a cycle of any length, including a self-reference - Rejecting the formula without modifying any state - The cost of the check, and recursion depth on long dependency chains ### What a Strong Answer Covers - Working code for all three parts within the interview time - Eager evaluation that keeps every dependent value correct after any change - A dependency graph with correctly ordered recomputation - Complete cycle detection that leaves the sheet unchanged on rejection - Clear choices for unset cells, invalid input and label normalization, with tests ### Follow-up Questions - One cell has 100,000 cells depending on it in a chain. What does `set_cell` on it cost, and would lazy evaluation be better for that workload? - How would you add `-` and `*` with operator precedence? - How would you support a range function, such as a sum over `A1:A100`? - How would you implement undo for `set_cell`?