LOW LEVEL DESIGN · MACHINE CODING · HARD · 35 OF 42

Design a Spreadsheet with Formulas: LLD in Java

A spreadsheet engine designed and coded: cells holding numbers, text or formulas like =A1+B2*2 and =SUM(A1:A3), a recursive descent parser that builds expression trees (Interpreter), a two-way dependency graph, recalculating only affected cells in topological order, cycle detection with a clear path, error values, undo and redo with Command, and the follow-ups, with full Java 17 code.

Reported atArcesium

Patterns usedInterpreterStrategyCommand

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
1 / 20

Press play to hear the narration, or step through at your own pace. The full Java code is below.

Full Java solution

One file, Java 17, 554 lines, with a small main() demo. Save it as Spreadsheet.java, then run javac Spreadsheet.java && java Spreadsheet.

import java.math.BigDecimal;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

/**
 * A spreadsheet with formulas: cells hold numbers, text or formulas such as =A1+B2*2 or =SUM(A1:A3).
 * Formulas are parsed into expression trees (Interpreter), a dependency graph recalculates only the
 * affected cells in topological order, cycles are rejected before anything changes, and every edit
 * is a command that can be undone and redone.
 */
public final class Spreadsheet {

    // ---------- cell addresses ----------
    /** "b12" becomes "B12"; columns are letters (A..Z, AA..), rows start at 1. */
    static String normalise(String address) {
        String a = address.trim().toUpperCase();
        if (!a.matches("[A-Z]{1,3}[1-9][0-9]{0,5}"))
            throw new IllegalArgumentException("bad cell " + address);
        return a;
    }

    static int columnIndex(String letters) {
        int n = 0;
        for (char c : letters.toCharArray()) n = n * 26 + (c - 'A' + 1);
        return n;
    }

    static String columnLetters(int index) {
        StringBuilder sb = new StringBuilder();
        for (int n = index; n > 0; n = (n - 1) / 26) sb.insert(0, (char) ('A' + (n - 1) % 26));
        return sb.toString();
    }

    /** A1:B3 expands to A1, B1, A2, B2, A3, B3 (row by row). */
    static List<String> expandRange(String from, String to) {
        int c1 = columnIndex(from.replaceAll("[0-9]", "")), c2 = columnIndex(to.replaceAll("[0-9]", ""));
        int r1 = Integer.parseInt(from.replaceAll("[A-Z]", ""));
        int r2 = Integer.parseInt(to.replaceAll("[A-Z]", ""));
        if ((long) (Math.abs(c2 - c1) + 1) * (Math.abs(r2 - r1) + 1) > 10_000)
            throw new IllegalArgumentException("range too large");
        List<String> out = new ArrayList<>();
        for (int r = Math.min(r1, r2); r <= Math.max(r1, r2); r++)
            for (int c = Math.min(c1, c2); c <= Math.max(c1, c2); c++) out.add(columnLetters(c) + r);
        return out;
    }

    // ---------- errors ----------
    /** An evaluation error shown in the cell, like #DIV/0!; it flows to every cell that reads it. */
    static final class FormulaError extends RuntimeException {
        private static final long serialVersionUID = 1L;

        FormulaError(String code) { super(code); }
    }

    /** Thrown when an edit would create a cycle. The sheet is left exactly as it was. */
    static final class CycleException extends RuntimeException {
        private static final long serialVersionUID = 1L;

        CycleException(List<String> path) { super("cycle: " + String.join(" -> ", path)); }
    }

    // ---------- Interpreter: formulas as expression trees ----------
    /** How an expression reads other cells while it evaluates. */
    interface Values {
        double of(String cell);
    }

    interface Expr {
        double eval(Values values);

        void collectRefs(Set<String> out);
    }

    record Num(double value) implements Expr {
        @Override
        public double eval(Values values) { return value; }

        @Override
        public void collectRefs(Set<String> out) {}
    }

    record Ref(String cell) implements Expr {
        @Override
        public double eval(Values values) { return values.of(cell); }

        @Override
        public void collectRefs(Set<String> out) { out.add(cell); }
    }

    record Neg(Expr inner) implements Expr {
        @Override
        public double eval(Values values) { return -inner.eval(values); }

        @Override
        public void collectRefs(Set<String> out) { inner.collectRefs(out); }
    }

