Spreadsheet engine with setCell/getCell, cell references, and cycle detection

Implement a spreadsheet engine with two operations: - `set_cell(cell, content)` stores the content of a cell (`setCell` in camelCase languages). A cell is named by column letters followed by a row number, such as `A1` or `B12`. - `get_cell(cell)` returns the computed value of a cell (`getCell`). Cells can reference other cells, so setting a cell must detect circular dependencies. Once the implementation works, you write tests for it during the interview. The report does not specify the formula grammar. For practice, assume that content is either an integer such as `7`, or a formula that starts with `=` and adds integers and cell references, such as `=A1+B2+5`. Confirm the grammar with the interviewer before you start. ### Clarifying Questions - When `set_cell` would create a cycle, should it reject the write and keep the old content, or store the formula and make the affected cells read as an error? - What does `get_cell` return for a cell that was never set: `0`, an empty value, or an error? - Are reads much more frequent than writes, so that caching computed values pays off? - Which operators or functions must formulas support beyond addition? ### Part 1 — `set_cell` and `get_cell` with references Implement both operations so that a change to one cell is reflected in every cell that depends on it, directly or indirectly. State the complexity of each operation. ```hint Two directions A formula tells you which cells it reads. Think about what you need in order to find the cells that read a given cell when that cell changes. ``` #### What This Part Should Cover - A data model that separates stored content from computed values - When values are computed (on read or on write) and what each choice costs - How a change propagates to every dependent cell, including along several paths at once ### Part 2 — Cycle detection Detect when `set_cell` would create a circular reference, such as setting `A1` to `=B1+1` while `B1` is `=A1`, and handle it with the policy agreed in the clarifying questions. ```hint Where the cycle must be Before the write, the sheet has no cycles. Ask which cell any new cycle would have to pass through. ``` #### What This Part Should Cover - When the check runs, and why running it before any state changes matters - The cost of the check in terms of the cells and references it visits - The state of the sheet after a rejected write ### Part 3 — Write tests Write unit tests for your implementation live, run them, and fix whatever they reveal. ```hint Test the graph, not the arithmetic List the situations where the dependency graph changes shape, not only the ones where values change. ``` #### What This Part Should Cover - Coverage of propagation, overwrites that remove dependencies, and direct, indirect and self cycles - Assertions that a rejected write leaves the sheet unchanged - Small, independent, readable tests, and a methodical way to debug a failing one ### What a Strong Answer Covers - Clean data structures for forward and reverse dependencies - An invariant (the sheet is always acyclic) that the code maintains on every write - Removal of a cell's old dependencies when its content is overwritten - Honest complexity analysis for reads and writes - A test suite that would actually catch the common bugs in this problem ### Follow-up Questions - How would you support range formulas such as `=SUM(A1:A100)` without storing a separate edge for every cell in every range? - If one cell change forces recomputation of a very large number of dependents, how would you keep `set_cell` responsive? - How would you report the exact cells that form a detected cycle to the user?