Quick Overview

Implement eager spreadsheet formulas with constant-time cached reads, transitive dependency updates, cycle rejection, and atomic definition replacement.

Eager Spreadsheet Formulas with Constant-Time Reads

Company: Harvey

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a spreadsheet with `set_cell`, `get_cell`, arithmetic formulas, dependency updates, and circular-reference rejection. Each successful write must leave computed values ready so a subsequent `get_cell` is a constant-time cached read. Implement `eager_sheet(operations: string[][]) -> string[]`. Each row is `["set", cell, raw]` or `["get", cell]`. Return one string per operation: - A successful set returns `"OK"`. - A set that would introduce a circular reference returns `"CYCLE"` and leaves the previous sheet unchanged. - A get returns the cell's computed integer in canonical decimal notation, with no leading plus or leading zeros; zero is `"0"`. ### Formula and edit contract The source describes formulas and dependency/cycle handling but does not give a grammar. This practice version explicitly uses: - Cell names are uppercase letters followed by a positive decimal row number with no leading zeros, such as `A1` or `AA10`. - Raw values are signed integer strings or formulas beginning with `=`. - Formula grammar is `term (('+' | '-') term)*`, where a term is a nonnegative integer or a cell reference. Spaces may surround tokens. Unary signs and parentheses inside formulas are excluded. - Unset cells evaluate to zero. Repeated references contribute repeatedly, so `=A1+A1` counts the value twice. - Set replaces the entire previous definition, including its dependency links. It may change a literal to a formula or a formula to a literal. - Direct and indirect cycles are rejected before the edit becomes visible. A failed set preserves both the old definition and every previously computed value. - On a successful set, update every affected dependent value before processing the next operation. Implement get using stored results, without dependency traversal on reads. ### Constraints - There are at most 500 operations and at most 100 terms per formula. - All names and expressions are syntactically valid. - Numeric tokens, stored literals, and all intermediate arithmetic results for an acyclic prospective sheet fit in a signed 32-bit integer. - The sheet starts empty, and operations are processed sequentially. - Cycle-error serialization, unset-cell behavior, grammar, and bounds are explicit practice assumptions. The constant-time-read requirement and the need to consider write-versus-read evaluation come from the reported task. ### Examples ```text operations = [ ["set","A1","2"], ["set","B1","=A1+1"], ["set","C1","=A1+B1"], ["set","A1","5"], ["get","C1"] ] result = ["OK","OK","OK","OK","11"] ``` ```text operations = [ ["set","A1","=B1"], ["set","B1","=A1+1"], ["get","A1"], ["set","A1","3"], ["set","B1","=A1+1"], ["get","B1"] ] result = ["OK","CYCLE","0","OK","OK","4"] ``` The rejected edit in the second example leaves `B1` unset. Replacing `A1` with a literal later removes the dependency that would have completed the cycle. ```hint Keep both graph directions One graph direction identifies a formula's inputs. The other identifies which cached values can change after an input edit. Recompute dependents only after their changed inputs are ready. ```

Overview: Implement eager spreadsheet formulas with constant-time cached reads, transitive dependency updates, cycle rejection, and atomic definition replacement.

Read the full Harvey Software Engineer interview experience this question came from

Implement a spreadsheet with `set_cell`, `get_cell`, arithmetic formulas, dependency updates, and circular-reference rejection. Each successful write must leave computed values ready so a subsequent `get_cell` is a constant-time cached read. Implement `eager_sheet(operations: string[][]) -> string[]`. Each row is `["set", cell, raw]` or `["get", cell]`. Return one string per operation: - A successful set returns `"OK"`. - A set that would introduce a circular reference returns `"CYCLE"` and leaves the previous sheet unchanged. - A get returns the cell's computed integer in canonical decimal notation, with no leading plus or leading zeros; zero is `"0"`. ### Formula and edit contract The source describes formulas and dependency/cycle handling but does not give a grammar. This practice version explicitly uses: - Cell names are uppercase letters followed by a positive decimal row number with no leading zeros, such as `A1` or `AA10`. - Raw values are signed integer strings or formulas beginning with `=`. - Formula grammar is `term (('+' | '-') term)*`, where a term is a nonnegative integer or a cell reference. Spaces may surround tokens. Unary signs and parentheses inside formulas are excluded. - Unset cells evaluate to zero. Repeated references contribute repeatedly, so `=A1+A1` counts the value twice. - Set replaces the entire previous definition, including its dependency links. It may change a literal to a formula or a formula to a literal. - Direct and indirect cycles are rejected before the edit becomes visible. A failed set preserves both the old definition and every previously computed value. - On a successful set, update every affected dependent value before processing the next operation. Implement get using stored results, without dependency traversal on reads. ### Constraints - There are at most 500 operations and at most 100 terms per formula. - All names and expressions are syntactically valid. - Numeric tokens, stored literals, and all intermediate arithmetic results for an acyclic prospective sheet fit in a signed 32-bit integer. - The sheet starts empty, and operations are processed sequentially. - Cycle-error serialization, unset-cell behavior, grammar, and bounds are explicit practice assumptions. The constant-time-read requirement and the need to consider write-versus-read evaluation come from the reported task. ### Examples ```text operations = [ ["set","A1","2"], ["set","B1","=A1+1"], ["set","C1","=A1+B1"], ["set","A1","5"], ["get","C1"] ] result = ["OK","OK","OK","OK","11"] ``` ```text operations = [ ["set","A1","=B1"], ["set","B1","=A1+1"], ["get","A1"], ["set","A1","3"], ["set","B1","=A1+1"], ["get","B1"] ] result = ["OK","CYCLE","0","OK","OK","4"] ``` The rejected edit in the second example leaves `B1` unset. Replacing `A1` with a literal later removes the dependency that would have completed the cycle. ```hint Keep both graph directions One graph direction identifies a formula's inputs. The other identifies which cached values can change after an input edit. Recompute dependents only after their changed inputs are ready. ```