    record Binary(char op, Expr left, Expr right) implements Expr {
        @Override
        public double eval(Values values) {
            double l = left.eval(values), r = right.eval(values);
            return switch (op) {
                case '+' -> l + r;
                case '-' -> l - r;
                case '*' -> l * r;
                case '/' -> {
                    if (r == 0) throw new FormulaError("#DIV/0!");
                    yield l / r;
                }
                default -> throw new IllegalStateException("unknown operator " + op);
            };
        }

        @Override
        public void collectRefs(Set<String> out) {
            left.collectRefs(out);
            right.collectRefs(out);
        }
    }

    /** SUM over a list of arguments; a range argument has already been expanded into cell refs. */
    record Sum(List<Expr> args) implements Expr {
        @Override
        public double eval(Values values) {
            double total = 0;
            for (Expr e : args) total += e.eval(values);
            return total;
        }

        @Override
        public void collectRefs(Set<String> out) { for (Expr e : args) e.collectRefs(out); }
    }

    /**
     * Recursive descent parser. Grammar:
     *   expr   = term (('+' | '-') term)*
     *   term   = factor (('*' | '/') factor)*
     *   factor = number | cell | SUM '(' arg (',' arg)* ')' | '(' expr ')' | '-' factor
     *   arg    = cell ':' cell | expr
     */
    static final class Parser {
        private final String s;
        private int pos;

        Parser(String text) { this.s = text; }

        Expr parse() {
            Expr e = expr();
            skipSpaces();
            if (pos != s.length()) throw error("unexpected '" + s.charAt(pos) + "'");
            return e;
        }

        private Expr expr() {
            Expr e = term();
            while (peek('+') || peek('-')) {
                char op = s.charAt(pos++);
                e = new Binary(op, e, term());
            }
            return e;
        }

        private Expr term() {
            Expr e = factor();
            while (peek('*') || peek('/')) {
                char op = s.charAt(pos++);
                e = new Binary(op, e, factor());
            }
            return e;
        }

        private Expr factor() {
            skipSpaces();
            if (pos >= s.length()) throw error("formula ends too early");
            char c = s.charAt(pos);
            if (c == '-') {
                pos++;
                return new Neg(factor());
            }
            if (c == '(') {
                pos++;
                Expr e = expr();
                expect(')');
                return e;
            }
            if (Character.isDigit(c) || c == '.') return number();
            if (Character.isLetter(c)) {
                String word = word();
                if (word.equals("SUM")) return sum();
                return new Ref(normalise(word));
            }
            throw error("unexpected '" + c + "'");
        }

        private Expr sum() {
            expect('(');
            List<Expr> args = new ArrayList<>();
            do {
                skipSpaces();
                int start = pos;
                String first = Character.isLetter(peekChar()) ? word() : null;
                if (first != null && peek(':')) {
                    pos++;
                    skipSpaces();
                    String last = word();
                    for (String cell : expandRange(normalise(first), normalise(last)))
                        args.add(new Ref(cell));
                } else {
                    pos = start; // not a range: parse it again as a normal expression
                    args.add(expr());
                }
            } while (consume(','));
            expect(')');
            return new Sum(args);
        }

        private Expr number() {
            int start = pos;
            while (pos < s.length() && (Character.isDigit(s.charAt(pos)) || s.charAt(pos) == '.')) pos++;
            try {
                return new Num(Double.parseDouble(s.substring(start, pos)));
            } catch (NumberFormatException e) {
                throw error("bad number");
            }
        }

        private String word() {
            int start = pos;
            while (pos < s.length() && Character.isLetterOrDigit(s.charAt(pos))) pos++;
            return s.substring(start, pos).toUpperCase();
        }

        private char peekChar() { return pos < s.length() ? s.charAt(pos) : '\0'; }

        private boolean peek(char c) {
            skipSpaces();
            return pos < s.length() && s.charAt(pos) == c;
        }

        private boolean consume(char c) {
            if (!peek(c)) return false;
            pos++;
            return true;
        }

        private void expect(char c) { if (!consume(c)) throw error("expected '" + c + "'"); }

        private void skipSpaces() { while (pos < s.length() && s.charAt(pos) == ' ') pos++; }

