Design Spreadsheet

Free with account Updated Nov 19, 2026 · 9 min read
On this page

    Problem statement

    Build a small spreadsheet engine. Cells are named like A1 or C7. set(cell, text) stores either a number ("12") or a formula that adds cells and numbers ("=A1+B1+5"). get(cell) returns the cell's current value; an empty cell is 0. When a cell changes, every formula that depends on it, directly or through other formulas, must show the new value. A set that would make a cell depend on itself is rejected and changes nothing.

    This is a favourite "machine coding" round: it starts as string parsing and quickly becomes a graph problem. Interviewers usually run it in levels: values first, then formulas, then updates that ripple through dependents, then cycle detection. The plain one-level version is LeetCode 3484; the dependency levels below are what makes it a real interview question.

    Example

    C1 adds A1 and B1, D1 adds C1 and A1; changing A1 from 5 to 10 must update both formulas.
    C1 adds A1 and B1, D1 adds C1 and A1; changing A1 from 5 to 10 must update both formulas.
    set("A1", "5");  set("B1", "7")
    set("C1", "=A1+B1")      get("C1") -> 12
    set("D1", "=C1+A1")      get("D1") -> 17
    set("A1", "10")          get("C1") -> 17, get("D1") -> 27
    set("C1", "=D1")         rejected: C1 -> D1 -> C1 is a cycle
    get("Z9")                -> 0      # never set

    Constraints (assumed)

    • Up to 10⁴ cells and 10⁴ operations; a formula mentions at most a few dozen cells.
    • Formulas use only + of cell names and integers (other operators are a follow-up).
    • Reads are much more frequent than writes.

    What this question tests

    • Seeing the cells as a directed graph: an edge from A1 to C1 means "C1 reads A1".
    • Updating dependents in topological order, so each cell is recomputed after everything it reads.
    • Cycle detection before a write is committed, and clean class design you can extend level by level.

    Questions to ask first

    1. What can a formula contain? (Here: cell names and integers joined by +.)
    2. What does an empty or never-set cell count as? (Here: 0.)
    3. What should happen on a cycle? Reject the write, or store it and show an error value? (Here: reject, nothing changes.)
    4. Reads or writes, which are more frequent? That decides between computing on read and computing on write.