Quick Overview

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

Spreadsheet Formulas, Dependencies, and Circular References

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Other

Implement a spreadsheet that stores integer literals or formulas referencing other cells. Updating an input cell must affect later reads of all dependent cells. Detect circular references when a requested value cannot be evaluated. 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 ```text operations = [ ["set","A1","4"], ["set","B1","=A1+A1-1"], ["get","B1"], ["set","A1","8"], ["get","B1"] ] result = ["OK","OK","7","OK","15"] ``` ```text operations = [ ["set","A1","=B1+1"], ["set","B1","=A1"], ["get","A1"], ["get","C1"], ["set","B1","2"], ["get","A1"] ] result = ["OK","OK","CYCLE","0","OK","3"] ``` ```hint 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. ```

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

Read the full Software Engineer interview experience this question came from

Implement a spreadsheet that stores integer literals or formulas referencing other cells. Updating an input cell must affect later reads of all dependent cells. Detect circular references when a requested value cannot be evaluated. 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 ```text operations = [ ["set","A1","4"], ["set","B1","=A1+A1-1"], ["get","B1"], ["set","A1","8"], ["get","B1"] ] result = ["OK","OK","7","OK","15"] ``` ```text operations = [ ["set","A1","=B1+1"], ["set","B1","=A1"], ["get","A1"], ["get","C1"], ["set","B1","2"], ["get","A1"] ] result = ["OK","OK","CYCLE","0","OK","3"] ```

Constraints

  • At most 500 syntactically valid operations, each a set or get.
  • Cell names are uppercase letters followed by a positive decimal row with no leading zeros.
  • A set stores a signed integer string or an equals-prefixed formula.
  • Formula grammar is term ((+ | -) term)* with at most 100 terms; each term is a nonnegative integer or cell name. Spaces around tokens are permitted; unary signs and parentheses are not.
  • Unset cells are zero; repeated references contribute repeatedly.
  • Set replaces the prior value; only reachable cycles fail reads, and updates or cycle repairs must affect future reads.
  • Numeric tokens, stored integers, and every intermediate result of acyclic evaluation fit a signed 32-bit integer.
  • Each set returns OK; each get returns canonical decimal notation or CYCLE.

Examples

Input: ([['set', 'A1', '4'], ['set', 'B1', '=A1+A1-1'], ['get', 'B1'], ['set', 'A1', '8'], ['get', 'B1']],)

Expected Output: ['OK', 'OK', '7', 'OK', '15']

Explanation: Source duplicate-reference and update example.

Input: ([['set', 'A1', '=B1+1'], ['set', 'B1', '=A1'], ['get', 'A1'], ['get', 'C1'], ['set', 'B1', '2'], ['get', 'A1']],)

Expected Output: ['OK', 'OK', 'CYCLE', '0', 'OK', '3']

Explanation: Source cycle, unrelated read, and repair example.

Hints

  1. A repeated reference is evaluated at each occurrence in the arithmetic expression.
  2. Apply the stated cycle rule only to dependencies reachable from the requested cell.

Loading coding console...

Show the approach

Approach

Keep the latest raw definition for each cell. For every get, allocate a fresh memo table and active-path set. Evaluate a literal directly or tokenize a formula into cell names, nonnegative constants, and binary operators. Accumulate terms with the current plus/minus sign in input order. Unset cells evaluate to zero. Mark a cell active before following its dependencies; reaching an active cell proves a directed cycle, while a completed memoized value can safely be reused across shared paths. By induction over acyclic dependencies, every memoized cell equals the arithmetic value of its stored definition. A cycle aborts only the current read. New per-read state prevents stale values after sets or repairs. Convert successful integers to decimal strings to enforce canonical formatting.

Time complexity:
O(S + sum_g(P_g + V_g)) expected, where S is total stored-input processing and P_g and V_g are reachable definition text and cells for get g
Space complexity:
O(S_live + max_g(P_g + V_g)) auxiliary, excluding returned output; each get discards its memo and active-path state