Katkat
Back

Implement an Integer Spreadsheet with Formulas

HarveySoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Design an in-memory integer spreadsheet supporting cell assignments, additive formulas with nested references, and dynamic recalculation of acyclic dependency chains.

Problem Statement

Implement an in-memory integer spreadsheet engine that supports literal values, additive formulas referencing other cells, replacement updates, and evaluation of dependent cells.

Your Spreadsheet class should support the following operations:

  • set_cell(cell: str, expr: str) -> None: Sets the contents of the given cell. The expression expr can be:
    • An integer literal (e.g., "42", "-5").
    • An additive formula starting with "=" followed by terms separated by "+" (e.g., "=A1+B2+10"). Each term in the formula is either a cell reference (e.g., "A1") or an integer literal.
    • Overwriting an existing cell replaces its previous definition completely.
  • get_value(cell: str) -> int: Computes and returns the current integer value of the cell.
    • If the cell has not been explicitly set, its value defaults to 0.
    • Any unset cell referenced within a formula also evaluates to 0.
    • All formulas are guaranteed to be acyclic (no circular dependencies).

Interface

class Spreadsheet:
    def __init__(self):
        pass

    def set_cell(self, cell: str, expr: str) -> None:
        pass

    def get_value(self, cell: str) -> int:
        pass

Examples

Example 1

sheet = Spreadsheet()
sheet.set_cell("A1", "10")
sheet.set_cell("A2", "20")
sheet.set_cell("B1", "=A1+A2+5")

print(sheet.get_value("B1"))  # Output: 35 (10 + 20 + 5)
print(sheet.get_value("C1"))  # Output: 0 (unset cell defaults to 0)

# Updating a cell dynamically reflects in dependent cells
sheet.set_cell("A1", "5")
print(sheet.get_value("B1"))  # Output: 30 (5 + 20 + 5)

Example 2

sheet = Spreadsheet()
sheet.set_cell("A1", "=B1+5")
print(sheet.get_value("A1"))  # Output: 5 (B1 is unset, so it evaluates to 0)

sheet.set_cell("B1", "15")
print(sheet.get_value("A1"))  # Output: 20 (B1 is now 15)

# Replacing formula with a literal
sheet.set_cell("A1", "100")
print(sheet.get_value("A1"))  # Output: 100

Constraints

  • cell coordinates consist of 1–3 uppercase letters followed by 1–4 digits (e.g., "A1", "BC102").
  • Integer literals in inputs fit within standard 32-bit signed integers.
  • Formula chains are strictly acyclic and can reach up to 1,000 cells deep.
  • Up to 10,000 total calls to set_cell and get_value.

Hints

Hint 1

Store expressions in their raw or parsed form in a hash map, and consider whether to evaluate lazily upon get_value or eagerly upon set_cell.

Hint 2

Since dependency chains can be up to 1,000 cells deep, a recursive DFS for evaluation must be careful with Python's default recursion limit or be implemented iteratively / with memoization during a single get_value call.

Hint 3

If updating frequently but reading occasionally, lazy evaluation with per-call memoization is often simpler and avoids maintaining complex reverse dependency graphs.

Follow-up questions

  • How would you detect and handle circular dependencies (cycles) if the acyclic guarantee were removed?
  • If reads vastly outnumber writes, how would you design an eager caching system with cache invalidation across the dependency graph?
  • How would you extend the expression parser to support full arithmetic operators (+, -, *, /) and parentheses while maintaining correct operator precedence?