Spreadsheet Formula Engine with Cycle Detection

Problem Statement

Implement an in-memory spreadsheet formula engine. The spreadsheet consists of cells identified by alphanumeric string IDs (e.g., "A1", "B2"). Cells can hold either integer literals or formulas that sum dependencies and integer constants.

Implement the Spreadsheet class with the following methods:

• set_cell(cell_id: str, expr: str) -> bool: Sets the contents of cell_id to expr. An expression is either:

  • An integer literal as a string (e.g., "10", "-3").
  • A formula starting with "=", consisting of cell IDs and/or integer literals separated by "+" without spaces (e.g., "=A1+B2", "=A1+5").

  If setting this expression would introduce a circular dependency (directly or indirectly), the update must be rejected: return False and preserve the cell's previous value. Otherwise, apply the update and return True.

• get_cell(cell_id: str) -> int: Returns the evaluated integer value of cell_id. If the cell has never been set, its default value is 0.

Class Interface

class Spreadsheet:
    def __init__(self):
        pass

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

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

Examples

Example 1

sheet = Spreadsheet()
sheet.set_cell("A1", "10")      # returns True
sheet.set_cell("B1", "20")      # returns True
sheet.set_cell("C1", "=A1+B1")  # returns True
sheet.get_cell("C1")            # returns 30

sheet.set_cell("A1", "15")      # returns True (updates A1)
sheet.get_cell("C1")            # returns 35 (reflects updated A1)

Example 2 (Cycle Detection)

sheet = Spreadsheet()
sheet.set_cell("A1", "=B1+1")   # returns True
sheet.set_cell("B1", "=C1+2")   # returns True
sheet.set_cell("C1", "=A1+3")   # returns False (creates cycle: A1 -> B1 -> C1 -> A1)
sheet.get_cell("C1")            # returns 0 (reverted/never set)

Constraints

• cell_id consists of 1 to 5 uppercase letters followed by 1 to 5 digits.
• Integer literals fit within a standard 32-bit signed integer range.
• Up to 10,000 calls combined across set_cell and get_cell.
• Expressions in formulas only use the "+" operator and contain no whitespace.