Spreadsheet Formula Engine with Incremental Recalculation of Dependent Cells

Implement a small spreadsheet formula engine. Cells have names such as `A1` or `B12`. A cell holds either a number or a formula that refers to other cells, and reading a cell returns its current value. The exercise has a basic first part, then a part in which changing a cell must update only the cells that need updating rather than every cell. Between the two, the interviewer asks which tests you would write for the incremental version and then runs a prepared test suite against your code. The interface and the formula syntax were not reported; the illustration below is an assumption to make the parts concrete. ```text set("A1", "5") set("B1", "=A1+3") B1 is 8 set("C1", "=A1+B1") C1 is 13 get("C1") returns 13 set("A1", "10") B1 becomes 13 and C1 becomes 23 ``` ### Clarifying Questions - What can a formula contain: only cell references and integer constants joined by `+`, or also other operators, parentheses and functions over ranges? - What value does an empty or never-set cell have when a formula refers to it? - What should happen when an update creates a circular reference: reject the update, or store it and show an error value in the cells involved? - Are values integers or decimals, and how should a malformed formula be reported? - Are reads much more frequent than writes? That decides whether values are recomputed when a cell is set or when it is read. ### Part 1 — Set and get cells Implement `set(cell, content)` and `get(cell)`. `content` is either a number or a formula beginning with `=`. `get` returns the cell's value, with a formula evaluated from the current values of the cells it refers to. ```hint Parse once Turn a formula into the cells it refers to, plus whatever else its value needs, when it is set, rather than re-reading the text on every `get`. ``` #### What This Part Should Cover - Parsing contents into numbers and formulas, rejecting malformed input without changing the sheet - Correct values through chains of references, references to empty cells, and a cell referenced twice in one formula - Detecting a circular reference instead of recursing forever ### Part 2 — Tests for the incremental version Before writing the incremental version, list the tests you would write for it. The interviewer then runs a prepared suite, so a good list anticipates what that suite checks. ```hint Observe more than values Besides asserting values, think about how a test can tell which cells were recomputed, and which shapes of dependencies make a careless update order produce a wrong value. ``` #### What This Part Should Cover - Value tests over chains, one cell feeding many, many cells feeding one, and diamond-shaped dependencies - Tests in which a formula's references change, a formula is replaced by a number, or an update would create a cycle and must leave the sheet unchanged - A way to assert that unrelated cells are not recomputed and that each affected cell is recomputed once ### Part 3 — Recompute only the cells that need it Change the engine so that setting a cell recomputes only the cells whose values can change as a result, each after its inputs are up to date. Neither `set` nor `get` may recompute the whole sheet. ```hint Who depends on whom Think about how to find the cells that refer to a changed cell, and in what order to visit the cells downstream of a change when some of them also depend on each other. ``` #### What This Part Should Cover - Keeping the dependency information correct as formulas change - Finding the affected cells and recomputing them in an order where each is computed once, after its inputs - Rejecting a cycle before any state changes - The cost of one update in terms of the cells and references it affects ### What a Strong Answer Covers - Settles the formula syntax, the value of empty cells and the cycle policy before coding - A clear separation between parsing, the dependency graph and evaluation - Incremental recomputation in dependency order that touches only affected cells - A test list that covers diamonds, changed references, cycles and untouched cells, written before the prepared suite runs - Complexity analysis and code that stays readable within the interview's time ### Follow-up Questions - Add a function that sums a range such as `A1:A100`. How do you record the dependency on a range without adding one edge per cell? - A recomputed cell ends up with the same value as before. How do you avoid recomputing the cells downstream of it? - Writes become far more frequent than reads. Would you switch to recomputing on read, and how would you track which values are stale? - How would you support undoing the last `set`?