How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Harvey.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Harvey during technical interviews.

Implement a Spreadsheet With Formulas | Harvey Coding Question

Implement a Spreadsheet With Formulas

Company: Harvey

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design and implement a small spreadsheet engine. ### Part 1: Basic cells Implement a `Spreadsheet` class that supports: - `set_cell(cell_id, value)`: set a cell to a numeric value. - `get_cell(cell_id)`: return the current numeric value of a cell. `cell_id` is a string such as `"A1"`, `"B2"`, or `"AA10"`. If a cell has never been set, assume its value is `0`. A straightforward hash map-based implementation is expected for this part. ### Part 2: Formula cells Extend the spreadsheet so that a cell can also contain a formula. A formula is an expression made of integer constants, cell references, plus signs, and minus signs. For example: ```text A1 = 10 B1 = 5 C1 = A1 + B1 - 3 ``` The spreadsheet should support: - `set_cell(cell_id, value_or_formula)`: set a cell to either a number or a formula string. - `get_cell(cell_id)`: return the evaluated numeric value of the cell. Requirements: 1. Formula cells may depend on other formula cells. 2. Updating a cell should affect all dependent cells. 3. The implementation should correctly evaluate cells in dependency order, for example using topological sorting or DFS with cycle detection. 4. If a circular dependency is introduced, the implementation should detect it and report an error. Example: ```text set_cell("A1", 10) set_cell("B1", "A1 + 5") get_cell("B1") -> 15 set_cell("A1", 20) get_cell("B1") -> 25 set_cell("C1", "B1 + A1") get_cell("C1") -> 45 ``` Discuss the data structures you would use, the evaluation algorithm, and the time complexity of `set_cell` and `get_cell`.

Quick Answer: This question evaluates understanding of data structures and algorithms for dependency management, expression parsing and evaluation, and detection of circular references in a spreadsheet-style system.

Part 1: Basic Spreadsheet Cells

Process a list of spreadsheet operations on basic numeric cells. Each cell ID is a string such as "A1", "B2", or "AA10". Support setting a cell to an integer value and getting the current value of a cell. Any cell that has never been set should be treated as 0. Return the results of all GET operations in order.

Constraints

0 <= len(operations) <= 100000
Each cell_id consists of one or more uppercase letters followed by one or more digits
Values fit in a signed 32-bit integer
All operations are valid and are either SET or GET

Examples

Input: [['SET', 'A1', '10'], ['GET', 'A1'], ['SET', 'B2', '7'], ['GET', 'B2']]

Expected Output: [10, 7]

Explanation: Basic set and get operations on two different cells.

Input: [['GET', 'C3'], ['SET', 'C3', '4'], ['GET', 'C3']]

Expected Output: [0, 4]

Explanation: An unset cell should read as 0.

Input: [['SET', 'AA10', '-3'], ['GET', 'AA10'], ['SET', 'AA10', '8'], ['GET', 'AA10']]

Expected Output: [-3, 8]

Explanation: Handles multi-letter column names, negative values, and overwriting an existing cell.

Input: []

Expected Output: []

Explanation: Edge case: no operations means no outputs.

Hints

A hash map from cell ID to integer value is enough for this part.
When a cell has never been assigned, return 0 instead of raising an error.

Part 2: Spreadsheet With Formula Cells

Implement a small spreadsheet engine that supports both numeric cells and formula cells. Each operation is either setting a cell or getting a cell. A SET value is given as a string and may be a plain integer like "10" or a formula like "A1 + B2 - 3". Formulas may reference other formula cells. Unset cells evaluate to 0. If a SET operation would introduce a circular dependency, reject that update, keep the previous cell contents unchanged, and report "CYCLE". For each GET operation, return the evaluated numeric value as a string.

Constraints

0 <= len(operations) <= 2000
1 <= length of each formula string <= 200
Cell IDs contain one or more uppercase letters followed by one or more digits
All formulas are syntactically valid
Formula tokens are integers, cell references, +, -, and optional spaces

Examples

Input: [['SET', 'A1', '10'], ['SET', 'B1', 'A1 + 5'], ['GET', 'B1'], ['SET', 'A1', '20'], ['GET', 'B1'], ['SET', 'C1', 'B1 + A1 - 3'], ['GET', 'C1']]

Expected Output: ['15', '25', '42']

Explanation: Dependent formulas should reflect updated source values.

Input: [['SET', 'A1', 'B1 - 2'], ['GET', 'A1'], ['GET', 'B1']]

Expected Output: ['-2', '0']

Explanation: Unset referenced cells evaluate to 0, so A1 becomes 0 - 2.

Input: [['SET', 'A1', '1'], ['SET', 'B1', 'A1 + 2'], ['SET', 'A1', 'B1 + 3'], ['GET', 'A1'], ['GET', 'B1']]

Expected Output: ['CYCLE', '1', '3']

Explanation: The third operation would create A1 -> B1 -> A1, so it is rejected and previous values remain.

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

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

Explanation: A direct self-reference is also a cycle, and the failed update leaves A1 unset.

Input: []

Expected Output: []

Explanation: Edge case: no operations.

Hints

Model dependencies as a directed graph from a formula cell to the cells it references.
Use DFS both to evaluate formulas and to detect whether a new formula introduces a cycle.

Quick Overview

This question evaluates understanding of data structures and algorithms for dependency management, expression parsing and evaluation, and detection of circular references in a spreadsheet-style system.