Katkat
Back

Reactive Budget Notebook With Live Formulas and Cycle Rejection

OpenAISoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Build a small reactive calculator where named variables hold integers or formulas that reference other variables, values stay correct as inputs change, and any definition that would create a circular dependency is rejected. Tests graph modeling, cache invalidation, cycle detection, and writing tests live.

You are building the engine behind a personal-budget notebook. Each line defines a variable:

rent  = 1200
power = 90
bills = = rent + power + 15
left  = = 2000 - bills

Implement:

class Notebook:
    def define(self, name: str, expr: str) -> None: ...
    def value(self, name: str) -> int: ...

Expression grammar. Either an integer literal like "1200", or "=" followed by terms joined with + or -. A term is a non-negative integer or a variable name ([a-z_][a-z0-9_]*), optionally preceded by a unary -. Whitespace is ignored.

Semantics

  • value of a variable that was never defined is 0.
  • Redefining a variable replaces its formula; everything that depends on it, directly or through other variables, must reflect the change.
  • If a define would create a circular dependency (including self-reference), raise CycleError (a subclass of ValueError) and leave the notebook exactly as it was.
  • A syntax error raises ValueError and also changes nothing.

Part 1: Values and propagation

Make define and value work. Reads are far more frequent than writes, so avoid recomputing unchanged values. State the cost of each operation.

Part 2: Cycle rejection

Detect cycles before committing a write. Explain why your check is sufficient.

Part 3: Tests

Write a compact test suite that would convince a reviewer. Cover at least diamond-shaped dependencies, rewiring a formula so it no longer depends on something, undefined references, and rejected writes leaving no trace.

Example

define rent 1200; define power 90
define bills "= rent + power + 15"; define left "= 2000 - bills"
value("left")                 -> 695
define power 140
value("bills"), value("left") -> 1355, 645
define rent "= left - 5"      -> CycleError
value("rent"), value("left")  -> 1200, 645

Hints

Hint 1

Store the formula separately from the computed value. Keep both edge directions: what a variable reads, and who reads it.

Hint 2

Before the write the graph is acyclic, so any new cycle must pass through the variable being defined. Check whether any new reference can reach it.

Hint 3

On a write, clear cached values for the variable and everything reachable through 'read-by' edges; recompute lazily on the next read.

Hint 4

Do all validation (parse, cycle check) before mutating anything; that gives atomic rejection for free.

Follow-up questions

  • Add multiplication and parentheses. What changes in the parser and in evaluation?
  • Instead of rejecting cycles, store the formula and make every variable on the cycle read as an error. How do you implement that and undo it later?
  • Support `undo()` for the last define. What must you snapshot?
  • How would this change if 100 users edit the same notebook concurrently?