Spreadsheet Formulas with Dependency Updates

Problem Statement

Design an in-memory spreadsheet system that supports setting cell values, defining summation formulas across multiple cells, and retrieving cell values. When a cell's value changes, any cell whose formula depends on it must reflect the updated value upon subsequent retrieval.

Implement the Spreadsheet class:

• Spreadsheet(): Initializes the spreadsheet. All cells implicitly have a default value of 0 until explicitly set.
• set_val(cell: str, val: int) -> None: Assigns an integer val to cell. If cell previously held a formula, the formula and its dependencies are overwritten.
• set_sum(cell: str, formula_cells: list[str]) -> None: Sets cell to evaluate to the sum of the values of the cells listed in formula_cells. Note that formula_cells may contain duplicate cell identifiers; each appearance contributes its value independently (e.g., ["A1", "A1"] computes 2 * value("A1")). Overwrites any prior value or formula for cell.
• get(cell: str) -> int: Returns the current integer value of cell.

You may assume that no operations will introduce circular dependencies.

Method Signatures

class Spreadsheet:
    def __init__(self):
        pass

    def set_val(self, cell: str, val: int) -> None:
        pass

    def set_sum(self, cell: str, formula_cells: list[str]) -> None:
        pass

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

Example

sheet = Spreadsheet()
sheet.set_val("A1", 10)
sheet.set_val("B1", 20)
sheet.set_sum("C1", ["A1", "B1", "A1"])  # C1 = 10 + 20 + 10 = 40
assert sheet.get("C1") == 40

sheet.set_val("A1", 5)                   # C1 should now be 5 + 20 + 5 = 30
assert sheet.get("C1") == 30

sheet.set_sum("D1", ["C1", "B1"])        # D1 = 30 + 20 = 50
assert sheet.get("D1") == 50

sheet.set_val("C1", 100)                 # C1 is now a static value, overwriting formula
assert sheet.get("D1") == 120            # D1 = 100 + 20 = 120
assert sheet.get("A1") == 5

Constraints

• cell strings consist of uppercase English letters followed by digits (e.g., "A1", "Z99").
• -10^6 <= val <= 10^6
• 1 <= len(formula_cells) <= 1000
• At most 20,000 total calls to set_val, set_sum, and get combined.
• No cyclic dependencies will be introduced.

Edge Cases

• Referencing a cell in formula_cells that has never been set should treat its value as 0.
• Overwriting a formula cell with a direct value must sever its old dependency graph edges so it no longer receives updates from previously referenced cells.