Evaluate Spreadsheet Cells and Reject Circular References
Company: Pika
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
## Problem
Implement a small spreadsheet with columns `A` through `Z` and rows `1` through `26`. A cell stores either an integer or a formula consisting of one cell reference plus an integer offset. Formulas are evaluated using current referenced values, and updates that would create any dependency cycle must be rejected.
## Function Contract
Implement `run_spreadsheet(commands)` and return one string per command.
## Rules
- `["SET_VALUE", cell, value]` stores an integer and emits `"OK"`.
- `["SET_FORMULA", cell, referenced_cell, offset]` stores `cell = referenced_cell + offset`; emit `"CIRCULAR"` and preserve the old cell if the update creates a cycle, otherwise emit `"OK"`.
- `["GET", cell]` emits its integer value, or `"UNSET"` when it or any referenced cell is unset.
- Changing a cell immediately affects all formulas that depend on it.
- Cell matching is case-insensitive, but every command contains a syntactically valid address.
## Constraints
- `1 <= len(commands) <= 100000`.
- Values and offsets are integers in `[-10^9, 10^9]`.
- Every evaluated result fits in a signed 64-bit integer.
## Examples
```text
commands = [
["SET_VALUE", "A1", 20],
["SET_FORMULA", "B1", "A1", 10],
["GET", "B1"],
["SET_FORMULA", "A1", "B1", 0],
["GET", "A1"]
]
output = ["OK", "OK", "30", "CIRCULAR", "20"]
```
Overview: Implement a small spreadsheet whose cells hold integers or single-reference formulas with offsets. Evaluate through current dependencies, propagate updates, report unset chains, and reject a formula atomically whenever it would introduce a circular reference.
Process commands for a spreadsheet whose valid cells are columns A through Z and rows 1 through 26. Cell matching is case-insensitive. SET_VALUE stores an integer and emits "OK". SET_FORMULA stores cell = referenced_cell + offset and emits "OK", unless that update would create any dependency cycle; in that case emit "CIRCULAR" and preserve the cell's previous contents. GET emits the cell's current integer value as a string, or "UNSET" if the cell or any cell it depends on is unset. Formula values must reflect later source updates immediately. Return one emitted string for every command.
Constraints
- 1 <= len(commands) <= 100000.
- Cells range from A1 through Z26, and matching is case-insensitive.
- Each command is a valid SET_VALUE, SET_FORMULA, or GET command.
- Values and offsets are integers in [-10^9, 10^9].
- Every evaluated result fits in a signed 64-bit integer.
- A rejected cycle-creating update must preserve the cell's old contents.
Examples
Input: ([['SET_VALUE', 'A1', 20], ['SET_FORMULA', 'B1', 'A1', 10], ['GET', 'B1'], ['SET_FORMULA', 'A1', 'B1', 0], ['GET', 'A1']],)
Expected Output: ['OK', 'OK', '30', 'CIRCULAR', '20']
Explanation: This is the source example; the cycle-creating update is rejected and A1 keeps its literal value.
Input: ([['GET', 'Z26']],)
Expected Output: ['UNSET']
Explanation: A cell with no stored value or formula is unset.
Hints
- Each formula points to exactly one other cell, so cycle detection can follow a single dependency chain.
- Evaluate formulas from current cell state at GET time rather than copying source values during updates.