Implement a Formula Spreadsheet
Company: Harvey
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Design and implement a small in-memory spreadsheet.
The spreadsheet must support cell labels such as `A1` and `B10`, where a label consists of uppercase letters followed by a positive row number.
Implement the following API:
```python
set_cell(label, value)
get_cell(label) -> int
```
### Part 1: Plain integer cells
A cell can store an integer value.
Example:
```python
set_cell("A1", 10)
get_cell("A1") # returns 10
```
### Part 2: Formulas
A cell can also store a formula. A formula is an expression containing only:
- integer literals,
- cell references,
- the `+` operator.
You do not need to support subtraction, multiplication, division, parentheses, or operator precedence beyond addition.
Examples:
```python
set_cell("A1", "10")
set_cell("A2", "A1+20")
get_cell("A2") # returns 30
set_cell("A3", "A1+A2+5")
get_cell("A3") # returns 45
```
Formulas should be evaluated using the current values of referenced cells. If a referenced cell does not exist, raise an error.
### Part 3: Cycle detection
The spreadsheet must detect cyclic dependencies and report an error instead of recursing forever.
Example:
```python
set_cell("A1", "B1+1")
set_cell("B1", "A1+1")
get_cell("A1") # raises a cycle-detected error
```
Implement the data structures and logic needed for `set_cell` and `get_cell`.
Overview: This question evaluates expression parsing, symbolic cell reference resolution, dependency graph construction, cycle detection, and stateful API design for an in-memory spreadsheet.
Part 1: Plain Integer Spreadsheet
Implement a tiny in-memory spreadsheet that stores only integer values. You are given a sequence of operations. Each operation is either ('SET', label, value) to store an integer in a cell, or ('GET', label) to read a cell. Cell labels look like 'A1' or 'BC12' and are guaranteed to be valid. Return the result of every GET in order. If a GET asks for a cell that has never been set, return 'ERROR' for that GET.
Constraints
- 0 <= len(operations) <= 100000
- All labels in the input are valid spreadsheet labels: uppercase letters followed by a positive row number
- Stored values are integers in the 32-bit signed range
- Only SET and GET operations appear
Examples
Input: []
Expected Output: []
Explanation: There are no operations, so there are no GET results to return.
Input: [('SET', 'A1', 10), ('GET', 'A1')]
Expected Output: [10]
Explanation: Cell A1 is set to 10, so the GET returns 10.
Hints
- A hash map from label to integer is enough for this part.
- You only need to add something to the output when you see a GET operation.
Part 2: Spreadsheet with Addition Formulas
Extend the spreadsheet so cells can store either integers or formulas. A SET value may be an integer like 10, or a string formula such as '10', 'A1+20', or 'A1+A2+5'. Formulas contain only integer literals, cell references, and the '+' operator, with no spaces. Evaluate formulas lazily when GET is called, using the spreadsheet's current contents at that moment. If a GET tries to read an unset cell, or any referenced cell does not exist, return 'ERROR' for that GET. In this part, you may assume there are no cyclic dependencies.
Constraints
- 0 <= len(operations) <= 10000
- All labels in the input are valid spreadsheet labels
- Formula strings contain no spaces and use only integer literals, valid cell references, and '+'
- For this part, dependency graphs are acyclic
- A later SET can overwrite any earlier cell content
Examples
Input: [('SET', 'A1', 10), ('GET', 'A1')]
Expected Output: [10]
Explanation: A1 is set to 10, so GET A1 returns 10.
Input: [('SET', 'A1', 10), ('SET', 'A1', 30), ('GET', 'A1')]
Expected Output: [30]
Explanation: The second SET overwrites the first value.
Hints
- Store the raw value for each cell. If it is a formula, evaluate it only when needed.
- Split a formula on '+' and process each token as either an integer literal or another cell reference.
Part 3: Spreadsheet with Cycle Detection
Now support formulas exactly as in Part 2, but also detect cyclic dependencies. A cell may contain an integer or a formula string made of integer literals, cell references, and '+'. When evaluating a GET, if the dependency graph contains a cycle, return 'CYCLE' for that GET instead of recursing forever. If a referenced cell is missing, return 'ERROR'. Formulas must still use the current cell values at evaluation time.
Constraints
- 0 <= len(operations) <= 10000
- All labels in the input are valid spreadsheet labels
- Formula strings contain no spaces and use only integer literals, valid cell references, and '+'
- Cycles may exist and must be reported on GET
- A later SET can overwrite any earlier cell content
Examples
Input: [('SET', 'A1', 'B1+1'), ('SET', 'B1', 'A1+1'), ('GET', 'A1')]
Expected Output: ['CYCLE']
Explanation: A1 depends on B1, and B1 depends back on A1.
Input: [('SET', 'A1', 'A1+1'), ('GET', 'A1')]
Expected Output: ['CYCLE']
Explanation: A direct self-reference is also a cycle.
Hints
- During DFS evaluation, keep a set of cells currently on the recursion stack.
- Use two states: one structure for cells already fully computed in this GET, and one for cells currently being visited.
Community answers
Answer by priyankmishra1102
import java.util.*;
class FormulaSpreadsheetLazyEvaluation {
private final Map DEFINITIONS;
public FormulaSpreadsheetLazyEvaluation() {
this.DEFINITIONS = new HashMap<>();
}
public void set_cell(String cellNumber, String value) {
if (cellNumber == null || cellNumber.trim().isEmpty()) {
throw new IllegalArgumentException("CellNumber cannot be empty");
}
if (value == null || value.trim().isEmpty()) {
throw new IllegalArgumentException("Value cannot be empty");
}
// Save the raw definition (stripping whitespace)
this.DEFINITIONS.put(cellNumber.trim(), value.replaceAll("\\s+", ""));
}
public int get_cell(String cellNumber) {
if (cellNumber == null || cellNumber.trim().isEmpty()) {
throw new IllegalArgumentException("CellNumber cannot be empty");
}
cellNumber = cellNumber.trim();
if (!this.DEFINITIONS.containsKey(cellNumber)) {
throw new IllegalArgumentException("Cell " + cellNumber + " does not exist");
}
// Sets to track nodes in the current path (cycle detection) and already evaluated nodes
Set visiting = new HashSet<>();
Set visited = new HashSet<>();
return evaluate(cellNumber, visiting, visited);
}
private int evaluate(String current, Set visiting, Set visited) {
if (!this.DEFINITIONS.containsKey(current)) {
throw new IllegalArgumentException("Referenced cell does not exist: " + current);
}
// Cycle detected: current node is already in the recursion call stack
if (visiting.contains(current)) {
throw new CycleException("Cycle detected involving cell: " + current);
}
visiting.