Design a spreadsheet with formulas

01The design, in the six-step framework

1. Requirements and use cases

A user sets a cell to a number or to a formula that adds and subtracts other cells and numbers, such as =A1+B2-3. Reading a cell returns its current value. Changing a cell updates every cell that depends on it, directly or through other cells. A formula that would make a cell depend on itself, even through a chain, is rejected and the sheet is left exactly as it was. Interested parties, such as a display, are told which cells changed.

Out of scope: multiplication, ranges, strings and error values; those are parser extensions, and the reported phone interview limited the grammar to plus and minus on purpose. Extensible aggregates over ranges are the next problem.

Constraints: a change must recalculate each affected cell once, not once per path through the graph; the cycle check must run before any state is mutated; unset cells read as zero; the formula text is kept so a cell can be re-evaluated and displayed.

2. Core entities and relationships

• Spreadsheet: owns the cells by reference and the listeners; the only entry point for mutation.
• Cell: its reference, the formula text or None, the cached value, and two sets: the cells it reads (deps) and the cells that read it (dependents).
• Term: one signed item of a parsed formula, either a reference or a literal; immutable.
• parse: a tokenizer for the tiny grammar; it raises a positioned error on bad input.
• CycleError: raised before any mutation when a new formula would close a loop.

The sheet composes cells. Cells reference each other only by string, never by object, so deleting or rewriting a cell cannot leave a dangling pointer; the two sets form a graph stored in both directions, forward for the cycle check and backward for recalculation.

3. Interfaces and key methods

class Cell:
    ref: str                      # "A1"
    formula: str | None           # "=A1+B2" or None for a literal
    value: int
    deps: set[str]                # cells this one reads
    dependents: set[str]          # cells that read this one

class Spreadsheet:
    def set_cell(self, ref: str, content: str) -> None:
        """A number or a formula with + and -; raises CycleError, leaves the sheet unchanged."""
    def get_cell(self, ref: str) -> int:
        """Current value; unset cells are 0."""
    def on_change(self, cb: Callable[[str, int], None]) -> None:
        """Notified for every cell whose value changed, including dependents."""

Invariants: b in a.deps if and only if a in b.dependents; the dependency graph is acyclic after every successful set_cell; every cached value equals the evaluation of its formula over current values; a rejected set_cell changes nothing.

4. Design patterns and the choices behind them

Cache values, recalculate downstream in topological order

