Design a Spreadsheet with Cell Updates and Sum Queries
Company: Citadel
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Implement a spreadsheet with `rows` rows and 26 columns labeled `A` through `Z`. Row numbers are one-based. Every cell initially contains zero and can hold an integer from `0` through `100000`.
Implement the following `Spreadsheet` operations:
- `Spreadsheet(int rows)`: initialize the grid.
- `void setCell(string cell, int value)`: replace the specified cell's current value with `value`.
- `void resetCell(string cell)`: set that cell's current value to zero.
- `int getValue(string formula)`: evaluate a formula of the form `"=X+Y"`. Each operand is either a valid cell reference, such as `A1` or `Z12`, or a nonnegative integer at most `100000`. Return the sum of the two current operand values.
Reading a cell that has never been set gives zero. Evaluating a formula does not store a formula in a cell or change the spreadsheet.
### C++ Interface
```cpp
class Spreadsheet {
public:
Spreadsheet(int rows) {
}
void setCell(string cell, int value) {
}
void resetCell(string cell) {
}
int getValue(string formula) {
}
};
```
### Examples
**Example 1**
```text
Operations: ["Spreadsheet","getValue","setCell","setCell","getValue","resetCell","getValue"]
Arguments: [[12],["=A12+5"],["A12",14],["B2",9],["=A12+B2"],["A12"],["=A12+B2"]]
Output: [null,5,null,null,23,null,9]
```
The first query reads the unset `A12` as zero. After setting `A12` to `14` and `B2` to `9`, their sum is `23`. Resetting `A12` changes the last sum to `9`.
**Example 2**
```text
Operations: ["Spreadsheet","setCell","getValue","setCell","getValue","getValue","resetCell","getValue"]
Arguments: [[1],["Z1",100000],["=Z1+Z1"],["Z1",0],["=Z1+Z1"],["=100000+Z1"],["A1"],["=A1+0"]]
Output: [null,null,200000,null,0,100000,null,0]
```
The same cell can be both operands, so the first sum is `200000`. Setting `Z1` to zero affects subsequent queries. Resetting an already-zero, unset `A1` leaves it zero. The `null` entries describe constructor and `void` operations in the trace; they are not additional C++ return values.
### Constraints
- `1 <= rows <= 1000`.
- Values passed to `setCell` satisfy `0 <= value <= 100000`.
- Every formula has exactly the form `"=X+Y"`, with each operand a valid cell reference or a nonnegative integer at most `100000`.
- Each cell reference is one capital letter from `A` through `Z` followed by a row number from `1` through `rows`.
- At most `10000` calls in total are made to `setCell`, `resetCell`, and `getValue`.
### Clarifying Questions
- Can formulas contain subtraction, multiplication, or nested expressions? No. The given format contains exactly two operands joined by addition.
- Does `getValue` create a stored formula or dependency? No. It returns the sum using the cell values at that call.
- May a cell be reset before it has been explicitly set? Yes. Its value remains zero.
### What a Strong Answer Covers
- Persistent cell values across the exact constructor and method sequence.
- Column letters, multi-digit row numbers, and one-based row references.
- Cell and integer operands, repeated references, and zero defaults.
- Correct results after overwrites and resets, with bounds for initialization and each operation.
### Follow-up Questions
- What should a query return when both operands reference the same cell after that cell has been reset?
- What additional behavior would need to be specified if formulas could be stored inside cells instead of evaluated immediately?
```hint Separate storage from evaluation
A zero-initialized grid is small enough for these limits. Parse a cell into its row and column, and resolve each formula operand as either a current cell value or an integer literal.
```
Overview: Implement the Spreadsheet class with persistent zero-initialized cells, updates, resets and immediate two-operand sum queries. Preserve one-based row references, current values and the constructor and method API.