        private IllegalArgumentException error(String msg) {
            return new IllegalArgumentException("bad formula =" + s + ": " + msg + " at position " + pos);
        }
    }

    // ---------- cells ----------
    /** What the user typed, plus what we computed from it. */
    static final class Cell {
        final String input; // "1200", "Rent" or "=SUM(B1:B3)"
        final Expr expr;    // null for text
        double value;
        String error;       // "#DIV/0!", "#VALUE!" or null

        Cell(String input, Expr expr) {
            this.input = input;
            this.expr = expr;
        }

        boolean isText() { return expr == null; }
    }

    // ---------- dependency graph ----------
    /** Edges both ways: what a cell reads (precedents) and who reads it (dependents). */
    static final class DependencyGraph {
        private final Map<String, Set<String>> reads = new HashMap<>();
        private final Map<String, Set<String>> readBy = new HashMap<>();

        Set<String> readersOf(String cell) { return readBy.getOrDefault(cell, Set.of()); }

        /** If cell started reading 'newReads', would a path lead back to cell? Returns that path or null. */
        List<String> findCycle(String cell, Set<String> newReads) {
            Set<String> seen = new HashSet<>();
            for (String r : newReads) {
                Deque<String> path = new ArrayDeque<>();
                if (reaches(r, cell, seen, path)) {
                    List<String> out = new ArrayList<>();
                    out.add(cell);
                    out.addAll(path);
                    return out;
                }
            }
            return null;
        }

        private boolean reaches(String from, String target, Set<String> seen, Deque<String> path) {
            path.addLast(from);
            if (from.equals(target)) return true;
            if (seen.add(from))
                for (String next : reads.getOrDefault(from, Set.of()))
                    if (reaches(next, target, seen, path)) return true;
            path.removeLast();
            return false;
        }

        void setReads(String cell, Set<String> newReads) {
            for (String old : reads.getOrDefault(cell, Set.of())) {
                Set<String> by = readBy.get(old);
                by.remove(cell);
                if (by.isEmpty()) readBy.remove(old);
            }
            if (newReads.isEmpty()) reads.remove(cell);
            else reads.put(cell, new LinkedHashSet<>(newReads));
            for (String r : newReads) readBy.computeIfAbsent(r, k -> new LinkedHashSet<>()).add(cell);
        }

        /** The changed cell and everything downstream of it, each once, every cell after what it reads. */
        List<String> recalcOrder(String changed) {
            Set<String> affected = new LinkedHashSet<>();
            Deque<String> todo = new ArrayDeque<>(List.of(changed));
            while (!todo.isEmpty()) {
                String c = todo.poll();
                if (affected.add(c)) todo.addAll(readersOf(c));
            }
            // Topological sort by counting unmet inputs, only inside the affected set.
            Map<String, Integer> waiting = new HashMap<>();
            for (String c : affected) {
                int n = 0;
                for (String r : reads.getOrDefault(c, Set.of())) if (affected.contains(r)) n++;
                waiting.put(c, n);
            }
            List<String> order = new ArrayList<>();
            Deque<String> ready = new ArrayDeque<>(List.of(changed));
            while (!ready.isEmpty()) {
                String c = ready.poll();
                order.add(c);
                for (String d : readersOf(c))
                    if (waiting.merge(d, -1, Integer::sum) == 0) ready.add(d);
            }
            return order; // the graph has no cycles, so every affected cell is here
        }
    }

    // ---------- Command: every edit can be undone ----------
    interface Command {
        void execute();

        void undo();
    }

    /** Remembers the previous input of the cell, so undo just types it back in. */
    final class SetCellCommand implements Command {
        final String cell;
        final String before;
        final String after;

        SetCellCommand(String cell, String after) {
            this.cell = cell;
            Cell old = cells.get(cell);
            this.before = old == null ? "" : old.input;
            this.after = after;
        }

        @Override
        public void execute() { apply(cell, after); }

        @Override
        public void undo() { apply(cell, before); } // the sheet was valid then, so this cannot form a cycle
    }

    // ---------- the sheet ----------
    private final Map<String, Cell> cells = new HashMap<>();
    private final DependencyGraph graph = new DependencyGraph();
    private final Deque<Command> undoStack = new ArrayDeque<>();
    private final Deque<Command> redoStack = new ArrayDeque<>();
    private List<String> lastRecalc = List.of();

