Katkat
Back

Implement Spreadsheet Cell Updates

HarveySoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manage a directed graph of dependencies and implement a topological update mechanism to recompute spreadsheet cell values efficiently.

Spreadsheet Cell Updates

Design a system to represent a spreadsheet grid and handle cell updates. A cell can contain either a static numeric value or a formula. Formulas reference other cells (e.g., "=A1+B2") and must be recomputed whenever their dependencies change.

Requirements

Implement a class Spreadsheet with the following methods:

  1. set_cell(cell_id, value): Sets the content of a cell. If value is a number (e.g., 10), the cell is a constant. If it starts with '=', it is a formula that performs addition on other cell IDs. If a formula is invalid or contains a cycle, the cell value should be None.
  2. get_value(cell_id): Returns the current numeric value of the cell. If the cell is not set or its formula cannot be evaluated, return None.

Constraints

  • cell_id is a string like "A1", "B12", etc.
  • Formulas only use the '+' operator and cell references.
  • The spreadsheet size is effectively infinite, but the number of operations is up to 10^4.

Examples

# Example 1
ss = Spreadsheet()
ss.set_cell("A1", "10")
ss.set_cell("A2", "=A1+5")
print(ss.get_value("A2")) # Output: 15

# Example 2
ss.set_cell("A1", "=A2+1")
ss.set_cell("A2", "=A1+1")
print(ss.get_value("A1")) # Output: None (Cycle detected)

Edge Cases

  • Circular dependencies that are only formed after updating an existing cell.
  • Referencing a cell that has not been set yet (treat as 0 or handle as error).

Hints

Hint 1

Represent the spreadsheet as a directed graph where an edge exists from cell A to cell B if B depends on A.

Hint 2

Use a topological sort or a recursive dependency resolution approach with a 'visited' set to detect cycles during evaluation.

Hint 3

When a cell's value is updated, maintain a list of 'dependent' cells to trigger cascading re-evaluations only when necessary.

Follow-up questions

  • How would you optimize the re-evaluation process to avoid redundant calculations if multiple cells depend on the same underlying value?
  • How would you extend this system to support more complex operations like multiplication or built-in functions like SUM?
  • What changes are required if the system needs to handle multi-threaded updates where multiple users are editing the sheet simultaneously?