Katkat
Back

Spreadsheet Formulas, Dependencies, and Circular References

OtherSoftware Engineer · Other
MediumSoftware EngineerOtherCoding & Algorithms

Last updated

Implement spreadsheet formulas with dependency updates, repeated references, unset cells, and cycle detection that recovers after formulas change.

Implement evaluate_sheet(operations: string[][]) -> string[]. Each operation is ["set", cell, raw] or ["get", cell]. Return one string per operation: "OK" for set, the computed integer in canonical decimal notation for a successful get, or "CYCLE" for a get whose dependency traversal encounters a cycle. Canonical decimal notation has no leading plus or leading zeros, and zero is "0".

Practice contract

The reports describe different formula and error conventions. This exercise uses an explicit shared practice contract without attributing it to a single company:

  • Cell names match uppercase letters followed by a positive decimal row number, such as A1 or AA27. Row numbers have no leading zeros.
  • A set stores a signed integer string, such as -5, or a formula starting with =.
  • A formula has grammar term (('+' | '-') term)*, where a term is a nonnegative integer or a cell name. Spaces may appear around tokens. Unary signs and parentheses inside formulas are not supported in this version.
  • Unset cells evaluate to zero. Each occurrence of a referenced cell contributes separately: =A1+A1 counts it twice.
  • A set replaces the previous raw value completely. It may introduce a cycle; the error is reported by a get whose reachable dependencies contain that cycle.
  • A cycle elsewhere in the sheet does not make an unrelated get fail. Replacing a formula can remove a cycle, and subsequent reads must then succeed.
  • Inputs are syntactically valid. There are at most 500 operations and at most 100 terms in a formula. Numeric tokens, stored integers, and every intermediate arithmetic result of an acyclic evaluation fit in a signed 32-bit integer.

Examples

operations = [
 ["set","A1","4"],
 ["set","B1","=A1+A1-1"],
 ["get","B1"],
 ["set","A1","8"],
 ["get","B1"]
]
result = ["OK","OK","7","OK","15"]

operations = [
 ["set","A1","=B1+1"],
 ["set","B1","=A1"],
 ["get","A1"],
 ["get","C1"],
 ["set","B1","2"],
 ["get","A1"]
]
result = ["OK","OK","CYCLE","0","OK","3"]

Hints

Hint 1

Distinguish active work from completed work: A cell reached twice through different dependency paths is not necessarily cyclic. Track whether its value is still being evaluated in the current traversal or has already been completed.