Design Spreadsheet
Asked at OpenAI, Rippling
Problem
Design a spreadsheet that supports setting cell values and computing sum formulas. Cells can contain integers or formulas of the form "=SUM(cell1:cell2)" which sum all cells in a rectangular range. Formulas may reference other cells, and cell values update dynamically when dependencies change.
Asked At
| Company | Difficulty | |
|---|---|---|
| OpenAI | Medium | View all OpenAI questions → |
| Rippling | Medium | View all Rippling questions → |
How to Think About It
Data structure: use a hash map (dict) mapping cell names (like "A1", "B2") to their raw values (integer or formula string). This is simpler than a 2D array because spreadsheet cells can be sparse.
Parsing: when setting a cell, check if the value starts with "=". If so, it's a formula. Parse the range from "=SUM(A1:B3)" — extract the start cell ("A1") and end cell ("B3"), convert letters to column index and numbers to row index.
Evaluation: to evaluate =SUM(A1:B3), iterate over all cells in the rectangle from A1 to B3. For each cell, if it's an integer, add it. If it's a formula, recursively evaluate it first. Use a visited set to detect circular references.
Cell name parsing: "A1" means column A (index 0), row 1. "B3" means column B (index 1), row 3. To iterate A1 to B3: columns from 0 to 1, rows from 1 to 3. Build cell names like f"{chr(ord('A')+col)}{row}".
Circular reference detection: before evaluating a formula, check if the current cell is in the visited set. If so, it's a cycle — throw an error or return 0. Add the cell to visited before recursing, remove after.
Set operation: when set(cell, value) is called, store the raw value. The spreadsheet does not need to eagerly recompute all dependent formulas — only evaluate on get(). This is lazy evaluation and is the standard approach.
Optimal Approach
Use a hash map cells mapping cell name (string) to raw value (int or formula string).
setCell(cell, value):
- Store
cells[cell] = value.
getValue(cell):
- If cell not in
cells, return 0. - If
cells[cell]is an integer, return it. - If it's a formula string starting with "=", parse the range.
- Extract
"=SUM(A1:B3)"-> start="A1", end="B3". - Convert cell names to (col, row) tuples.
- Iterate all cells in the rectangle.
- For each cell, recursively call
getValue(). - Sum and return.
- Extract
Walkthrough: setCell("A1", 10), setCell("A2", 20), setCell("B1", "=SUM(A1:A2)").
getValue("B1"): formula = "=SUM(A1:A2)". Range A1 to A2.- getValue("A1") = 10. getValue("A2") = 20.
- Sum = 30. Return 30.
Time: setCell is O(1). getValue is O(rows * cols) per formula evaluation. Space: O(n) for the hash map.
What Trips People Up in Real Interviews
Not handling circular references. If cell A1 has =SUM(B1:B2) and B1 has =A1, evaluating A1 causes infinite recursion. Use a visited set to detect cycles.
Misunderstanding the cell name format. "A1" is column A, row 1. Columns are letters (A-Z or beyond), rows are numbers. The conversion from letter to index is ord(letter) - ord('A').
Trying to eagerly recompute all formulas when a cell is set. This is complex and unnecessary. Lazy evaluation (compute on get()) is simpler and sufficient for interviews.
Forgetting that formulas can reference cells that also contain formulas. You must recursively evaluate dependencies, not just read raw values.
Not handling the case where a formula references an empty cell. Assume empty cells have value 0, or handle it explicitly. Clarify with the interviewer.
Solution Code
class Spreadsheet:
def __init__(self, rows: int):
self.cells = {}
def setCell(self, cell: str, value: int | str) -> None:
self.cells[cell] = value
def getValue(self, cell: str) -> int:
if cell not in self.cells:
return 0
val = self.cells[cell]
if isinstance(val, int):
return val
# Parse formula like "=SUM(A1:B3)"
inner = val[1:] # remove "="
func, args = inner.split("(", 1)
args = args.rstrip(")")
start, end = args.split(":")
return self._eval_sum(start, end, set())
def _eval_sum(self, start: str, end: str, visited: set) -> int:
sc, sr = start[0], int(start[1:])
ec, er = end[0], int(end[1:])
total = 0
for c in range(ord(sc), ord(ec) + 1):
for r in range(sr, er + 1):
name = chr(c) + str(r)
if name in visited:
continue
visited.add(name)
total += self.getValue(name)
return totalFrequently Asked Questions
What is the Design Spreadsheet problem?
Design a spreadsheet that supports setting cell values and computing sum formulas. Cells can contain integers or formulas of the form `"=SUM(cell1:cell2)"` which sum all cells in a rectangular range. Formulas may reference other cells, and cell values update dynamically when dependencies change.
How do you solve Design Spreadsheet?
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 Spreadsheet?
Design Spreadsheet is asked at OpenAI, Rippling. It is a medium difficulty problem.
What are common mistakes on Design Spreadsheet?
- Not handling circular references. If cell A1 has `=SUM(B1:B2)` and B1 has `=A1`, evaluating A1 causes infinite recursion. Use a `visited` set to detect cycles.
- Misunderstanding the cell name format. "A1" is column A, row 1. Columns are letters (A-Z or beyond), rows are numbers. The conversion from letter to index is `ord(letter) - ord('A')`.
- Trying to eagerly recompute all formulas when a cell is set. This is complex and unnecessary. Lazy evaluation (compute on `get()`) is simpler and sufficient for interviews.
- Forgetting that formulas can reference cells that also contain formulas. You must recursively evaluate dependencies, not just read raw values.
- Not handling the case where a formula references an empty cell. Assume empty cells have value 0, or handle it explicitly. Clarify with the interviewer.