Spreadsheet Formula Dependencies

Maintain an initially empty in-memory spreadsheet. Each cell holds either an integer or a formula referring to other cells. Process operations in order and return one string for every operation.

For this exercise, each formula is one binary expression. Its left and right operands are independently either a cell identifier or an integer literal. Formulas can be nested through cell references.

• ["SET", cell, value] replaces the cell with the integer value and returns "OK".
• ["FORMULA", cell, left, operator, right] proposes replacing the cell with left operator right. The operator is +, -, *, or /. Accept the replacement and return "OK" unless it introduces a direct or indirect circular reference. In that case, return "CYCLE" and leave the spreadsheet completely unchanged.
• ["GET", cell] returns the cell's current value as a decimal string. A cell that has never been assigned has value 0. Values must reflect every earlier accepted update, including updates to indirect dependencies.

Arithmetic is integer arithmetic. Division truncates toward zero. Division by zero, or a reference to a cell whose evaluation encounters division by zero, makes that evaluation return "ERROR". Such a formula may be stored successfully; the error is reported when its value is read. A later update can repair it.

Using the same cell more than once in a formula is legal and is not itself a cycle. Replacing a formula removes its old dependency relationships. Rejected updates must not change definitions or cached values.

In a read-heavy workload, how can per-query memoization be improved with a persistent cache and reverse dependencies? Explain which cached cells must be invalidated after an accepted update and how overwriting a formula changes the dependency graph.