0

Spreadsheet with live formulas and cycle detection

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Spreadsheet with live formulas and cycle detection

Companies: OpenAI

Difficulty: Hard

Problem statement

Build an in-memory spreadsheet. Columns are A to Z and rows are 1 to 100, so addresses run from A1 to Z100. Every cell starts empty and reads as 0.0.

Implement a Spreadsheet class:

  • set_cell(cell: str, raw: str) -> None sets the content of cell. raw is either a number ("42", "-3.5") or a formula that starts with =.
  • get_cell(cell: str) -> float returns the current value of cell.

A formula can use numbers, cell references, +, -, *, /, unary minus and parentheses, with the usual precedence (for example =(B2 + 4) * C7 / 2). Spaces are allowed. A formula always reflects the current values of the cells it reads: when an input changes, everything that depends on it, directly or indirectly, changes too.

Rules:

  • If raw is malformed or refers to an address outside the grid, raise ValueError and leave the sheet unchanged.
  • If the new content would create a circular reference (a cell that depends on itself, directly or through other cells), raise ValueError and leave the sheet unchanged. The cell keeps its previous content.
  • You may assume no formula divides by zero.

Part 1. Make it correct. Part 2. The sheet is read far more often than it is written: make get_cell O(1) while keeping every value current.

Example 1

set_cell("C3", "4")
set_cell("D3", "=C3 * 3 - 2")   # D3 = 10.0
set_cell("E5", "=D3 + C3")      # E5 = 14.0
set_cell("C3", "1")
get_cell("D3")  -> 1.0
get_cell("E5")  -> 2.0
get_cell("Q9")  -> 0.0          # never set

Example 2

set_cell("B1", "=B2 + 1")       # B2 is empty, so B1 = 1.0
set_cell("B2", "=B1 * 2")       # raises ValueError: B1 -> B2 -> B1
get_cell("B2")  -> 0.0          # unchanged

Constraints: at most 2,600 cells, formulas up to 200 characters, and up to 10^4 calls in total.

Approach

The sheet is a directed graph: an edge X -> Y means "Y's formula reads X". Three things have to be right: parsing a formula, rejecting a write that would close a cycle, and keeping every value current when an input changes.

Brute force (lazy evaluation). Store only the raw formula per cell. get_cell parses the formula and recursively calls get_cell on every referenced cell, tracking the cells on the current recursion path to detect a cycle. set_cell is O(1). This is the natural part 1 answer and worth writing first if the interviewer starts there, but get_cell costs time proportional to the whole upstream subgraph, and the same cell is recomputed many times in a diamond (D1 = B1 + C1, both reading A1). Memoising with a cache fixes repeated reads, but then every write has to invalidate everything downstream, which needs the reverse edges anyway.

Optimal for read-heavy use (eager propagation). Keep both edge directions and a cached value per cell, so get_cell is a dictionary lookup.

  1. Parse the new content into tokens and run the parser once in "check" mode, so a syntax error is raised before any state changes.
  2. Cycle check. The new formula for cell reads refs. Writing it closes a cycle exactly when cell is already reachable from some ref by following deps (what a cell reads). One DFS over the upstream graph answers that. A self reference (A1 = A1 + 1) is the one-node case. If a cycle is found, raise and leave the old formula, edges and values untouched.
  3. Rewire edges. Remove cell from the dependents of its old refs, record the new refs, and add cell to each new ref's dependents.
  4. Propagate. Collect cell plus every cell downstream of it with a DFS over dependents, and recompute them in reverse post-order, which is a topological order of that subgraph. Each affected cell is evaluated exactly once, after all of its inputs, so diamonds come out right and no cell sees a stale input.

Invariants after every successful set_cell:

  • The deps graph is acyclic.
  • dependents is exactly the reverse of deps.
  • For every cell, values[cell] equals its formula evaluated on the current values of its refs. Unset cells read as 0.0.

The parser is a small recursive-descent grammar (expr := term (+|- term)*, term := factor (*|/ factor)*, factor := number | ref | -factor | (expr)), which gives the usual precedence and left associativity without eval. Never use Python's eval on user input in an interview answer; say why if you are tempted.

Code

from __future__ import annotations

import re
from collections import defaultdict

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


