In-Memory Spreadsheet with Formulas, Cycle Detection and Read vs Write Computation

Implement a simplified in-memory spreadsheet in Python that supports three operations: - `set_cell(cell, value)`: set the cell to a numeric value. - `set_formula(cell, formula)`: set the cell to a formula that supports addition, subtraction, multiplication and division. - `get_cell(cell)`: return the cell's current computed value. The follow-ups extend it to nested formulas, circular references and legal repeated references, and then turn to complexity and design trade-offs. ```text set_cell("A1", 5) set_cell("A2", 3) set_formula("B1", "A1 + A2") set_formula("C1", "B1 * 2") # nested: C1 reads a formula cell get_cell("C1") -> 16 set_cell("A1", 10) get_cell("C1") -> 26 set_formula("A1", "C1 - 1") get_cell("A1") -> error: circular reference A1 -> C1 -> B1 -> A1 ``` The example assumes formulas are strings of cell names, numbers and the four operators. A design that checks formulas when they are written may reject the last `set_formula` call itself instead. ### Clarifying Questions - What does a formula look like: a string such as `"A1 + B2 * 3"` that must be parsed with operator precedence and parentheses, or an already-parsed structure? Can it contain numeric literals? - What does a reference to a cell that was never set evaluate to: zero, or an error? - How should division by zero be reported? - Should a circular reference be rejected when the formula is set, or reported when a cell is read? - Does `set_cell` on a cell that holds a formula replace the formula, and the other way round? ### Part 1 — The three operations Implement `set_cell`, `set_formula` and `get_cell` for formulas whose operands are numbers and cells that hold numeric values. ```hint Two kinds of cell Decide what a cell stores when it holds a number and when it holds a formula, and what `get_cell` has to do differently for each. ``` #### What This Part Should Cover - A cell model and the three methods, with defined behavior for unset cells and for overwriting a cell - Formula evaluation with correct precedence for the four operators, or an explicitly stated formula format - Deliberate handling of division by zero and malformed formulas, with no use of `eval` on user input ### Part 2 — Nested formulas, circular references and repeated references Formulas may now reference cells that are themselves formulas, to any depth. Detect circular references and raise an error, both a direct self-reference (`A1 = A1 + 1`) and an indirect cycle such as A1 → B1 → C1 → A1. References that repeat without forming a cycle must keep working: a formula that names the same cell twice, or two cells that both read a shared cell. ```hint A shape that is not a cycle Trace a diamond: B1 and C1 both read A1, and D1 reads B1 and C1. Make sure your cycle check does not flag it, and count how many times A1 gets evaluated. ``` #### What This Part Should Cover - Evaluation of nested formulas to any depth - Cycle detection that catches self-references and indirect cycles and reports the cycle - No false positives on repeated or shared references, and no repeated evaluation of shared cells within one read - A consistent state after an error ### Part 3 — Complexity and design trade-offs Analyze the complexity of your design. Why compute the value in `get_cell`? Could the computation move into the set operations instead? If writes are rare and reads are frequent, which design fits better, and what does it need? ```hint Who has to hear about a change If values are computed when they are written, work out which other cells become wrong when one cell changes, and how you would find them quickly. ``` #### What This Part Should Cover - The cost of reads and writes in each design, in terms of the cells and references involved - Memoization within a single read versus a cache that persists across reads - Reverse dependencies and cache invalidation when a value or formula changes, including a formula overwritten with different references - A choice justified by the read/write ratio ### What a Strong Answer Covers - Clarifies the formula format, unset cells, division by zero and when cycles are reported - Working, tested code for the three operations and for nested formulas - Correct cycle detection with no false positives on repeated references - A concrete design discussion: read/write ratio, per-read memoization, a persistent cache, reverse dependencies, invalidation, and updating dependency edges when a formula is overwritten - The complexity of every operation in each design ### Follow-up Questions - One cell is read in a tight loop while its inputs change once a minute. How does each design behave? - Changing one input invalidates a long chain of dependents. How do you recompute them in a valid order, and each only once? - Add a function such as a sum over a range of cells (`A1:A100`). What changes in parsing and in dependency tracking? - How would you make the spreadsheet safe for concurrent readers and writers?