Implement spreadsheet cells with formulas
Company: Fuse Energy
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Design an in-memory spreadsheet that supports these operations on cells such as `A1`, `B2`, and ranges such as `A1:B2`:
- `Set(cell, value)`: assign an integer literal to a cell.
- `Sum(dest, refs)`: assign `dest` to a formula equal to the sum of all referenced cells. Each item in `refs` is either a single cell like `"B2"` or a rectangular range like `"A1:B2"`.
- `Get(cell)`: return the current value of the cell.
- `Undo()`: revert the most recent successful write operation. Both `Set` and `Sum` count as write operations.
Rules:
1. Cells that have never been assigned should be treated as `0`.
2. Formula cells are reactive: if a referenced cell changes later, `Get` on the formula cell should reflect the new value.
3. Duplicate references count multiple times.
4. A `Sum` operation is invalid if it would introduce a cycle in the dependency graph. In that case, it should raise an error and leave the spreadsheet unchanged.
Example:
```text
Set("A1", 1)
Set("B2", 2)
Sum("D1", ["A1:B2", "B2"])
Get("D1") // 5, because A1 + A2 + B1 + B2 + B2 = 1 + 0 + 0 + 2 + 2
Set("A1", 2)
Get("D1") // 6
```
Cycle examples:
```text
Sum("A1", ["A1", "B1"]) // invalid: direct self-cycle
Sum("A1", ["B1"]) // valid
Sum("B1", ["A1"]) // invalid if A1 already depends on B1
Sum("B3", ["B3"]) // invalid
```
Implement the data structure and explain how you would track dependencies, detect cycles, and support `Undo()` efficiently.
Quick Answer: This question evaluates proficiency in data structures and algorithms for dependency management, reactive computation, cycle detection, and state versioning (undo), assessing the ability to reason about how cells, formulas, and ranges interact under updates.
Design an in-memory spreadsheet that supports integer cells, reactive sum formulas, cycle rejection, and undo. Cells are named with uppercase column letters followed by a positive row number, such as "A1" or "B2". Ranges such as "A1:B2" include every cell in the rectangle. You are given a batch of operations and must return the observable outputs.
Operations are encoded as lists of strings:
- ["Set", cell, value]: assign an integer literal to cell. This removes any previous formula in that cell.
- ["Sum", dest, ref1, ref2, ...]: assign dest to a formula equal to the sum of all referenced cells. Each ref is either a single cell like "B2" or a rectangular range like "A1:B2".
- ["Get", cell]: read the current value of cell.
- ["Undo"]: revert the most recent successful write operation. Both Set and valid Sum operations count as writes.
Rules:
1. Cells that have never been assigned are treated as 0.
2. Formula cells are reactive: if a referenced cell changes later, Get on the formula cell reflects the new value.
3. Duplicate references count multiple times, including duplicates caused by overlapping ranges.
4. A Sum operation is invalid if it would introduce a cycle in the dependency graph. For this batch interface, report this by appending "ERROR" to the returned output list and leaving the spreadsheet unchanged. Invalid Sum operations are not added to the undo history.
5. Undo on an empty history does nothing.
Constraints
- 0 <= len(operations) <= 2000
- Cell names contain uppercase letters followed by a positive row number, such as "A1" or "AA27"
- Set values are integers in the range [-10^9, 10^9]
- The total number of cells expanded from all ranges across all Sum operations is at most 200000
- All input operations are syntactically valid
Examples
Input: ([] ,)
Expected Output: []
Explanation: No operations produce no observable output.
Input: ([["Get", "Z99"], ["Undo"], ["Get", "A1"]],)
Expected Output: ["0", "0"]
Explanation: Unassigned cells read as 0. Undo with no successful writes is a no-op.
Hints
- Store formula dependencies as a graph from a formula cell to the cells it references. Keep reference counts because duplicates must contribute multiple times.
- To check whether assigning dest to depend on refs creates a cycle, ask whether any referenced cell can already reach dest through existing formula dependencies.