Katkat
Back

Evaluate a Variable from Chained Assignments with +/- Expressions and Cycle Detection

InstacartSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

A coding problem that evaluates a target variable from chained assignments such as T1 = T2 and T2 = 5, then extends to right-hand sides with plus and minus and to inputs that may contain cycles. It tests parsing, memoized dependency resolution and cycle detection that does not flag shared dependencies.

Given a set of assignments and a target variable, return the value of the target. For example, with the target T1 and the assignments

T1 = T2
T2 = 5

the answer is 5. The problem is then extended twice.

Clarifying Questions

  • What is the input format: a list of strings such as T1 = T2? Is whitespace around = and operators optional?
  • Are all values integers, and can a literal be negative?
  • Can a variable be assigned more than once, and if so, which assignment wins?
  • What should happen when the target, or a variable it depends on, is never assigned?

Part 1 — Follow a chain of assignments

Each right-hand side is either an integer literal or a single variable name. Return the value of the target.

What This Part Should Cover

  • Parsing the assignments into a lookup structure.
  • Resolving a chain of references down to a value, with memoization for repeated lookups.
  • Behavior for a variable that is never assigned.

Part 2 — Expressions with + and -

A right-hand side can now be an expression that combines variables and integers with + and -, for example:

T1 = T2 + 3 - T3
T2 = 5
T3 = T2 - 1

Here T1 evaluates to 4.

Clarifying Questions for this Part

  • Can an expression start with a sign, as in T1 = -T2, or contain two operators in a row?
  • Can expressions contain parentheses or other operators?

What This Part Should Cover

  • A tokenizer that tolerates missing whitespace (T2+3) and rejects malformed expressions (T2 3, T2 +).
  • Evaluating a variable as a signed sum of its operands, without recomputing shared dependencies.
  • Complexity in terms of the number of variables and the total length of the expressions.

Part 3 — Cycles

The assignments may now contain a cycle, for example:

A = B + 1
B = C
C = A - 2

Detect cycles instead of looping forever.

Clarifying Questions for this Part

  • When a cycle exists, should the evaluation fail only if the target depends on the cycle, or should the whole input be rejected?
  • Should the error name the variables that form the cycle?

What This Part Should Cover

  • Distinguishing a real cycle from a variable reached twice through different paths.
  • The scope of the check (only what the target depends on, or the whole input) and a useful error report.
  • Stack depth on very long chains of assignments.

Hints

Hint 1

Follow the references: Each variable points at a number or at exactly one other variable. Think about the lookup structure, and about what resolving the same variable a second time should cost.

Hint 2

Tokens before arithmetic: Split each right-hand side into operands and signs before evaluating anything; the value of a variable is then built from the values of its operands.

Hint 3

Visited is not enough: A variable can legitimately be reached twice through different paths. What extra state tells a shared dependency apart from a loop back to a variable that is still being resolved?

Follow-up questions

  • If assignments change one at a time and the target is queried after each change, how would you avoid re-evaluating everything?
  • How would you add multiplication and parentheses?
  • How would you evaluate every variable at once and list all variables that are on, or depend on, a cycle?
  • How would you handle values that overflow a 64-bit integer in a language without arbitrary-precision integers?