HardArrayHash TableStringGraphDesignUpdated Sep 2026

631. Design Excel Sum Formula

Asked at OpenAI, Rippling, Airbnb

Difficulty

Hard

Time

O(V + E) per set or sum, where V

Space

O(V + E)

Pattern

Array

Companies

3

Problem

Design a small spreadsheet, like a tiny Excel sheet. The sheet has height rows (numbered 1 to height) and width columns (named 'A' to the given letter). Every cell starts at 0.

You must support three operations. set(row, col, val) writes a plain number into a cell. get(row, col) reads the current value of a cell. sum(row, col, numbers) makes a cell equal to the total of other cells, and returns that total. Each entry in numbers is either one cell like "A1", or a rectangle like "A1:B3" meaning all cells from the top-left corner to the bottom-right corner.

The tricky part: a sum is a live formula, not a one-time copy. If cell C3 sums A1 and the range A1:B2, and later someone changes A1 or B2, then C3 must change too. A formula stays in place until that same cell is overwritten by a new number or a new sum. You may assume no circular references exist, so a cell never ends up depending on itself, directly or through other cells.

Return the value from sum right after you set it. set and get return nothing.

A sum is a live formula

sheetABC123200000004After set(1,A,2) and sum(3,C,[A1, A1:B2]): C3 = 2 + 0+ 0 + 0 = 4.sheetABC123200020006After set(2,B,2): B2 is now 2, so the live formula inC3 becomes 2 + 0 + 0 + 2 = 6.
C3 sums A1 and the block A1:B2. When B2 changes from 0 to 2, C3 must grow from 4 to 6.

Constraints

  • ●1 <= height <= 26
  • ●'A' <= width <= 'Z'
  • ●1 <= row <= height
  • ●'A' <= column <= width
  • ●-100 <= val <= 100
  • ●1 <= numbers.length <= 5
  • ●Each numbers[i] is "ColRow" or "ColRow1:ColRow2"
  • ●At most 100 calls total to set, get and sum

Examples

Example 1
Input["Excel", "set", "sum", "set", "get"] [[3, "C"], [1, "A", 2], [3, "C", ["A1", "A1:B2"]], [2, "B", 2], [3, "C"]]
Output[null, null, 4, null, 6]
WhyThe sheet is 3x3 and all zeros. set(1,"A",2) makes A1 = 2. Then C3 sums A1 plus the rectangle A1:B2. At that moment A1 is 2 and B1, A2, B2 are 0, so the total is 4. Later set(2,"B",2) makes B2 = 2, and because C3 is a live formula it updates to 2 + 2 + 0 + 2 = 6. get(3,"C") returns 6.
Example 2
Input["Excel", "sum", "set", "get"] [[2, "B"], [1, "A", ["A1:B2"]], [2, "B", 5], [1, "A"]]
Output[null, 0, null, 5]
WhyA1 sums the whole 2x2 block A1:B2, which is all zeros, so it returns 0. Then B2 is set to 5. A1 depends on B2, so A1 becomes 5. get(1,"A") returns 5.
Example 3
Input["Excel", "set", "sum", "set", "get"] [[3, "C"], [1, "A", 1], [1, "B", ["A1"]], [1, "A", 7], [1, "B"]]
Output[null, null, 1, null, 7]
WhyB1 is defined as the sum of A1, which is 1 at that time. After A1 is changed to 7, B1 is recomputed and becomes 7. get(1,"B") returns 7.

Asked At

3 companies
CompanyDifficulty
OpenAIHardView all OpenAI questions →
RipplingHardView all Rippling questions →
AirbnbHardView all Airbnb questions →

How to Think About It

1

The key challenge: unlike the spreadsheet problem, this one requires dependency tracking. When you set cell A1 = 5 and B1 = "=SUM(A1:A1)", changing A1 must update B1. You need a directed graph of dependencies.

2

Data structures:

  • grid[r][c]: stores the raw value (int or formula) of each cell.
  • deps[r][c]: set of cells that this cell depends on (its "parents").
  • dependents[r][c]: set of cells that depend on this cell (its "children").
    When A1 is used in B1's formula, A1 has B1 in its dependents, and B1 has A1 in its deps.
