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.

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.

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.

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?

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