    /** Type into a cell: a number, text, a formula starting with '=', or "" to clear it. */
    synchronized void set(String address, String input) {
        Command cmd = new SetCellCommand(normalise(address), input == null ? "" : input.trim());
        cmd.execute(); // throws on a bad formula or a cycle, and then changes nothing
        undoStack.push(cmd);
        redoStack.clear();
    }

    synchronized boolean undo() {
        Command cmd = undoStack.poll();
        if (cmd == null) return false;
        cmd.undo();
        redoStack.push(cmd);
        return true;
    }

    synchronized boolean redo() {
        Command cmd = redoStack.poll();
        if (cmd == null) return false;
        cmd.execute();
        undoStack.push(cmd);
        return true;
    }

    /** The heart of it: parse, reject cycles, rewire the graph, store, then recalculate downstream. */
    private void apply(String cell, String input) {
        Expr expr = null;
        Set<String> reads = new LinkedHashSet<>();
        if (input.startsWith("=")) {
            expr = new Parser(input.substring(1)).parse();
            expr.collectRefs(reads);
        } else if (input.matches("-?[0-9]+(\\.[0-9]+)?")) {
            expr = new Num(Double.parseDouble(input));
        }
        List<String> cycle = graph.findCycle(cell, reads); // check before touching anything
        if (cycle != null) throw new CycleException(cycle);

        graph.setReads(cell, reads);
        if (input.isEmpty()) cells.remove(cell);
        else cells.put(cell, new Cell(input, expr));
        lastRecalc = graph.recalcOrder(cell);
        for (String c : lastRecalc) evaluate(c);
    }

    private void evaluate(String address) {
        Cell c = cells.get(address);
        if (c == null || c.isText()) return;
        try {
            c.value = c.expr.eval(this::read);
            c.error = null;
        } catch (FormulaError e) {
            c.value = 0;
            c.error = e.getMessage();
        }
    }

    /** How a formula sees another cell: empty is 0, text is #VALUE!, and errors pass straight through. */
    private double read(String address) {
        Cell c = cells.get(address);
        if (c == null) return 0;
        if (c.isText()) throw new FormulaError("#VALUE!");
        if (c.error != null) throw new FormulaError(c.error);
        return c.value;
    }

    synchronized String display(String address) {
        Cell c = cells.get(normalise(address));
        if (c == null) return "";
        if (c.isText()) return c.input;
        if (c.error != null) return c.error;
        return BigDecimal.valueOf(c.value).stripTrailingZeros().toPlainString();
    }

    synchronized List<String> lastRecalc() { return lastRecalc; }

    // ---------- demo ----------
    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    static void expectRejected(Spreadsheet s, String cell, String input) {
        try {
            s.set(cell, input);
            throw new AssertionError("should reject " + input);
        } catch (IllegalArgumentException | CycleException e) {
            System.out.println("Rejected " + cell + " " + input + " -> " + e.getMessage());
        }
    }

    String show(String... addresses) {
        List<String> parts = new ArrayList<>();
        for (String a : addresses) parts.add(a + "=" + display(a));
        return String.join(", ", parts);
    }

