Quick Overview

This question evaluates expression parsing, symbolic cell reference resolution, dependency graph construction, cycle detection, and stateful API design for an in-memory spreadsheet.

Implement a Formula Spreadsheet

Company: Harvey

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design and implement a small in-memory spreadsheet. The spreadsheet must support cell labels such as `A1` and `B10`, where a label consists of uppercase letters followed by a positive row number. Implement the following API: ```python set_cell(label, value) get_cell(label) -> int ``` ### Part 1: Plain integer cells A cell can store an integer value. Example: ```python set_cell("A1", 10) get_cell("A1") # returns 10 ``` ### Part 2: Formulas A cell can also store a formula. A formula is an expression containing only: - integer literals, - cell references, - the `+` operator. You do not need to support subtraction, multiplication, division, parentheses, or operator precedence beyond addition. Examples: ```python set_cell("A1", "10") set_cell("A2", "A1+20") get_cell("A2") # returns 30 set_cell("A3", "A1+A2+5") get_cell("A3") # returns 45 ``` Formulas should be evaluated using the current values of referenced cells. If a referenced cell does not exist, raise an error. ### Part 3: Cycle detection The spreadsheet must detect cyclic dependencies and report an error instead of recursing forever. Example: ```python set_cell("A1", "B1+1") set_cell("B1", "A1+1") get_cell("A1") # raises a cycle-detected error ``` Implement the data structures and logic needed for `set_cell` and `get_cell`.

Quick Answer: This question evaluates expression parsing, symbolic cell reference resolution, dependency graph construction, cycle detection, and stateful API design for an in-memory spreadsheet.

Part 1: Plain Integer Spreadsheet

Implement a tiny in-memory spreadsheet that stores only integer values. You are given a sequence of operations. Each operation is either ('SET', label, value) to store an integer in a cell, or ('GET', label) to read a cell. Cell labels look like 'A1' or 'BC12' and are guaranteed to be valid. Return the result of every GET in order. If a GET asks for a cell that has never been set, return 'ERROR' for that GET.

Constraints

  • 0 <= len(operations) <= 100000
  • All labels in the input are valid spreadsheet labels: uppercase letters followed by a positive row number
  • Stored values are integers in the 32-bit signed range
  • Only SET and GET operations appear

Examples

Input: []

Expected Output: []

Explanation: There are no operations, so there are no GET results to return.

Input: [('SET', 'A1', 10), ('GET', 'A1')]

Expected Output: [10]

Explanation: Cell A1 is set to 10, so the GET returns 10.

Hints

  1. A hash map from label to integer is enough for this part.
  2. You only need to add something to the output when you see a GET operation.

Part 2: Spreadsheet with Addition Formulas

Extend the spreadsheet so cells can store either integers or formulas. A SET value may be an integer like 10, or a string formula such as '10', 'A1+20', or 'A1+A2+5'. Formulas contain only integer literals, cell references, and the '+' operator, with no spaces. Evaluate formulas lazily when GET is called, using the spreadsheet's current contents at that moment. If a GET tries to read an unset cell, or any referenced cell does not exist, return 'ERROR' for that GET. In this part, you may assume there are no cyclic dependencies.

Constraints

  • 0 <= len(operations) <= 10000
  • All labels in the input are valid spreadsheet labels
  • Formula strings contain no spaces and use only integer literals, valid cell references, and '+'
  • For this part, dependency graphs are acyclic
  • A later SET can overwrite any earlier cell content

Examples

Input: [('SET', 'A1', 10), ('GET', 'A1')]

Expected Output: [10]

Explanation: A1 is set to 10, so GET A1 returns 10.

Input: [('SET', 'A1', 10), ('SET', 'A1', 30), ('GET', 'A1')]

Expected Output: [30]

Explanation: The second SET overwrites the first value.

Hints

  1. Store the raw value for each cell. If it is a formula, evaluate it only when needed.
  2. Split a formula on '+' and process each token as either an integer literal or another cell reference.

Part 3: Spreadsheet with Cycle Detection

Now support formulas exactly as in Part 2, but also detect cyclic dependencies. A cell may contain an integer or a formula string made of integer literals, cell references, and '+'. When evaluating a GET, if the dependency graph contains a cycle, return 'CYCLE' for that GET instead of recursing forever. If a referenced cell is missing, return 'ERROR'. Formulas must still use the current cell values at evaluation time.

Constraints

  • 0 <= len(operations) <= 10000
  • All labels in the input are valid spreadsheet labels
  • Formula strings contain no spaces and use only integer literals, valid cell references, and '+'
  • Cycles may exist and must be reported on GET
  • A later SET can overwrite any earlier cell content

Examples

Input: [('SET', 'A1', 'B1+1'), ('SET', 'B1', 'A1+1'), ('GET', 'A1')]

Expected Output: ['CYCLE']

Explanation: A1 depends on B1, and B1 depends back on A1.

Input: [('SET', 'A1', 'A1+1'), ('GET', 'A1')]

Expected Output: ['CYCLE']

Explanation: A direct self-reference is also a cycle.

Hints

  1. During DFS evaluation, keep a set of cells currently on the recursion stack.
  2. Use two states: one structure for cells already fully computed in this GET, and one for cells currently being visited.

Loading coding console...