Constraints

  • At most 500 sequential valid operations, each [set,cell,raw] or [get,cell], from an empty sheet.
  • Names use uppercase letters and a positive decimal row without leading zeros. Raw values are signed integers or formulas beginning =.
  • Formulas contain at most 100 nonnegative integer or cell-reference terms joined by + or -, with optional spaces around tokens; no unary signs or parentheses.
  • Unset cells are zero, repeated references contribute repeatedly, and successful set replaces the entire definition and dependencies.
  • Reject direct or indirect cycles with CYCLE and no visible changes. Successful sets return OK and eagerly refresh computed values; gets use cached values in canonical decimal form.
  • Numeric tokens, literals, and intermediate results in acyclic prospective sheets fit signed 32-bit integers.

Examples

Input: ([],)

Expected Output: []

Explanation: An empty operation list has no results.

Input: ([['get', 'A1'], ['set', 'A1', '+0007'], ['get', 'A1'], ['set', 'A1', '-0'], ['get', 'A1']],)

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

Explanation: Unset cells and signed literals produce canonical decimal strings.

Loading coding console...

Show the approach

Approach

For each write, copy the definitions and replace the target definition only in that prospective map. A memoized dependency DFS evaluates all prospective definitions. The active recursion set detects an edge back to an unfinished cell, which is exactly a directed cycle; reject that write without assigning either the prospective map or its temporary cache. On success, each referenced value has been computed before its consumer, and repeated formula terms are added or subtracted separately. Commit both the definitions and complete cache together. This bounded implementation deliberately rebuilds every defined value at each successful write, which includes every affected dependent and simplifies atomicity. Reads perform only a cache lookup; unset names default to zero. Formula-to-literal edits automatically discard prior dependencies because the old expression is replaced.

Time complexity:
Expected O(1) per get. O(V+E+L) per set for V referenced/defined cells, E reference occurrences, and L total expression characters in the prospective sheet; across Q writes, O(Q*(V+E+L)).
Space complexity:
O(V+E+L) for definitions, prospective state, cache, parsed traversal work and recursion; output O(number of operations).