    public static void main(String[] args) throws Exception {
        Spreadsheet s = new Spreadsheet();
        s.set("A1", "Rent");
        s.set("B1", "1200");
        s.set("A2", "Food");
        s.set("B2", "300");
        s.set("A3", "Travel");
        s.set("B3", "150");
        s.set("B4", "=SUM(B1:B3)");
        s.set("B5", "=B4 * 12");
        s.set("C4", "=B4 / 3");
        System.out.println("Budget: " + s.show("B4", "B5", "C4"));
        s.set("B2", "450");
        System.out.println("Food to 450, recalculated " + s.lastRecalc() + ": " + s.show("B4", "B5", "C4"));
        check(s.display("B5").equals("21600") && s.lastRecalc().equals(List.of("B2", "B4", "B5", "C4")),
                "recalc");

        // A diamond: G1 reads E1 and F1, and F1 reads E1. G1 must wait for F1.
        s.set("E1", "2");
        s.set("F1", "=E1*10");
        s.set("G1", "=E1+F1");
        s.set("H1", "=F1 + G1*2");
        s.set("E1", "3");
        System.out.println("E1 to 3, order " + s.lastRecalc() + ": " + s.show("F1", "G1", "H1"));
        check(s.lastRecalc().equals(List.of("E1", "F1", "G1", "H1")) && s.display("H1").equals("96"), "topo");

        s.set("I1", "=(B1 - 200) / 4 + -E1");
        s.set("I2", "=SUM(B1, B3:B3, 50)");
        System.out.println("Precedence and SUM args: " + s.show("I1", "I2"));
        check(s.display("I1").equals("247") && s.display("I2").equals("1400"), "parser");

        expectRejected(s, "B1", "=B5/12");
        expectRejected(s, "J1", "=J1+1");
        expectRejected(s, "J1", "=B1+*2");
        check(s.display("B1").equals("1200") && s.display("J1").isEmpty(), "rejected edits change nothing");

        s.set("D1", "=B1/(E1-3)");
        s.set("D2", "=D1+1");
        s.set("D3", "=A1*2");
        System.out.println("Errors: " + s.show("D1", "D2", "D3"));
        s.set("E1", "4");
        System.out.println("E1 to 4 fixes them: " + s.show("D1", "D2"));
        check(s.display("D2").equals("1201"), "errors clear on recalc");
        s.undo();
        System.out.println("Undo: " + s.show("E1", "D1", "D2"));
        s.redo();
        System.out.println("Redo: " + s.show("E1", "D1", "D2"));

        s.set("B4", "0"); // overwrite the formula with a constant
        System.out.println("B4 typed over: " + s.show("B4", "B5"));
        s.undo();
        System.out.println("Undo restores the formula: " + s.show("B4", "B5"));
        check(s.display("B5").equals("21600"), "undo restores a formula and its dependents");

        // A chain of 1000 cells: K1, then K2 = K1 + 1, and so on. One change ripples through all of them.
        s.set("K1", "1");
        for (int r = 2; r <= 1000; r++) s.set("K" + r, "=K" + (r - 1) + "+1");
        s.set("K1", "5");
        System.out.println("Chain: K1 to 5 recalculated " + s.lastRecalc().size() + " cells, K1000="
                + s.display("K1000"));
        check(s.display("K1000").equals("1004"), "chain");

        // Edits from several threads are serialised by the sheet's lock; the total is always exact.
        s.set("L5", "=SUM(L1:L4)");
        ExecutorService pool = Executors.newFixedThreadPool(4);
        List<Future<?>> jobs = new ArrayList<>();
        for (int t = 1; t <= 4; t++) {
            String cell = "L" + t;
            jobs.add(pool.submit(() -> { for (int v = 1; v <= 500; v++) s.set(cell, String.valueOf(v)); }));
        }
        for (Future<?> f : jobs) f.get();
        pool.shutdown();
        System.out.println("Concurrent edits: " + s.show("L1", "L2", "L3", "L4", "L5"));
        check(s.display("L5").equals("2000"), "concurrent edits");
    }
}

Notes

Requirements

Fix the scope. Set a cell to a number, some text, or a formula that starts with an equals sign. Formulas support plus, minus, times, divide, brackets, unary minus and a SUM function over ranges or a list of arguments. When a cell changes, everything that depends on it updates. A cycle is rejected with a clear message. Division by zero and maths on text show error values. And every edit can be undone and redone.

Ask the questions that shape the code. An empty cell in a formula counts as zero. When an edit would create a cycle, do we store an error in the cell or reject the edit? We reject it and leave the sheet unchanged, which is simpler to reason about. Bad syntax is also rejected, with the position. If a cell I read has an error, I show that error too. More functions, copy and paste, formatting and live collaboration are out of scope for now.

Requirements
  • set(cell, input)
  • number, text, or a formula
  • formula starts with =
  • operators: + - * / and ( )
  • SUM(A1:A3) and SUM(a, b, c)
  • change a cell: dependents update
  • cycles rejected with a message
  • errors: #DIV/0!, #VALUE!
  • undo and redo every edit
  • display(cell) shows the value
Clarify first
  • empty cell in a formula?
  • counts as zero
  • cycle: store an error or reject?
  • reject, sheet unchanged
  • bad syntax like =B1+*2?
  • reject with the position
  • error in a cell I read?
  • it flows to me too
  • out of scope: more functions,
  • copy paste, formatting,
  • multi-user editing

