Courses › Low-Level Design › Problem Walkthroughs
Design a Spreadsheet
Formulas as a dependency graph: cycle detection, topological recalculation and parsing.
"Design a spreadsheet with formulas" is a favorite at companies that build productivity tools and at AI labs. It combines object modeling (cells, values, formulas), graph algorithms (dependency tracking, cycle detection, topological recalculation) and a little parsing. The core insight: the cells and their formula references form a directed graph, and every hard part of the question is a graph problem.
Requirements
set(cell, raw), where raw is a number ("5") or a formula ("=A1+B2*2","=SUM(A1:A3)").get(cell)returns the computed value. Empty cells count as 0.- Changing a cell updates every cell that depends on it, directly or indirectly.
- Circular references (
A1 = B1,B1 = A1) are rejected, and the sheet keeps its previous state. - Possible extras: ranges and functions, undo, error values such as
#DIV/0!.
Model
Cell id ("A1"), raw, formula | None, value
Formula expression AST; references() -> set of cell ids; evaluate(lookup)
Sheet cells; deps[cell] -> cells it reads; rdeps[cell] -> cells that read it
set(cell, raw), get(cell)Keep both directions of the graph:
deps[A3] = {A1, A2}: what A3 reads. Used to evaluate A3.rdeps[A1] = {A3}: who reads A1. Used to find what to recompute when A1 changes.
Recalculation order
When a cell changes, find every cell downstream of it by following rdeps, then recompute them in topological order, so each cell is computed after everything it reads. While building that order, check the new cell's formula for a cycle, which would mean it depends on itself.
[parse raw] -> [check new refs for a cycle] -> [update dep edges] -> [collect downstream cells] -> [topological order] -> [recompute each]Implementation
The parser handles numbers, cell references, + - * /, parentheses and SUM(range). Evaluation uses a small recursive-descent parser. The question is really about the dependency graph, so keep the parser simple and say so.
import re
from collections import defaultdict, deque
TOKEN = re.compile(r"\s*(SUM|[A-Z]+[0-9]+(?::[A-Z]+[0-9]+)?|\d+(?:\.\d+)?|[-+*/()])")
class CycleError(Exception):
pass
def expand(ref):
"""'A1:A3' -> ['A1', 'A2', 'A3'] (single column or single row ranges)."""
if ":" not in ref:
return [ref]
(c1, r1), (c2, r2) = (re.match(r"([A-Z]+)(\d+)", p).groups() for p in ref.split(":"))
if c1 == c2:
return [f"{c1}{r}" for r in range(int(r1), int(r2) + 1)]
return [f"{chr(c)}{r1}" for c in range(ord(c1), ord(c2) + 1)]
class Formula:
def __init__(self, text):
self.tokens = TOKEN.findall(text)
if "".join(self.tokens) != text.replace(" ", ""):
raise ValueError(f"bad formula: {text}")
def references(self):
return {c for t in self.tokens if t[0].isalpha() and t != "SUM" for c in expand(t)}
def evaluate(self, lookup):
self.pos, self.lookup = 0, lookup
value = self._expr()
if self.pos != len(self.tokens):
raise ValueError("trailing tokens")
return value
# expr := term (('+'|'-') term)* ; term := factor (('*'|'/') factor)*
def _peek(self):
return self.tokens[self.pos] if self.pos < len(self.tokens) else None
def _next(self):
tok = self._peek()
self.pos += 1
return tok
def _expr(self):
v = self._term()
while self._peek() in ("+", "-"):
v = v + self._term() if self._next() == "+" else v - self._term()
return v
def _term(self):
v = self._factor()
while self._peek() in ("*", "/"):
op, rhs = self._next(), self._factor()
v = v * rhs if op == "*" else v / rhs
return v
def _factor(self):
tok = self._next()
if tok == "-":
return -self._factor()
if tok == "(":
v = self._expr()
self._next() # ')'
return v
if tok == "SUM":
self._next() # '('
v = sum(self.lookup(c) for c in expand(self._next()))
self._next() # ')'
return v
if tok[0].isalpha():
return self.lookup(tok)
return float(tok)
class Sheet:
def __init__(self):
self.raw, self.formulas, self.values = {}, {}, {}
self.deps = defaultdict(set) # cell -> cells it reads
self.rdeps = defaultdict(set) # cell -> cells that read it
def get(self, cell):
return self.values.get(cell, 0.0)
def set(self, cell, raw):
formula = Formula(raw[1:]) if raw.startswith("=") else None
new_refs = formula.references() if formula else set()
if self._reaches(new_refs, cell):
raise CycleError(f"{cell} would depend on itself")
for ref in self.deps[cell]: # rewire edges
self.rdeps[ref].discard(cell)
self.deps[cell] = new_refs
for ref in new_refs:
self.rdeps[ref].add(cell)
self.raw[cell] = raw
self.formulas[cell] = formula
if formula is None:
self.values[cell] = float(raw)
for c in self._topo_downstream(cell):
self._recompute(c)
def _reaches(self, starts, target):
"""Does any cell in `starts` (transitively) read `target`?"""
stack, seen = list(starts), set()
while stack:
c = stack.pop()
if c == target:
return True
if c not in seen:
seen.add(c)
stack.extend(self.deps[c])
return False
def _topo_downstream(self, start):
affected, stack = {start}, [start] # everything downstream
while stack:
for d in self.rdeps[stack.pop()]:
if d not in affected:
affected.add(d)
stack.append(d)
indeg = {c: len(self.deps[c] & affected) for c in affected}
q = deque(c for c in affected if indeg[c] == 0) # Kahn's algorithm
order = []
while q:
c = q.popleft()
order.append(c)
for d in self.rdeps[c]:
if d in affected:
indeg[d] -= 1
if indeg[d] == 0:
q.append(d)
return order
def _recompute(self, cell):
f = self.formulas.get(cell)
if f is not None:
try:
self.values[cell] = f.evaluate(self.get)
except ZeroDivisionError:
self.values[cell] = float("nan") # stand-in for #DIV/0!s = Sheet()
s.set("A1", "2")
s.set("A2", "3")
s.set("A3", "=SUM(A1:A2)*10")
s.set("B1", "=A3-A1")
assert s.get("A3") == 50 and s.get("B1") == 48
s.set("A1", "4") # recomputes A3, then B1
assert s.get("A3") == 70 and s.get("B1") == 66
try:
s.set("A1", "=B1") # A1 → B1 → A3 → A1
except CycleError:
pass
assert s.get("A1") == 4 # rejected; nothing changedDesign decisions to explain
- Check for cycles before mutating anything. The check walks forward from the new references and asks whether any of them leads back to the cell. If so, nothing has been changed yet, so rejecting is free.
- Only recompute what's downstream, in topological order. A naive "recompute everything until nothing changes" is slower and gives wrong intermediate values.
- Store the raw input, the parsed formula and the computed value separately. The UI shows the raw text when editing and the value otherwise.
- The parser is isolated behind
Formula. New functions (AVG,IF) don't touch the dependency logic.
[!INTERVIEW] Lead with the graph "The cells form a directed graph of references. Setting a cell rewires its incoming edges, rejects the change if it would create a cycle, and recomputes the downstream cells in topological order." Saying this in the first five minutes shows the interviewer you've found the core of the problem. The parser can come later.
Follow-ups
- Undo: each
setbecomes a command that stores the previous raw value. Undoing just callssetwith the old value. See Design a Text Editor (Undo/Redo). - Large sheets: recompute lazily (mark downstream cells dirty and compute them on read), or in parallel by topological level.
- Copying a formula to another cell: relative references shift.
$A$1style absolute references don't. - Collaboration: each edit becomes an operation on a shared log. Conflicts happen per cell, and the server orders the edits.
[!TIP] Practice Design a Spreadsheet with Formulas · Graphs: Topo Sort & Dijkstra · Basic Calculator