Katkat
Back

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

OpenAISoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Build a small spreadsheet engine with setCell and getCell, where formulas reference other cells and a write that would create a circular dependency must be detected. The exercise also asks for live unit tests, probing data modeling, dependency graphs, cache invalidation and test design.

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.

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.

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.

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

Hints

Hint 1

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.

Hint 2

Where the cycle must be: Before the write, the sheet has no cycles. Ask which cell any new cycle would have to pass through.

Hint 3

Test the graph, not the arithmetic: List the situations where the dependency graph changes shape, not only the ones where values change.

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?