Entities

The entities. The spreadsheet holds cells by address. A cell keeps what the user typed, an expression tree built from it, the computed value and an error if there is one. The parser turns formula text into that tree. A dependency graph knows which cells read which. And every edit is a command object, so it can be undone. Notice the split: parsing, the graph and history are separate classes, and the sheet just wires them together.

Class diagram

A cell stores the raw input exactly as typed, because that is what we show when editing and what undo puts back. A plain number becomes a tiny number expression, so numbers and formulas are evaluated the same way. Text has no expression. The value and the error are results, recomputed whenever needed. Storing the input as the source of truth means everything else can always be rebuilt from it.

Cell
final class Cell {
  final String input;  // "=SUM(B1:B3)"
  final Expr expr;     // null for text
  double value;
  String error;        // "#DIV/0!" or null
}

"1200"   -> Num(1200)
"Rent"   -> text, expr null
"=B4*12" -> Binary(*, Ref B4, Num 12)

Interpreter pattern

This is the Interpreter pattern. Each kind of piece in the formula language is a small class with one method to evaluate itself: a number, a cell reference, a unary minus, a binary operator, and SUM. A formula is a tree of these. The tree has a second job too: collect refs walks it and returns every cell the formula reads, and that list becomes the edges in the dependency graph. One tree gives both the value and the dependencies.

Expr
interface Expr {
  double eval(Values values);
  void collectRefs(Set<String> out);
}
record Num(double value)
record Ref(String cell)
record Neg(Expr inner)
record Binary(char op, Expr l, Expr r)
record Sum(List<Expr> args)

=B4*12  is  Binary(*, Ref(B4), Num(12))

The parser

The parser is recursive descent, one method per grammar rule. An expression is terms joined by plus or minus. A term is factors joined by times or divide. A factor is a number, a cell, a minus sign before a factor, something in brackets, or a SUM call. Because times lives one level deeper than plus, A1 plus B2 times two groups the multiplication first, with no precedence table at all. Inside SUM, a range like B1 to B3 expands into three cell references.

Grammar
expr   = term   ((+ | -) term)*
term   = factor ((* | /) factor)*
factor = number | cell | -factor
       | ( expr )
       | SUM ( arg (, arg)* )
arg    = cell : cell | expr

=A1+B2*2:
  Binary(+, A1, Binary(*, B2, 2))

Dependency graph

The dependency graph keeps edges in both directions. Reads maps a cell to the cells its formula uses. Read by is the reverse, mapping a cell to the formulas that use it. We need reads to detect cycles and to count inputs, and read by to find what must update after a change. When a cell gets a new formula, set reads removes its old edges from both maps and adds the new ones, so the two maps never disagree.

Two maps
Map<String, Set<String>> reads;
Map<String, Set<String>> readBy;

B4 = SUM(B1:B3)
  reads:  B4 -> {B1, B2, B3}
  readBy: B1 -> {B4}, B2 -> {B4} ...
B5 = B4*12:  readBy B4 -> {B5, C4}

setReads(cell, refs): drop old
  edges, add the new ones

Cycle detection

Cycle detection happens before anything changes. Before giving a cell new inputs, search from each new input along the reads edges. If the search reaches the cell itself, the edit would close a loop. Setting B1 to B5 divided by twelve fails, because B5 reads B4 and B4 reads B1. The error spells out the whole path, so the user can see where the loop is. A cell that reads itself is the shortest cycle of all.

findCycle(cell, newReads)
for (String r : newReads)
  depth-first search along reads
  if we reach cell: cycle found

B1 = B5/12
  B5 reads B4, B4 reads B1
  -> cycle: B1 -> B5 -> B4 -> B1
J1 = J1+1 -> cycle: J1 -> J1

checked BEFORE any change

Topological recalc

Recalculation has two steps. First, walk the read by edges from the changed cell to find every affected cell; the rest of the sheet is untouched. Second, sort those cells topologically: count how many of each cell's inputs are also affected, start with the changed cell, and when a cell is done, lower the count of its readers. A reader is ready when its count hits zero. Every cell is evaluated once, and always after its inputs.