def tokenize(text: str) -> list[str]:
    tokens = []
    for number, ref, op in TOKEN.findall(text.strip()):
        if op and op not in "+-*/()":
            raise ValueError(f"bad character {op!r}")
        if ref:
            check_address(ref)
        tokens.append(number or ref or op)
    return tokens


def check_address(cell: str) -> None:
    if not re.fullmatch(r"[A-Z](?:[1-9]\d?|100)", cell):
        raise ValueError(f"bad cell address {cell!r}")


class Spreadsheet:
    def __init__(self) -> None:
        self.tokens: dict[str, list[str]] = {}            # cell -> formula tokens
        self.values: dict[str, float] = {}                # cached results
        self.deps: dict[str, set[str]] = defaultdict(set)        # cell -> cells it reads
        self.dependents: dict[str, set[str]] = defaultdict(set)  # cell -> cells that read it

    def set_cell(self, cell: str, raw: str) -> None:
        check_address(cell)
        tokens = tokenize(raw[1:]) if raw.startswith("=") else tokenize(raw)
        refs = {t for t in tokens if t[0].isalpha()}
        self._evaluate(tokens, check_only=True)          # syntax check before mutating
        if self._reaches(refs, cell):
            raise ValueError(f"circular reference through {cell}")
        for old in self.deps[cell]:
            self.dependents[old].discard(cell)
        self.deps[cell] = refs
        for ref in refs:
            self.dependents[ref].add(cell)
        self.tokens[cell] = tokens
        self._propagate(cell)

    def get_cell(self, cell: str) -> float:
        return self.values.get(cell, 0.0)

    def _reaches(self, starts: set[str], target: str) -> bool:
        """True if target is reachable from starts by following deps (would form a cycle)."""
        stack, seen = list(starts), set()
        while stack:
            node = stack.pop()
            if node == target:
                return True
            if node not in seen:
                seen.add(node)
                stack.extend(self.deps[node])
        return False

    def _propagate(self, cell: str) -> None:
        """Recompute cell and everything downstream, each once, in topological order."""
        order, seen = [], {cell}
        stack = [(cell, iter(self.dependents[cell]))]
        while stack:                      # iterative DFS post-order (chains can be 2,600 long)
            node, children = stack[-1]
            nxt = next((c for c in children if c not in seen), None)
            if nxt is None:
                order.append(node)
                stack.pop()
            else:
                seen.add(nxt)
                stack.append((nxt, iter(self.dependents[nxt])))
        for node in reversed(order):
            self.values[node] = self._evaluate(self.tokens[node])

    def _evaluate(self, tokens: list[str], check_only: bool = False) -> float:
        pos = 0

        def peek() -> str | None:
            return tokens[pos] if pos < len(tokens) else None

        def take() -> str:
            nonlocal pos
            if pos >= len(tokens):
                raise ValueError("unexpected end of formula")
            pos += 1
            return tokens[pos - 1]

        def expr() -> float:                  # expr := term (('+'|'-') term)*
            value = term()
            while peek() in ("+", "-"):
                value = value + term() if take() == "+" else value - term()
            return value

        def term() -> float:                  # term := factor (('*'|'/') factor)*
            value = factor()
            while peek() in ("*", "/"):
                op, rhs = take(), factor()
                value = value * rhs if op == "*" else (value / rhs if not check_only else 0.0)
            return value

        def factor() -> float:                # factor := number | ref | '-' factor | '(' expr ')'
            tok = take()
            if tok == "-":
                return -factor()
            if tok == "(":
                value = expr()
                if take() != ")":
                    raise ValueError("expected )")
                return value
            if tok[0].isalpha():
                return 0.0 if check_only else self.values.get(tok, 0.0)
            if tok[0].isdigit() or tok[0] == ".":
                return float(tok)
            raise ValueError(f"unexpected token {tok!r}")

        result = expr()
        if pos != len(tokens):
            raise ValueError(f"unexpected token {tokens[pos]!r}")
        return result

Complexity

Let V be the number of non-empty cells (at most 2,600), L the formula length, and k the number of refs in the new formula.

  • get_cell: O(1) time, O(1) space. It reads the cached value.
  • set_cell: O(L) to tokenize and syntax check. The cycle check is O(size of the upstream subgraph of the refs) and propagation is O(sum of formula lengths of the affected downstream cells). Both are bounded by O(V + E + total formula length), and in a typical sheet they touch only a few cells. Space is O(V) for the DFS stacks and visited sets.
  • Storage: O(V + E + total formula length) for tokens, both edge maps and cached values.
  • The lazy brute force is the reverse: set_cell O(L), get_cell O(upstream subgraph) per call, or worse without memoisation, because shared inputs are recomputed.

