Katkat
Back

Mini Spreadsheet with Formulas Evaluated in set_cell and Cycle Rejection

HarveySoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

A three-part coding exercise: build a mini spreadsheet with set_cell and get_cell, add formulas that sum constants and cell references with values computed eagerly in set_cell, and detect and reject circular dependencies. It tests dependency graphs, ordered recomputation and cycle checks.

Build a small in-memory spreadsheet with two operations: set_cell(label, value) stores a value in a cell, and get_cell(label) returns a cell's value. A label is letters followed by digits, such as "A1". The exercise has three parts, and the interview expects all three to be finished within the session, so budget your time.

Constraints and Clarifications

  • Formulas support only +; there is no -, * or /.
  • A cell's value must be computed when set_cell is called, not when get_cell is called: get_cell returns a stored value without evaluating anything.
  • Assume plain values and the constants inside formulas are integers.

Clarifying Questions

  • What does get_cell return for a cell that was never set, and what value does a formula use when it references such a cell?
  • Are labels case-sensitive: is "a1" the same cell as "A1"?
  • Can a formula contain spaces, such as "= A1 + 5"?
  • When a value is rejected, should set_cell raise an error or return a status, and must the cell keep its previous content?

Part 1 — Plain values

Implement set_cell(label, value) and get_cell(label) for plain integer values.

What This Part Should Cover

  • Validation and normalization of labels
  • Storage of values, and the behavior for cells that were never set
  • A representation that extends to formulas without a rewrite

Part 2 — Formulas computed in set_cell

A value that begins with = is a formula: a sum of integer constants and cell references, such as "=B1+5" or "=A1+A2+5". For example, after set_cell("A1", 10) and set_cell("A2", "=A1+20"), get_cell("A2") returns 30.

The value must be computed during set_cell, not during get_cell. Assume standard spreadsheet behavior: a formula always reflects the current values of the cells it references, so when a referenced cell changes, every cell that depends on it, directly or through other cells, is updated within that set_cell call. After set_cell("A1", 1) in the example, get_cell("A2") returns 21.

Clarifying Questions for this Part

  • Can a formula reference a cell that has not been set yet?

What This Part Should Cover

  • Parsing a formula into constants and references
  • Tracking dependencies in both directions
  • Recomputing every affected cell in a correct order during set_cell
  • The cost of set_cell and of get_cell

Part 3 — Cycle detection

Detect and reject circular dependencies. For example, after set_cell("A1", "=B1+1"), the call set_cell("B1", "=A1+1") must be rejected; likewise, after set_cell("A1", "=B1+C1"), the call set_cell("C1", "=A1") must be rejected.

What This Part Should Cover

  • Detecting whether a new formula would create a cycle of any length, including a self-reference
  • Rejecting the formula without modifying any state
  • The cost of the check, and recursion depth on long dependency chains

Hints

Hint 1

Leave room for formulas: Store enough per cell that a later part can tell a constant from a formula and recompute the cell when something it depends on changes.

Hint 2

Who needs to know: When a cell changes, think about how you find every cell whose value depends on it, directly or through other cells.

Hint 3

Order of recomputation: If A3 depends on both A1 and A2, and A2 depends on A1, decide which cell must be recomputed first after A1 changes.

Hint 4

Check before you commit: A rejected formula must leave no trace. Decide what you can check before you change any state.

Hint 5

Where a cycle can close: A new formula for a cell can only create a cycle that passes through that cell. Think about what you need to search to find one.

Follow-up questions

  • One cell has 100,000 cells depending on it in a chain. What does `set_cell` on it cost, and would lazy evaluation be better for that workload?
  • How would you add `-` and `*` with operator precedence?
  • How would you support a range function, such as a sum over `A1:A100`?
  • How would you implement undo for `set_cell`?