Why not simply recompute every reader as you find it? Look at the diamond in the demo. G1 reads both E1 and F1, and F1 reads E1. A naive walk might update G1 straight after E1, using the old value of F1, then update it again later. In a big sheet that repeated work explodes, and a careless version can even leave a stale value. Topological order fixes both problems: G1 simply waits until F1 is done.

recalcOrder(changed)
1. affected = changed + everything
   reachable through readBy
2. count inputs inside affected
3. start with changed; when a cell
   is done, lower its readers count;
   at zero they are ready

F1=E1*10  G1=E1+F1  H1=F1+G1*2
E1 changes -> E1, F1, G1, H1
each cell evaluated exactly once
Why not just follow readers?
  • G1 reads E1 and F1
  • F1 reads E1
  • naive depth-first from E1:
  • E1, G1 (uses OLD F1!), F1,
  • G1 again, ...
  • repeated or wrong work
  • topological: G1 waits for F1
  • correct, and each cell once

Error values

Some problems are not edit errors but value errors. Dividing by zero shows hash div zero in that cell. Doing maths on a text cell shows hash value. And a formula that reads a cell holding an error shows the same error, so the problem is visible everywhere it matters. These are stored on the cell, not thrown at the user, and they clear by themselves on the next recalculation once the input is fixed.

Errors are values
divide by zero -> #DIV/0!
formula reads text -> #VALUE!
reads a cell with an error
  -> same error passes through

D1 = B1/(E1-3)   E1 = 3 -> #DIV/0!
D2 = D1+1                -> #DIV/0!
E1 = 4  -> D1 = 1200, D2 = 1201
errors clear on the next recalc

Command: undo

Undo uses the Command pattern. Each edit becomes a set cell command that remembers the cell, the input before and the input after. Execute applies the new input; undo applies the old one through exactly the same path, so the graph and every dependent update automatically. Two stacks hold the history, and a fresh edit clears the redo stack. Undo can never form a cycle, because the sheet it returns to was valid before.

SetCellCommand
final String cell, before, after;
void execute() { apply(cell, after); }
void undo()    { apply(cell, before); }

set():  execute, push undo,
        clear redo
undo(): pop undo, cmd.undo(),
        push redo
redo(): pop redo, execute,
        push undo

Flow: set a cell

Put it together for one edit, food from three hundred to four hundred and fifty. Parse the input; a syntax error throws here, before any change. Collect the references and check for a cycle; that can also throw, still before any change. Only then rewire the graph and store the cell. Finally get the recalculation order, B2, then the total in B4, then the yearly total and the per person share, and evaluate each one. All validation comes first, so a failed edit leaves nothing half done.

apply(cell, input)
expr = input starts with "="
  ? new Parser(rest).parse()
  : number ? new Num(..) : null
reads = refs of expr
cycle = graph.findCycle(cell, reads)
if (cycle != null) throw
graph.setReads(cell, reads)
store or remove the Cell
for (c : graph.recalcOrder(cell))
  evaluate(c)

Concurrency

Concurrency. One edit can ripple through thousands of cells, and the order matters across all of them, so fine-grained locks per cell would be complex and easy to get wrong. Instead, every public method on the sheet is synchronized: edits are applied one at a time, and readers never see a half finished recalculation. The demo runs four threads making five hundred edits each, and the SUM always ends at exactly two thousand. Live collaboration is a different design: a server puts edits in one order.

Concurrency
  • one sheet, one lock:
  • set, undo, redo, display are
  • synchronized
  • why not finer locks? a recalc
  • touches many cells, and order
  • matters across all of them
  • demo: 4 threads x 500 edits
  • L5 = SUM(L1:L4) ends at 2000
  • collaboration: a server orders
  • edits, clients replay them

Extensibility

New features land in one layer each. More functions like minimum, maximum, average or if are new expression classes and one branch in the parser. Number formats are a strategy used only when displaying. The sheet is already sparse, since only filled cells are stored. Saving only needs the inputs, because values can always be recomputed. Copy and paste needs relative references that shift, with a marker for references that must stay fixed.

Extension points
  • MIN, MAX, AVG, IF: new Expr
  • classes, one parser branch
  • cell formats: a Format strategy
  • used only by display()
  • big sheets: sparse map, already
  • lazy recalc: mark dirty, compute
  • on read
  • save and load: store inputs only
  • copy paste: shift relative refs
  • ($A$1 stays fixed)

Testing

