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 Onsite rounds at Harvey.

What role is this question designed for?

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

Design Spreadsheet Formula Cells | Harvey Coding Question

Design Spreadsheet Formula Cells

Company: Harvey

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Design an in-memory spreadsheet that supports assigning either literal integer values or formulas to cells. Cells are identified by names such as `A1`, `B1`, and `C12`. A formula is an expression made of cell references and integer constants joined by `+`, for example: ```text A1 = B1 + C1 + 5 ``` Implement an API similar to: ```text setCell(cellName, valueOrFormula) getCell(cellName) -> int ``` Requirements: 1. `setCell` may assign either: - an integer value, such as `10`, or - a formula, such as `B1 + C1`. 2. `getCell` returns the current evaluated integer value of the requested cell. 3. If a referenced cell has not been assigned, treat its value as `0`. 4. When a cell is updated, future reads should reflect the updated dependencies. 5. Follow-up: detect circular dependencies between formulas and reject updates that would create a cycle. For example, the following should be rejected because it creates a cycle: ```text A1 = B1 + C1 C1 = A1 ``` Explain your data structures and implement the API.

Quick Answer: This question evaluates ability to design and implement data structures and algorithms for expression parsing, dependency tracking, incremental evaluation, and cycle detection in an in-memory spreadsheet.

Part 1: Evaluate Spreadsheet Cells Without Cycle Detection

You are given a sequence of spreadsheet operations to execute in order. Each cell stores either an integer literal or a formula string made of cell references and integer constants joined only by '+'. Unset referenced cells evaluate to 0. When a cell is updated, later reads of dependent cells must reflect the new value automatically. For this part, the input is guaranteed to contain no circular dependencies. Instead of building a class, write a function that processes all operations and returns the results of every GET operation in order.

Constraints

0 <= len(operations) <= 10^4
cellName consists of uppercase letters followed by digits, for example A1 or BC12
Integer literals fit in 32-bit signed range
Formulas contain only cell references, integer constants, and '+'
For this part, the operations never create a circular dependency

Examples

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

Expected Output: [10]

Explanation: A1 is assigned a literal value, so GET A1 returns 10.

Input: ([('SET', 'A1', 'B1 + C1 + 5'), ('GET', 'A1'), ('SET', 'B1', 3), ('GET', 'A1'), ('SET', 'C1', 'B1 + 2'), ('GET', 'A1')],)

Expected Output: [5, 8, 13]

Explanation: Unset cells count as 0 at first, then later updates to B1 and C1 change A1's evaluated value.

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

Expected Output: [4, 12]

Explanation: A1 depends on both B1 and C1, and C1 also depends on B1, so changing B1 affects both parts of A1.

Input: ([('GET', 'Z99')],)

Expected Output: [0]

Explanation: Edge case: an unset cell evaluates to 0.

Hints

Store each cell's raw content instead of eagerly updating every dependent cell.
When evaluating a GET, use DFS recursion with a per-query memo dictionary so repeated references are only computed once.

Part 2: Reject Circular Spreadsheet Formulas

Now extend the spreadsheet so that updates creating circular dependencies are rejected. A cell may still store either an integer literal or a '+' formula of cell references and constants. Unset referenced cells evaluate to 0. For a SET operation, if applying the new value or formula would create a dependency cycle, reject that update and leave the spreadsheet unchanged. Write a function that processes all operations and returns the result of every operation in order: SET returns True if accepted and False if rejected, while GET returns the current evaluated integer value.

Constraints

0 <= len(operations) <= 10^4
cellName consists of uppercase letters followed by digits
Integer literals fit in 32-bit signed range
Formulas contain only cell references, integer constants, and '+'
If a SET is rejected, the previous content of that cell must remain unchanged

Examples

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

Expected Output: [True, 10, True, 15]

Explanation: Both SET operations are valid. B1 evaluates to A1 + 5 = 15.

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

Expected Output: [True, True, False, 1, 0, 3]

Explanation: The third SET would create B1 -> C1 -> A1 -> B1, so it is rejected. B1 stays unset and therefore equals 0.

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

Expected Output: [True, False, 7]

Explanation: A direct self-reference is a cycle, so the second SET is rejected and A1 keeps its old value.

Input: ([('GET', 'Z9')],)

Expected Output: [0]

Explanation: Edge case: reading an unset cell returns 0.

Hints

Extract the referenced cells from a formula and think of them as directed edges from the assigned cell to its dependencies.
When setting cell X, the update is invalid exactly when some new dependency can already reach X in the current dependency graph.

Quick Overview

This question evaluates ability to design and implement data structures and algorithms for expression parsing, dependency tracking, incremental evaluation, and cycle detection in an in-memory spreadsheet.