Design Excel Sum Formula
Asked at OpenAI, Rippling
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| OpenAI | Hard | View all OpenAI questions → |
| Rippling | Hard | View all Rippling questions → |
How to Think About It
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.
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 itsdependents, and B1 has A1 in itsdeps.
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.
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.
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.
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):
- Clear old dependencies of (row, col) from both
depsanddependents. - If
valstarts with "=", parse references and build new dependency edges. - Check for cycles (DFS from this cell through
deps). If cycle found, revert and throw error. - Recompute this cell's value.
- BFS from this cell through
dependentsto recompute all downstream cells.
sum(row, col, numbers):
- Parse each reference, expand ranges.
- For each referenced cell, add (row, col) to its
dependents, and the referenced cell to (row, col)'sdeps. - 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.
What Trips People Up in Real Interviews
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.
Solution Code
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))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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Design Excel Sum Formula?
Design Excel Sum Formula is asked at OpenAI, Rippling. 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.