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 Fuse Energy.

What role is this question designed for?

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

Implement spreadsheet cells with formulas | Fuse Energy Coding Question

Quick Overview

This question evaluates proficiency in data structures and algorithms for dependency management, reactive computation, cycle detection, and state versioning (undo), assessing the ability to reason about how cells, formulas, and ranges interact under updates.

Implement spreadsheet cells with formulas

Company: Fuse Energy

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design an in-memory spreadsheet that supports these operations on cells such as `A1`, `B2`, and ranges such as `A1:B2`: - `Set(cell, value)`: assign an integer literal to a cell. - `Sum(dest, refs)`: assign `dest` to a formula equal to the sum of all referenced cells. Each item in `refs` is either a single cell like `"B2"` or a rectangular range like `"A1:B2"`. - `Get(cell)`: return the current value of the cell. - `Undo()`: revert the most recent successful write operation. Both `Set` and `Sum` count as write operations. Rules: 1. Cells that have never been assigned should be treated as `0`. 2. Formula cells are reactive: if a referenced cell changes later, `Get` on the formula cell should reflect the new value. 3. Duplicate references count multiple times. 4. A `Sum` operation is invalid if it would introduce a cycle in the dependency graph. In that case, it should raise an error and leave the spreadsheet unchanged. Example: ```text Set("A1", 1) Set("B2", 2) Sum("D1", ["A1:B2", "B2"]) Get("D1") // 5, because A1 + A2 + B1 + B2 + B2 = 1 + 0 + 0 + 2 + 2 Set("A1", 2) Get("D1") // 6 ``` Cycle examples: ```text Sum("A1", ["A1", "B1"]) // invalid: direct self-cycle Sum("A1", ["B1"]) // valid Sum("B1", ["A1"]) // invalid if A1 already depends on B1 Sum("B3", ["B3"]) // invalid ``` Implement the data structure and explain how you would track dependencies, detect cycles, and support `Undo()` efficiently.

Quick Answer: This question evaluates proficiency in data structures and algorithms for dependency management, reactive computation, cycle detection, and state versioning (undo), assessing the ability to reason about how cells, formulas, and ranges interact under updates.

Design an in-memory spreadsheet that supports integer cells, reactive sum formulas, cycle rejection, and undo. Cells are named with uppercase column letters followed by a positive row number, such as "A1" or "B2". Ranges such as "A1:B2" include every cell in the rectangle. You are given a batch of operations and must return the observable outputs. Operations are encoded as lists of strings: - ["Set", cell, value]: assign an integer literal to cell. This removes any previous formula in that cell. - ["Sum", dest, ref1, ref2, ...]: assign dest to a formula equal to the sum of all referenced cells. Each ref is either a single cell like "B2" or a rectangular range like "A1:B2". - ["Get", cell]: read the current value of cell. - ["Undo"]: revert the most recent successful write operation. Both Set and valid Sum operations count as writes. Rules: 1. Cells that have never been assigned are treated as 0. 2. Formula cells are reactive: if a referenced cell changes later, Get on the formula cell reflects the new value. 3. Duplicate references count multiple times, including duplicates caused by overlapping ranges. 4. A Sum operation is invalid if it would introduce a cycle in the dependency graph. For this batch interface, report this by appending "ERROR" to the returned output list and leaving the spreadsheet unchanged. Invalid Sum operations are not added to the undo history. 5. Undo on an empty history does nothing.

Constraints

0 <= len(operations) <= 2000
Cell names contain uppercase letters followed by a positive row number, such as "A1" or "AA27"
Set values are integers in the range [-10^9, 10^9]
The total number of cells expanded from all ranges across all Sum operations is at most 200000
All input operations are syntactically valid

Examples

Input: ([] ,)

Expected Output: []

Explanation: No operations produce no observable output.

Input: ([["Get", "Z99"], ["Undo"], ["Get", "A1"]],)

Expected Output: ["0", "0"]

Explanation: Unassigned cells read as 0. Undo with no successful writes is a no-op.

Input: ([["Set", "A1", "1"], ["Set", "B2", "2"], ["Sum", "D1", "A1:B2", "B2"], ["Get", "D1"], ["Set", "A1", "2"], ["Get", "D1"]],)

Expected Output: ["5", "6"]

Explanation: A1:B2 contributes A1 + A2 + B1 + B2, and B2 is referenced again. Initially the sum is 1 + 0 + 0 + 2 + 2 = 5. After A1 becomes 2, the reactive formula reads 6.

Input: ([["Set", "A1", "10"], ["Sum", "A1", "A1", "B1"], ["Get", "A1"], ["Get", "B1"]],)

Expected Output: ["ERROR", "10", "0"]

Explanation: The Sum would make A1 directly depend on itself, so it is rejected and A1 remains the literal value 10.

Input: ([["Sum", "A1", "B1"], ["Sum", "B1", "A1"], ["Get", "A1"], ["Get", "B1"], ["Set", "B1", "7"], ["Get", "A1"]],)

Expected Output: ["ERROR", "0", "0", "7"]

Explanation: A1 depending on B1 is valid. Making B1 depend on A1 would create the cycle B1 -> A1 -> B1, so it is rejected. Later setting B1 to 7 makes A1's formula evaluate to 7.

Input: ([["Set", "A1", "3"], ["Set", "B1", "4"], ["Sum", "C1", "A1", "B1"], ["Get", "C1"], ["Set", "A1", "10"], ["Get", "C1"], ["Undo"], ["Get", "C1"], ["Undo"], ["Get", "C1"], ["Undo"], ["Get", "B1"], ["Get", "A1"]],)

Expected Output: ["7", "14", "7", "0", "0", "3"]

Explanation: C1 is reactive. Undo first restores A1 from 10 to 3, then removes the formula from C1, then removes the literal assignment to B1.

Input: ([["Set", "A1", "-3"], ["Set", "A2", "5"], ["Sum", "B1", "A1:A2", "A1"], ["Get", "B1"]],)

Expected Output: ["-1"]

Explanation: The range A1:A2 contributes -3 + 5, and A1 is counted again, giving -3 + 5 - 3 = -1.

Input: ([["Set", "A1", "5"], ["Set", "B1", "2"], ["Sum", "A1", "B1"], ["Get", "A1"], ["Sum", "B1", "A1"], ["Undo"], ["Get", "A1"], ["Get", "B1"]],)

Expected Output: ["2", "ERROR", "5", "2"]

Explanation: A1 is replaced by a formula depending on B1. The attempted B1 formula would create a cycle, so it is rejected and not added to history. Undo therefore reverts the valid Sum on A1, restoring literal 5.

Hints

Store formula dependencies as a graph from a formula cell to the cells it references. Keep reference counts because duplicates must contribute multiple times.
To check whether assigning dest to depend on refs creates a cycle, ask whether any referenced cell can already reach dest through existing formula dependencies.

Quick Overview