Katkat
Back

Incremental Variable Resolver for a Build Pipeline

HarveySoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Build an in-memory variable resolver for a CI configuration system in three stages: plain integer variables, expression variables that reference other variables, then cycle detection with recomputation limited to the affected dependents. Checks whether a candidate can grow a design incrementally, respect a correct computation order, and reason about a dependency graph under change.

Build a variable resolver for a CI pipeline configuration, in stages. Each stage adds a requirement on top of the previous one, and the full scope is meant to be a fair amount of work for a technical screen, so get each stage correct and runnable before moving to the next rather than designing the final version up front.

Variables are identified by name (any valid identifier string, case-sensitive). The resolver exposes two operations throughout:

class VariableResolver:
    def set_var(self, name: str, value) -> None: ...
    def get_var(self, name: str) -> int | None: ...

Clarifying questions worth asking

  • Can a variable be redefined, including switching it from a literal to an expression or back?
  • Can values be negative? Is there a defined range?
  • Should set_var raise on a cycle, or should get_var simply return None for anything caught in one?

Part 1 — Literal variables

set_var(name, value) stores an integer. get_var(name) returns the stored integer, or None if name was never set. No expressions exist yet; this stage should be a thin, fast-to-write wrapper around one dictionary — but pick a storage layout that won't need to be thrown away once expressions arrive.

Part 2 — Expression variables, full recompute

set_var now also accepts a string starting with =, meaning an expression: a sum of integer literals and other variable names, written with +, for example "=timeout_base+retry_padding+2". get_var returns the computed integer. If an expression references a variable that was never set, get_var returns None for it (and for anything that transitively depends on it). Cycles will not occur in this stage, and efficiency doesn't matter yet: recomputing every variable from scratch on every set_var call, so that get_var stays O(1), is an acceptable approach here.

Part 3 — Cycle detection and targeted recompute

Two new requirements:

  1. If a set_var call would introduce a cycle (directly or transitively through other expressions), raise ValueError and leave the resolver's existing state unchanged.
  2. Stop recomputing everything on every write. A set_var call should only recompute the variable itself and whatever transitively depends on it — not every variable in the resolver.
set_var("base_timeout", 5)
set_var("retry_timeout", "=base_timeout+10")
set_var("total_budget", "=retry_timeout+base_timeout+1")
get_var("total_budget")        # 21

set_var("base_timeout", 8)
get_var("retry_timeout")       # 18
get_var("total_budget")        # 27

State the time complexity of set_var and get_var in each stage.

Hints

Hint 1

Store every variable's kind (literal or expression) and its raw definition in a layout that stage 2 and stage 3 can both reuse without a rewrite.

Hint 2

For stage 2, before you can compute a variable's value you need every variable it reads to already have a value — that's a dependency order, not an arbitrary one.

Hint 3

For cycle detection, check whether the variable being defined is reachable from any of its own new dependencies before you commit the change, so a rejected definition never corrupts existing state.

Hint 4

For targeted recompute, you need the dependency graph in both directions: what a variable reads from, to detect cycles, and what reads from a variable, to know who to recompute when it changes.

Follow-up questions

  • How would you support subtraction and multiplication in expressions without breaking the dependency-extraction logic?
  • If `get_var` is called far more often than `set_var`, is there anything in stage 3's design you'd tune differently?
  • How would you report *which* chain of variables forms a cycle, not just that one exists, so the error message is actually actionable?
  • How would memory usage grow if thousands of variables formed a few very large dependency chains, and would anything here need to change?