The force is read versus write cost. Evaluating recursively on every get_cell (the reported candidate's first answer) is simple but makes a read O(size of the subgraph) and repeats work for shared sub-formulas. Caching the value and pushing changes downstream makes reads O(1) and writes proportional to what actually depends on the cell. A depth-first post-order over dependents, reversed, gives an order in which each cell is evaluated after everything it reads, so each cell is computed exactly once per change.

Check the cycle before touching state

The reported edge case is redefining a cell so that it creates a cycle. The check is a reachability search from the new dependencies back to the cell, run on the old graph before rewiring. Detecting the cycle during recalculation (by hitting a visited node) was rejected because by then half the graph is rewired and must be rolled back (see failing at the boundary).

A parser that produces terms, not a tree

With only plus and minus and no precedence, a flat list of signed terms is the correct representation; building an expression tree with a visitor is the right move the moment multiplication or parentheses appear, and it is worth saying that the step from the list to the tree is local to parse and _evaluate (see parsing and tokenizing).

Observer for changed cells

A display should redraw only what changed. Listeners are called with each cell whose value actually changed during recalculation, which is the observer pattern with change detection built in; a cell that recomputed to the same value stays quiet.

5. Core flow and code

1. set_cell("A1", "2") and set_cell("B1", "=A1+3"): B1's parse yields deps {A1}; the cycle check from A1 finds nothing; A1.dependents gains B1; B1 evaluates to 5 and listeners hear B1=5.
2. set_cell("C1", "=B1-A1"): deps {B1, A1}; C1 becomes 3.
3. set_cell("A1", "10"): no formula, so A1.value becomes 10; the recalculation visits dependents B1 and C1, orders them B1 then C1, evaluates B1=13 and C1=3. C1's value did not change, so only A1 and B1 are reported.
4. set_cell("A1", "=C1"): the check walks C1's deps to B1 and A1, finds A1, raises CycleError. A1 still holds 10 and no dependents were rewired.

import re
from dataclasses import dataclass, field
from typing import Callable

class CycleError(Exception): pass

TOKEN = re.compile(r"\s*([A-Z]+\d+|\d+|[+-])")

@dataclass
class Cell:
    ref: str
    formula: str | None = None
    value: int = 0
    deps: set[str] = field(default_factory=set)
    dependents: set[str] = field(default_factory=set)

@dataclass(frozen=True)
class Term:
    sign: int
    ref: str | None = None        # a cell reference ...
    literal: int = 0              # ... or a number

def parse(formula: str) -> list[Term]:
    """'=A1 + 3 - B2' -> [Term(+1, 'A1'), Term(+1, literal 3), Term(-1, 'B2')]"""
    body = formula[1:]
    pos, sign, terms = 0, 1, []
    while pos < len(body):
        m = TOKEN.match(body, pos)
        if not m:
            raise ValueError(f"bad token at {pos}: {body[pos:]!r}")
        tok = m.group(1); pos = m.end()
        if tok == "+": sign = 1
        elif tok == "-": sign = -1
        elif tok.isdigit(): terms.append(Term(sign, literal=int(tok))); sign = 1
        else: terms.append(Term(sign, ref=tok)); sign = 1
    return terms

class Spreadsheet:
    def __init__(self) -> None:
        self._cells: dict[str, Cell] = {}
        self._listeners: list[Callable[[str, int], None]] = []

    def _cell(self, ref: str) -> Cell:
        return self._cells.setdefault(ref, Cell(ref))

    def on_change(self, cb: Callable[[str, int], None]) -> None:
        self._listeners.append(cb)

    def get_cell(self, ref: str) -> int:
        return self._cells[ref].value if ref in self._cells else 0

    def set_cell(self, ref: str, content: str) -> None:
        cell = self._cell(ref)
        new_formula = content if content.startswith("=") else None
        new_deps = {t.ref for t in parse(content) if t.ref} if new_formula else set()
        if self._would_cycle(ref, new_deps):
            raise CycleError(f"{ref} would depend on itself")
        for d in cell.deps:                       # rewire the dependency graph
            self._cell(d).dependents.discard(ref)
        for d in new_deps:
            self._cell(d).dependents.add(ref)
        cell.deps, cell.formula = new_deps, new_formula
        if new_formula is None:
            cell.value = int(content)
        self._recalculate_from(ref)

    def _would_cycle(self, ref: str, new_deps: set[str]) -> bool:
        stack, seen = list(new_deps), set()
        while stack:
            cur = stack.pop()
            if cur == ref: return True
            if cur in seen: continue
            seen.add(cur); stack.extend(self._cells[cur].deps if cur in self._cells else ())
        return False

    def _evaluate(self, cell: Cell) -> int:
        return sum(t.sign * (self.get_cell(t.ref) if t.ref else t.literal) for t in parse(cell.formula))

    def _recalculate_from(self, start: str) -> None:
        """Topological order over everything downstream of start, each cell evaluated once."""
        order, seen = [], set()
        def visit(r: str) -> None:
            if r in seen: return
            seen.add(r)
            for d in self._cells[r].dependents: visit(d)
            order.append(r)
        visit(start)
        for r in reversed(order):                 # start first, then its dependents
            c = self._cells[r]
            new = self._evaluate(c) if c.formula else c.value
            changed = new != c.value or r == start
            c.value = new
            if changed:
                for cb in self._listeners: cb(r, new)

6. Extensions, concurrency and what interviewers probe

• Multiplication and parentheses: replace the term list with a recursive-descent parser producing an expression tree; _evaluate becomes a tree walk and nothing in the graph logic changes.
• Ranges such as SUM(A1:A100): expand the range into deps at set time; for large ranges switch to the aggregation interface from the next problem so traversal is not duplicated per function.
• Diamond dependencies: D reads B and C, both read A. The topological pass evaluates D once after both; naive recursion with notification would evaluate it twice and might report an intermediate wrong value.
• Concurrency: wrap set_cell in one lock; reads of cached ints are safe. Fine-grained locking across a graph invites deadlock for no gain at spreadsheet scale.
• Test first: the four-step scenario above, asserting values and the exact list of notifications; then a self-reference =A1 in A1; then a three-cell cycle through a redefinition.
• Common mistake: detecting cycles only at evaluation time, after the graph has been mutated, and recalculating recursively so shared cells are evaluated once per path.

02Where this question was reported

• LeetCode Discuss · LeetCode 631 (Hard), Google-tagged (freq 12.8); also LeetCode 3484 Design Spreadsheet (freq 8.2)
• Codemia · Codemia Hard
• LeetCode Discuss · Hash table + recursive evaluation; +/- only; edge case where redefining a cell creates a cycle
• PracHub · Google: add new aggregate without duplicating traversal; aggregate init/accumulate/finalise interface; cycles, caching, chunk merging