Test cases

  • New sheet: get_cell("Z100") returns 0.0.
  • set_cell("A1", "5"), set_cell("B1", "=A1*2+1"), set_cell("C1", "=B1+A1"): B1 = 11, C1 = 16.
  • Then set_cell("A1", "10"): B1 = 21, C1 = 31 (a change propagates two levels).
  • Precedence, parentheses and unary minus: D1 = "=(A1 - 4) / 3 * -2" with A1 = 10 gives -4.0.
  • Forward reference: E1 = "=F1+1" while F1 is empty gives 1.0. Then F1 = "2.5" makes E1 = 3.5.
  • Indirect cycle: with C1 = B1 + A1 and B1 reading A1, set_cell("A1", "=C1+1") raises, and A1, B1, C1 keep their old values.
  • Self cycle: set_cell("G1", "=G1") raises and G1 stays 0.0.
  • Syntax error: "=(A1+" raises with no state change. So do "=A1 % 2", "=AA1", "=A101" and "=A0".
  • Rewiring removes old edges: if C1 was =B1+A1 and becomes the constant 7, then A1 = "=C1+1" is legal (no cycle anymore) and gives 8.0.
  • Diamond: A1 = 1, B1 = A1+1, C1 = A1*10, D1 = B1+C1. Changing A1 to 2 makes D1 = 23, and D1 is recomputed once.
  • Longest chain: all 2,600 cells chained X = prev + 1 from A1 = 1 gives Z100 = 2600. Changing A1 updates the whole chain without hitting Python's recursion limit, and A1 = "=Z100" is rejected as a cycle.

Follow-ups

  • Ranges and functions (SUM(A1:B3), MIN, AVG). Add an identifier token and a call rule to factor. A range expands to its cells when you collect refs, so the graph is unchanged. With large ranges, store the range itself as one edge in an interval index, so that a 10,000-cell SUM does not create 10,000 edges, and look up "which ranges cover this cell" on write.
  • Error values instead of exceptions. Real spreadsheets store #DIV/0!, #REF! and #CYCLE! in the cell and keep going. Make a value either a float or an error, let errors flow through arithmetic, and accept a cyclic formula by marking every cell in the strongly connected component as #CYCLE! (Tarjan's algorithm on the affected subgraph). This also makes division by zero safe, which the base version assumes never happens.
  • Write-heavy sheets or many writes in a batch. Switch to lazy evaluation with dirty flags: a write marks the downstream cells dirty (or bumps a version), and get_cell recomputes only dirty cells it actually needs, memoising as it goes. For a batch paste, apply all edges first, then do one topological recompute (Kahn's algorithm over the union of affected cells), not one per write.
  • Undo / redo. Record each successful set_cell as (cell, old raw content, new raw content) on a stack. Undo replays the old content through set_cell. It cannot create a cycle, because that exact graph was valid before.
  • Concurrency or a very large sheet. Recompute independent branches of the affected subgraph in parallel by topological level, and keep reads lock-free by publishing a new value map (copy-on-write or versioned values) once a recompute finishes, so readers never see a half-updated sheet.

Interviewer expectations

Mid-level (L4)

  • Gets a correct lazy get_cell with recursive evaluation and a "currently visiting" set for cycle detection.
  • Parses + - * / with correct precedence, or clearly scopes the formula language with the interviewer first.
  • Tests a forward reference, a self reference and a two-cell cycle.

Senior (L5)

  • Moves to cached values with reverse edges, so that get_cell is O(1), and explains the read-heavy trade-off.
  • Rejects a cycle before mutating anything, removes stale edges on overwrite, and recomputes in topological order so diamonds evaluate once and correctly.
  • Writes a real parser instead of eval, and avoids recursion depth issues on long chains or at least names them.

Staff (L6+)

  • Frames lazy versus eager versus dirty-flag evaluation by read/write ratio and batch size, and picks one with numbers.
  • Handles ranges without an edge explosion, error values instead of exceptions, and SCC-based cycle marking.
  • Discusses undo, batch edits, and concurrent readers seeing a consistent snapshot, and how each one changes the data structures.

Sign in to comment, vote or remix.