3

set(row, col, val): first, clear the old dependencies of this cell. Then, if val is a formula (starts with "="), parse the cell references and build the new dependency graph. After setting, BFS/DFS from this cell to recompute all dependent cells. Before recomputing, check for cycles using the dependency graph.

4

Cycle detection: when adding a new dependency edge (parent -> child), check if a path already exists from child to parent. If so, adding the edge creates a cycle. Use DFS or topological sort to detect this. Throw an error if a cycle is detected.

5

sum(row, col, numbers): parse each reference (e.g., "A1", "A1:B3"). Expand ranges into individual cells. Compute the sum of all referenced cells' values. Store this as the cell's value. Set up dependency edges: each referenced cell has this cell in its dependents.

6

Propagation: when a cell changes, all cells that directly or indirectly depend on it must be recomputed. Use BFS from the changed cell through the dependents graph. Recompute each cell's formula in topological order to ensure dependencies are evaluated first.

Optimal Approach

Maintain a grid (2D array of values), deps (map of cell -> set of cells it depends on), and dependents (map of cell -> set of cells that depend on it).

set(row, col, val):

  1. Clear old dependencies of (row, col) from both deps and dependents.
  2. If val starts with "=", parse references and build new dependency edges.
  3. Check for cycles (DFS from this cell through deps). If cycle found, revert and throw error.
  4. Recompute this cell's value.
  5. BFS from this cell through dependents to recompute all downstream cells.

sum(row, col, numbers):

  1. Parse each reference, expand ranges.
  2. For each referenced cell, add (row, col) to its dependents, and the referenced cell to (row, col)'s deps.
  3. Sum all referenced cell values and store in grid[row][col].

Walkthrough: set(0, 0, 5) sets A1=5. set(0, 1, "=SUM(A1:A1)") sets B1=SUM(A1). B1 depends on A1. Now set(0, 0, 10): A1 changes to 10, BFS finds B1 depends on A1, recompute B1=10.

Time: set is O(V+E) where V=cells, E=dependency edges. Space: O(n²) for grid and dependency maps.

Track who depends on whom

sum(3,C,[A1, A1:B2])deps[C3] = {A1,B1,A2,B2}dependents[A1] += C3dependents[B2] += C3Building the formula records both directions of everyedge.set(2,B,2)clear old deps of B2B2 = 2walk dependents of B2recompute C3 = 6A change spreads forward through the dependents graph,so every affected formula is refreshed.deps[cell] = cells it readsdependents[cell] = cells that read iton change: BFS over dependents
Each formula cell stores the cells it reads (deps), and each read cell stores the formula cells that watch it (dependents).
ComplexityTime O(V + E) per set or sum, where VSpace O(V + E)The cost comes from walking the dependency graph to recompute every cell that (directly or indirectly) depends on the changed cell.

What Trips People Up in Real Interviews

1

Not clearing old dependencies when a cell is re-set. If A1's formula changes from "=SUM(B1:B3)" to "=SUM(C1:C3)", you must remove the B1-B3 dependency edges and add C1-C3 edges. Forgetting this leads to stale or incorrect updates.

2

Failing to detect cycles. If A1 = "=SUM(B1:B1)" and B1 = "=SUM(A1:A1)", setting either creates a cycle. You must check before adding the dependency edge, not after.

3

Recomputing in the wrong order. If C1 depends on B1 which depends on A1, and A1 changes, you must recompute B1 before C1. Use BFS/DFS with proper ordering, or topological sort.

4

Not handling the case where a formula references itself. "=SUM(A1:A1)" on cell A1 references itself — this is a self-cycle and must be rejected.

5

Parsing ranges incorrectly. "A1:B3" means columns A to B, rows 1 to 3 (4 cells total). Do not confuse row and column ranges. The format is always letter+number, letter+number.

Solution Code

