Katkat
Back

Evaluate Spreadsheet Cells and Reject Circular References

PikaSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Implement a small spreadsheet whose cells hold integers or single-reference formulas with offsets. Evaluate through current dependencies, propagate updates, report unset chains, and reject a formula atomically whenever it would introduce a circular reference.

Problem

Implement a small spreadsheet with columns A through Z and rows 1 through 26. A cell stores either an integer or a formula consisting of one cell reference plus an integer offset. Formulas are evaluated using current referenced values, and updates that would create any dependency cycle must be rejected.

Function Contract

Implement run_spreadsheet(commands) and return one string per command.

Rules

  • ["SET_VALUE", cell, value] stores an integer and emits "OK".
  • ["SET_FORMULA", cell, referenced_cell, offset] stores cell = referenced_cell + offset; emit "CIRCULAR" and preserve the old cell if the update creates a cycle, otherwise emit "OK".
  • ["GET", cell] emits its integer value, or "UNSET" when it or any referenced cell is unset.
  • Changing a cell immediately affects all formulas that depend on it.
  • Cell matching is case-insensitive, but every command contains a syntactically valid address.

Constraints

  • 1 <= len(commands) <= 100000.
  • Values and offsets are integers in [-10^9, 10^9].
  • Every evaluated result fits in a signed 64-bit integer.

Examples

commands = [
 ["SET_VALUE", "A1", 20],
 ["SET_FORMULA", "B1", "A1", 10],
 ["GET", "B1"],
 ["SET_FORMULA", "A1", "B1", 0],
 ["GET", "A1"]
]
output = ["OK", "OK", "30", "CIRCULAR", "20"]