# Design an In-Memory Spreadsheet Engine Build a minimal spreadsheet engine, similar to the calculation core of a tool like Excel. The engine stores values in named cells and supports formulas that reference other cells. Reads must return the up-to-date computed value, and reads must be fast (constant-time lookup of a cached value, not a re-computation on every read). ## Cell Addressing A cell is addressed by a string of the form `"<column><row>"`, where the column is one or more uppercase letters (`A`, `B`, ..., `Z`, `AA`, `AB`, ...) and the row is a positive integer (e.g. `"A1"`, `"B2"`, `"AA10"`). You only need to support cell addresses that are passed in via the API — you do not need to materialize an entire grid. ## API Implement a class/object with the following operations: - `set_cell(cell, value)` — Set the contents of `cell`. `value` is a string that is either: - a **literal integer**, e.g. `"10"` or `"-3"`, or - a **formula**, which begins with `=` and is a sum of one or more terms separated by `+`, where each term is either an integer literal or a cell reference. Examples: `"=A1+A2"`, `"=A1+5"`, `"=B2"`, `"=10+20+C3"`. - `get_cell(cell)` — Return the **integer value** of `cell` as computed from its current contents and the current contents of every cell it (transitively) references. If a cell has never been set, treat its value as `0`. `get_cell` must be **O(1)**: it returns a stored, already-computed value rather than re-evaluating the formula tree on every call. Setting a cell must update the cached value of that cell and of every cell whose value transitively depends on it, so that subsequent `get_cell` calls are correct and constant-time. ## Required Behaviors Your engine must handle all of the following: 1. **Literals and basic reads.** After `set_cell("A1", "10")`, `get_cell("A1")` returns `10`. 2. **Formulas with references.** After `set_cell("A1", "10")`, `set_cell("A2", "20")`, `set_cell("A3", "=A1+A2")`, `get_cell("A3")` returns `30`. 3. **Updates propagate.** Continuing the above, after `set_cell("A1", "5")`, `get_cell("A3")` returns `25`. Any cell that transitively depends on a changed cell must reflect the new value. 4. **Nested / chained references.** A formula may reference a cell that is itself a formula, to arbitrary depth. After `set_cell("A1", "1")`, `set_cell("A2", "=A1+1")`, `set_cell("A3", "=A2+1")`, `get_cell("A3")` returns `3`, and updating `A1` propagates through `A2` to `A3`. 5. **Repeated references in one formula.** A formula may reference the same cell more than once, e.g. `set_cell("A3", "=A1+A1")` must count `A1` twice. 6. **Reassigning / removing references.** Re-calling `set_cell` on a cell replaces its previous contents and its previous dependencies. After `set_cell("A3", "=A1+A2")` then `set_cell("A3", "20")`, `A3` no longer depends on `A1` or `A2`, and later changes to `A1`/`A2` must not affect `A3`. Conversely, removing a reference must drop the corresponding dependency edge so stale dependencies are not left behind. ## Constraints & Assumptions - All values are integers (literals and computed results). No floating point. - Formula operators: only `+` between terms. Whitespace handling around terms is up to you; the test cases use no spaces (e.g. `"=A1+A2"`). - A reference to a never-set cell evaluates to `0`. - Cell addresses, formulas, and the number of cells are bounded by available memory; aim for `get_cell` in O(1) and `set_cell` proportional to the number of cells that depend on the cell being changed. ## Cycle Handling The engine must detect dependency **cycles** and reject the offending `set_cell` rather than looping forever or corrupting state. A cycle is created when a `set_cell` would make a cell transitively depend on itself — directly (`set_cell("A1", "=A1")`) or indirectly (`set_cell("A1", "=A2")` while `A2` already, transitively, references `A1`). When a `set_cell` would introduce a cycle, it must: - be rejected (signal an error in an idiomatic way for your language — e.g. raise an exception or return a failure status), and - leave the engine in its **previous valid state**: the cell keeps its prior contents and value, and no dependency edges from the rejected formula are retained. `set_cell` calls that do **not** create a cycle must continue to succeed normally afterward.