Katkat
Back

Spreadsheet Class With Set/Get, Cell-Reference Formulas and Cycle-Rejecting Writes

HarveySoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Implement an in-memory spreadsheet class in three steps: set and get integer cell values, support formulas that reference other cells, and reject any write that would create a circular reference while leaving the sheet unchanged. It tests dependency tracking, update propagation and cycle detection.

Implement an in-memory spreadsheet. Cells are named by column letters followed by a row number, such as A1 or C12. The interview built the class in three parts, each extending the previous one; the code is substantial, so keep the design simple enough to finish all three.

A possible interface (adjust it as you clarify):

class Spreadsheet:
 def set(self, cell: str, value: str) -> None: ...
 def get(self, cell: str) -> int: ...

Constraints and Clarifications

  • The formula syntax was not specified. Unless the interviewer says otherwise, assume a value is either an integer literal such as "42", or a formula: a string starting with = that adds integer literals and cell references with +, such as "=A1+B2+5".
  • A formula may reference cells that have not been set yet.

Clarifying Questions

  • Which formula syntax must be supported: only +, or also -, *, parentheses, and functions over ranges such as a sum of A1:A10?
  • What does get return for a cell that has never been set?
  • When a referenced cell changes, must the next get of a formula cell reflect the new value?
  • How should a rejected write be reported: an exception, a boolean return value, or an error value stored in the cell?
  • Are reads much more frequent than writes, or the other way around?

Part 1 — Set and get values

Implement set and get for plain integer values.

What This Part Should Cover

  • Storage keyed by cell name, and validation of names and values
  • The value of a cell that was never set

Part 2 — Support formulas

A value that starts with = is a formula. get on a formula cell returns the formula evaluated with the current values of the cells it references, which may themselves contain formulas.

What This Part Should Cover

  • Parsing a formula into references and constants
  • Correct values through chains of references, including after a referenced cell changes
  • Updating dependencies when a cell's formula is replaced
  • The cost of set and of get

Part 3 — Reject writes that create a cycle

If a set would make a cell depend on itself, directly or through other cells, reject the write and leave the spreadsheet exactly as it was before the call.

What This Part Should Cover

  • Detecting the cycle before anything is modified
  • Self-references and indirect cycles
  • The cost of the check, and whether it can share work with the update from Part 2

Hints

Hint 1

Plan for the next part: Decide what a cell stores now, knowing that the next part puts formulas in the same cells.

Hint 2

Two different things in one cell: Separate what the user typed into a cell from what the cell is currently worth, and decide when the second one is computed.

Hint 3

Chains of references: When one cell changes, think about which other cells may now have a different value, and in what order they would have to be brought up to date.

Hint 4

What the new write adds: Model references as a graph. Ask which edges the new formula adds, and what path would already have to exist for one of them to close a cycle.

Follow-up questions

  • Support range functions such as a sum over `A1:B10`. What changes in dependency tracking, and what does a large range cost?
  • With millions of cells and long chains, how do you avoid recomputing values that nobody reads?
  • After one cell changes, how do you guarantee that each dependent cell is recomputed exactly once, after all of its inputs?
  • How would you add undo for the last `set`?