Implement Spreadsheet Cell Updates
Company: Harvey
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Design and implement a small spreadsheet engine that supports setting and reading cell values.
A cell name is a string such as `"A1"`, `"B12"`, or `"AA3"`. Each cell can store either an integer value or a formula string.
Implement the following operations:
```text
setCell(cellName, value)
getCell(cellName) -> int
```
Requirements:
1. **Integer-only version**
- Initially, `setCell` may receive only integer values.
- `getCell` should return the current integer value of the cell.
- Choose an appropriate data structure to store cell values.
2. **Formula support**
- Extend `setCell` so that `value` can also be a formula string.
- A formula always starts with `=`.
- Formulas contain only addition using `+`.
- Each term is either an integer literal or another cell reference.
- There is no subtraction, multiplication, division, modulus, parentheses, or operator precedence beyond left-to-right addition.
Example:
```text
setCell("B1", 10)
setCell("A1", "=B1+5")
getCell("A1") -> 15
```
3. **Dependency updates**
- If a cell changes, all cells that depend on it, directly or indirectly, should reflect the updated value.
Example:
```text
setCell("B1", 10)
setCell("A1", "=B1+5")
setCell("B1", 20)
getCell("A1") -> 25
```
4. **Circular dependency detection**
- Detect circular dependencies when setting a formula.
- Direct and indirect cycles should both be rejected.
Example:
```text
setCell("A1", "=B1+1")
setCell("B1", "=A1+1") // should be rejected because it creates a cycle
```
Assume undefined referenced cells have value `0`, unless you choose to explicitly reject references to undefined cells. State your choice clearly.
Quick Answer: This question evaluates skills in data structures, expression parsing, dependency graph management, incremental evaluation, and cycle detection for maintaining consistent spreadsheet state.