Design an In-Memory Spreadsheet Engine

Problem Statement

Design an in-memory spreadsheet engine that allows users to set raw integer values, define formulas that reference other cells, and fetch cell values in O(1) time.

To ensure O(1) reads, cell values must be eagerly evaluated and cached. Whenever a cell's value or formula is updated, all dependent cells must be recomputed in a valid topological order so that no cell is evaluated with stale data.

If an update introduces a cyclic dependency (e.g., A1 depends on B1, and B1 is updated to depend on A1), the engine must reject the update, leave the existing spreadsheet state unmodified, and return False.

Implement the Spreadsheet class:

• set_cell(cell_id: str, expression: str) -> bool
  • cell_id: A string representing the cell coordinate (e.g., "A1", "C3").
  • expression: Either an integer string (e.g., "42", "-5") or a formula string beginning with "=" consisting of cell coordinates separated by "+" (e.g., "=A1+B2", "=C1"). References to unset cells evaluate to 0.
  • Returns True if the cell was updated successfully. Returns False without changing any spreadsheet state if the update would create a cycle.
• get_value(cell_id: str) -> int
  • Returns the current cached integer value of cell_id. If cell_id has never been set, returns 0.
  • Must run in O(1) time.

Class Interface

class Spreadsheet:
    def __init__(self):
        pass

    def set_cell(self, cell_id: str, expression: str) -> bool:
        pass

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

Examples

Example 1

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

sheet.set_cell("A1", "5")
print(sheet.get_value("A3"))  # Output: 25 (eagerly updated)

Example 2: Cycle Detection

sheet = Spreadsheet()
sheet.set_cell("A1", "=B1")
sheet.set_cell("B1", "=C1")
# Attempting to make C1 depend on A1 creates a cycle: A1 -> B1 -> C1 -> A1
success = sheet.set_cell("C1", "=A1")
print(success)                 # Output: False (state unchanged)

sheet.set_cell("C1", "100")
print(sheet.get_value("A1"))  # Output: 100

Constraints

• Cell IDs are alphanumeric strings (e.g., "A1" to "Z100").
• Integer values are in the range [-10^9, 10^9].
• Up to 2,000 total calls to set_cell and 100,000 calls to get_value.
• Formulas only use the + operator between cell references.