3484. Design Spreadsheet
Asked at OpenAI, Rippling
Difficulty
Medium
Time
O(1) per setCell/resetCell, O(1)
Space
O(k)
Pattern
Array
Companies
2
Problem
Design a class that behaves like a small spreadsheet. The grid has 26 columns named 'A' through 'Z' and a fixed number of rows given at construction time. Every cell starts at 0.
Support three operations. setCell(cell, value) stores an integer in one cell. resetCell(cell) puts that cell back to 0. getValue(formula) takes a string of the form "=X+Y" and returns the sum, where X and Y are each either a cell reference like "A1" or a plain non-negative integer.
A cell reference is a capital letter plus a 1-indexed row number, for example "B10" means column B, row 10. Any cell you never set counts as 0 when it appears in a formula. The formula always has exactly two terms joined by +.
A sparse grid of cells
Constraints
- ●
1 <= rows <= 10^3 - ●
0 <= value <= 10^5 - ●
The formula is always in the format "=X+Y", where X and Y are either valid cell references or non-negative integers with - ●
Each cell reference consists of a capital letter from 'A' to 'Z' followed by a row number between 1 and rows. - ●
At most 10^4 calls will be made in total to setCell, resetCell, and getValue.
Examples
["Spreadsheet", "getValue", "setCell", "getValue", "setCell", "getValue", "resetCell", "getValue"]
[[3], ["=5+7"], ["A1", 10], ["=A1+6"], ["B2", 15], ["=A1+B2"], ["A1"], ["=A1+B2"]][null, 12, null, 16, null, 25, null, 15]["Spreadsheet", "getValue", "setCell", "getValue"]
[[1], ["=C1+Z1"], ["C1", 7], ["=C1+Z1"]][null, 0, null, 7]Asked At
2 companies| 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.
Store raw values, evaluate on demand
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
O(1) per setCell/resetCell, O(1) timeclass 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 runs in O(1) per setCell/resetCell, O(1) time and O(k) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.