Spreadsheet Class with Formula Cells, Recalculation and Cycle Detection

Implement an in-memory spreadsheet class in stages. The interviewer starts with a simple version and adds requirements after each stage, and the full scope is a fair amount of code for a technical screen, so each stage should be finished and runnable before you move on rather than building the final design in one go.

Cells are addressed by labels such as A1 or C12: a column letter followed by a row number. The class exposes two methods:

class Spreadsheet:
 def set_cell(self, label: str, value) -> None: ...
 def get_cell(self, label: str) -> int | None: ...

Clarifying Questions

• What is the exact label format: single-letter columns only, or also multi-letter columns such as AA10? Are labels case-sensitive?
• Can a cell be overwritten, including changing a plain number into a formula or the reverse?
• Can values be negative?

Part 1 — Integer cells

set_cell(label, value) stores an integer value in the cell. get_cell(label) returns the stored integer. There are no formulas in this stage, so it is meant to be finished quickly.

What This Part Should Cover

• A storage model keyed by label, and what get_cell returns for a label that was never set.
• Label validation at the level the interviewer asks for.
• Finishing fast enough to leave time for the later stages.

Part 2 — Formula cells

set_cell now also accepts a formula: a string that starts with =. For example:

• set_cell("A1", "=B1+C1+1"): the value of A1 is the value of B1 plus the value of C1 plus 1;
• set_cell("A1", "=1+2"): a formula made only of integer literals.

get_cell returns the computed integer value of a cell. If a cell has never been set, get_cell must return None or report an error; handle this case explicitly. Circular references such as A1 -> B1 -> A1 will not occur in this stage, and efficient dependency updates are not required: recomputing every previously set cell on each set_cell call, so that get_cell is O(1), is an acceptable approach.

Clarifying Questions for this Part

• Which operators can appear in a formula: only +, as in the examples, or also -, * and parentheses?
• When a formula references a cell that has never been set, is that cell treated as 0, or is the formula's own value undefined (None or an error)?
• Can formulas contain whitespace, and how should a malformed formula be reported?

What This Part Should Cover

• Parsing a formula into cell references and integer literals.
• Recomputation on every set_cell that evaluates cells in a valid order, so that chains of references produce correct values, with O(1) get_cell.
• One consistent rule for never-set cells, both when read directly and when referenced by a formula.
• The cost of recomputing everything on every write.

Part 3 — Cycle detection and targeted recomputation (follow-up)

Formulas may now form circular references, for example set_cell("A1", "=B1") followed by set_cell("B1", "=A1+1"). Add cycle detection, and optimize updates so that set_cell recomputes only the cells that depend, directly or indirectly, on the cell that changed.

Clarifying Questions for this Part

• When a set_cell call would create a cycle, should it be rejected with the sheet left unchanged, or accepted with the cells on the cycle reporting an error?
• Does a self-reference such as set_cell("A1", "=A1+1") count as a cycle?

What This Part Should Cover

• Detecting a cycle introduced by the new formula, including a self-reference, before any state changes, with a defined outcome.
• Dependency and reverse-dependency tracking that stays correct when a formula is replaced by another formula or by a number.
• Recomputation limited to the transitive dependents of the changed cell, in an order where each cell's inputs are already final.
• The cost of set_cell and get_cell compared with Part 2.