Spreadsheet with addition-only formulas: set and get cells with dependent updates

Implement a spreadsheet. The report names only "the classic spreadsheet problem" and says formulas need to support only the `+` operator; the interface below is the problem's usual form, stated as an assumption to confirm with the interviewer. Cells are named by a column letter and a row number, such as `A1` or `C12`. Support two operations: - `set(cell, content)`: store `content` in `cell`. The content is either an integer, such as `5`, or a formula that starts with `=` and adds integer literals and cell references with `+`, such as `=A1+B2+3`. - `get(cell)`: return the cell's current integer value. A formula's value is the sum of its terms using the current values of the cells it references, so changing one cell changes every cell whose formula depends on it, directly or indirectly. ```text set("A1", "5") set("B1", "=A1+2") set("C1", "=A1+B1") get("C1") -> 12 set("A1", "10") get("B1") -> 12 get("C1") -> 22 ``` ```hint Formulas form a graph Look at which cells each formula reads, and think about what has to happen to the cells that read a cell when that cell's content changes. ``` ```hint Pay on read or on write Decide whether a value is computed when it is read or kept up to date when a cell is set, and what each choice costs. ``` ### Constraints and Clarifications - Formulas contain only integer literals, cell references and `+`: no other operators, parentheses or functions. - Not given: the grid size, the expected number of cells, and the ratio of reads to writes. Ask, or state your assumptions. ### Clarifying Questions - What does a reference to a cell that was never set evaluate to: 0, or an error? - What should happen when a `set` would create a cycle, such as `A1` = `=B1+1` while `B1` = `=A1+1`: reject the update, or mark the cells as errors? - Can literals be negative, and can a formula contain spaces? - Should `set` validate its input and reject malformed formulas without changing the sheet? - Are reads much more frequent than writes, or the other way round? ### What a Strong Answer Covers - Parsing contents into literal and reference terms, with validation before any state changes - A dependency graph kept in both directions: what a cell reads, and which cells read it - Propagating a change to every transitive dependent, each recomputed once and in dependency order - Cycle detection with a stated policy that leaves the sheet consistent - The cost of `set` and `get` under the chosen strategy, the alternative strategy, and tests ### Follow-up Questions - How would you add `-`, `*` and parentheses? What changes in the parser, and what stays the same? - A formula sums a range such as `A1:A1000`. How do you avoid storing a thousand edges per range or recomputing the whole range on every change? - The sheet has millions of cells and frequent writes. How do you keep `set` cheap? - How would you support undoing the last `set`?