Katkat
Back

Implement a Spreadsheet With Formulas

HarveyMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to model cell dependencies using a directed graph, handle topological sorting for re-evaluation, and identify circular references.

Spreadsheet Evaluation Engine

Design a simple spreadsheet engine that manages cells and evaluates their formulas. A cell can contain either a raw integer or a formula in the format "=A1+B2". For simplicity, formulas only support addition between two cell references (e.g., "=A1+B2").

Implement the following class:

class Spreadsheet:
    def set_cell(self, cell_id: str, value: str):
        """Sets the value of a cell. If value starts with '=', it is a formula."""

    def get_value(self, cell_id: str) -> int:
        """Returns the evaluated integer value of the cell."""

Requirements

  1. If a cell contains a formula, it must be evaluated recursively.
  2. If a dependency loop is detected (e.g., A1 depends on B1, B1 depends on A1), raise a ValueError.
  3. Assume cell IDs are in the format "LetterNumber" (e.g., "A1", "B10").

Examples

sheet = Spreadsheet()
sheet.set_cell("A1", "10")
sheet.set_cell("B1", "20")
sheet.set_cell("C1", "=A1+B1")
print(sheet.get_value("C1")) # Output: 30

sheet.set_cell("A1", "=B1")
sheet.set_cell("B1", "=A1")
sheet.get_value("A1") # Raises ValueError: Circular dependency

Constraints

  • Cell IDs range from A1 to Z99.
  • Formulas always follow the format "=Ref1+Ref2".
  • If a referenced cell has not been set, treat its value as 0.

Hints

Hint 1

Model the spreadsheet as a directed graph where each cell is a node and a dependency creates a directed edge.

Hint 2

Use Depth First Search (DFS) with a recursion stack to track visited nodes during evaluation to detect cycles.

Hint 3

Consider memoizing the results of `get_value` to improve performance, but ensure the cache is invalidated when a cell's formula is updated.

Follow-up questions

  • How would you modify your implementation to support subtraction or multiplication in formulas?
  • If the spreadsheet is large and cells are updated frequently, how could you optimize the re-evaluation process so that only affected cells are updated?
  • How would you handle a scenario where a formula references a cell that contains a non-integer string?