The full code is below the player. The demo builds a small monthly budget with labels, a SUM total, a yearly total and a share per person, then changes food and prints the recalculation order. It runs the diamond, checks operator precedence, rejects two cycles and a syntax error, shows both error values clearing, undoes and redoes, restores a formula that was typed over, ripples a change through a chain of a thousand cells, and runs the concurrent edits.

Run it
Food to 450, recalculated
  [B2, B4, B5, C4]: B5=21600
E1 to 3, order [E1, F1, G1, H1]
Rejected B1 =B5/12
  -> cycle: B1 -> B5 -> B4 -> B1
Errors: D1=#DIV/0!, D3=#VALUE!
B4 typed over: B4=0, B5=0
Undo restores the formula: B5=21600
Chain: 1000 cells, K1000=1004
Concurrent edits: L5=2000

Follow-ups

Expect follow-ups. With a million cells, only the affected part is recalculated, which is the whole point of the graph. Very long chains can overflow the call stack in a recursive search, so switch to an explicit stack. Functions like now or random are volatile and must recompute every time. Some spreadsheets allow intended cycles with a capped number of rounds. And cells at the same depth of the order can be evaluated in parallel.

Follow-ups to expect
  • a million cells, one changes?
  • only the affected part recalcs
  • deep chains: recursion depth
  • use an explicit stack
  • volatile functions like NOW()?
  • always dirty on recalc
  • cycle by design (iteration)?
  • opt in, cap the rounds
  • parallel recalc: cells at the
  • same depth run together

Say it like this

The short version to say out loud. A cell keeps its raw input and an expression tree built by a recursive descent parser, the Interpreter pattern. A dependency graph stores edges both ways. Every edit checks for a cycle before changing anything, then rewires the graph and recalculates only the affected cells, in topological order. Each edit is a command that remembers the old input, so undo just applies it again.

In the interview
  • "A cell keeps its input and an
  • Expr tree from a recursive
  • descent parser. A graph stores
  • reads and read-by edges. Edits
  • check for a cycle first, then
  • rewire and recalculate only the
  • affected cells in topological
  • order. Each edit is a Command
  • that remembers the old input."

Interview questions

How do you parse a formula like =A1+B2*2?

With a small recursive descent parser that has one method per grammar rule: expression, term and factor. Because multiplication is handled one level below addition, precedence comes out right without a table. The result is an expression tree, which is the Interpreter pattern.

Why build an expression tree instead of evaluating the text each time?

Parsing happens once per edit, while evaluation can happen many times as inputs change. The tree also lists every cell the formula reads, which you need to build the dependency graph. And each node type is a small class, so adding a function is a new class.

How do you know which cells to recalculate when one cell changes?

Keep reverse edges: for each cell, the set of cells whose formulas read it. Walk those edges from the changed cell to collect everything downstream. Only that affected set is recalculated; the rest of the sheet is left alone.

Why must recalculation follow topological order?

A cell must be evaluated after all of its inputs. In a diamond, where a cell reads two cells that both depend on the changed one, a naive walk can compute it too early with a stale input or compute it several times. Topological order evaluates each affected cell exactly once, after its inputs.

How do you detect a circular reference?

Before applying a new formula, run a depth-first search from each cell it would read, following the existing read edges. If the search reaches the cell being edited, the edit would close a loop, so reject it and report the path. Checking first means a rejected edit changes nothing.

How do you implement undo and redo?

Each edit is a command that stores the cell, the old input and the new input. Execute applies the new input and undo applies the old one through the same code path, so the graph and dependents update automatically. Two stacks hold history, and a new edit clears the redo stack.

How do errors like division by zero behave?

They are values stored on the cell, not exceptions shown to the user. A formula that reads a cell with an error shows the same error, so it flows downstream. When the input is fixed, the next recalculation clears the error.

How would you make recalculation fast for very large sheets?

Recalculate only the affected subgraph, which the dependency graph already gives you. Beyond that, evaluate cells at the same depth in parallel, mark cells dirty and compute them lazily when read, and use an explicit stack instead of recursion for very long chains.

How do you make the sheet safe with several threads?

A single lock around every public method is the simple, correct choice, because one edit can touch many cells and the order matters across all of them. For real-time collaboration, a server puts edits into one order and every client applies them in that order.