O(V + E) per set or sum, where V time
class Excel:

    def __init__(self, height: int, width: str):
        self.cols = ord(width) - ord('A') + 1
        self.rows = height
        self.grid = [[0] * self.cols for _ in range(self.rows)]
        self.formula = [[None] * self.cols for _ in range(self.rows)]
        self.deps = [[set() for _ in range(self.cols)] for _ in range(self.rows)]
        self.dependents = [[set() for _ in range(self.cols)] for _ in range(self.rows)]

    def set(self, row: int, col: int, val: int | str) -> None:
        self._clear_deps(row, col)
        if isinstance(val, str) and val.startswith("="):
            self.formula[row][col] = val
            self._parse_and_set_deps(row, col, val)
        else:
            self.formula[row][col] = None
            self.grid[row][col] = int(val)
        self._propagate(row, col)

    def sum(self, row: int, col: int, numbers: list[str]) -> int:
        self._clear_deps(row, col)
        self.formula[row][col] = None
        total = 0
        for ref in numbers:
            cells = self._expand(ref)
            for r, c in cells:
                self.deps[row][col].add((r, c))
                self.dependents[r][c].add((row, col))
                total += self.grid[r][c]
        self.grid[row][col] = total
        self._propagate(row, col)
        return total

    def _clear_deps(self, row, col):
        for r, c in self.deps[row][col]:
            self.dependents[r][c].discard((row, col))
        self.deps[row][col].clear()

    def _parse_and_set_deps(self, row, col, val):
        inner = val[1:].split("(")[1].rstrip(")")
        for part in inner.split(","):
            cells = self._expand(part.strip())
            for r, c in cells:
                self.deps[row][col].add((r, c))
                self.dependents[r][c].add((row, col))

    def _expand(self, ref: str) -> list[tuple]:
        if ":" in ref:
            start, end = ref.split(":")
            sr, sc = self._parse_cell(start)
            er, ec = self._parse_cell(end)
            return [(r, c) for r in range(sr, er + 1) for c in range(sc, ec + 1)]
        r, c = self._parse_cell(ref)
        return [(r, c)]

    def _parse_cell(self, s: str):
        col = ord(s[0]) - ord('A')
        row = int(s[1:]) - 1
        return row, col

    def _evaluate(self, row, col) -> int:
        if self.formula[row][col] is None:
            return self.grid[row][col]
        total = 0
        for r, c in self.deps[row][col]:
            total += self._evaluate(r, c)
        return total

    def _propagate(self, row, col):
        from collections import deque
        q = deque()
        for r, c in self.dependents[row][col]:
            q.append((r, c))
        visited = set()
        while q:
            r, c = q.popleft()
            if (r, c) in visited:
                continue
            visited.add((r, c))
            self.grid[r][c] = self._evaluate(r, c)
            for nr, nc in self.dependents[r][c]:
                q.append((nr, nc))

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Design Excel Sum Formula problem?

Design an Excel-like system that supports `set(row, col, value)` and `sum(row, col, numbers)` where numbers is a list of cell references in the format "A1" or ranges like "A1:B3". The `sum` function must detect circular dependencies and update all dependent cells when a cell changes.

How do you solve Design Excel Sum Formula?

The optimal approach runs in O(V + E) per set or sum, where V time and O(V + E) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Design Excel Sum Formula?

Design Excel Sum Formula is asked at OpenAI, Rippling, Airbnb. It is a hard difficulty problem.

What are common mistakes on Design Excel Sum Formula?
  • Not clearing old dependencies when a cell is re-set. If A1's formula changes from "=SUM(B1:B3)" to "=SUM(C1:C3)", you must remove the B1-B3 dependency edges and add C1-C3 edges. Forgetting this leads to stale or incorrect updates.
  • Failing to detect cycles. If A1 = "=SUM(B1:B1)" and B1 = "=SUM(A1:A1)", setting either creates a cycle. You must check before adding the dependency edge, not after.
  • Recomputing in the wrong order. If C1 depends on B1 which depends on A1, and A1 changes, you must recompute B1 before C1. Use BFS/DFS with proper ordering, or topological sort.
  • Not handling the case where a formula references itself. "=SUM(A1:A1)" on cell A1 references itself — this is a self-cycle and must be rejected.
  • Parsing ranges incorrectly. "A1:B3" means columns A to B, rows 1 to 3 (4 cells total). Do not confuse row and column ranges. The format is always letter+number, letter+number.