Evaluate named arithmetic expressions whose variables can depend on definitions appearing later in the input. Extend the evaluator to distinguish unresolved variables from cyclic dependencies.

Requirements - Accept a list of assignment expressions and return a mapping from every variable name to its computed value. Definitions can appear after their first use. - Support expressions containing more than one operator and chains of dependencies. The initial examples use addition; a JavaScript configuration-parser version also discusses subtraction. - Detect a dependency on a variable that is never defined. In the backend screen, print Unresolvable equations. - Detect a cycle between variable definitions. In that screen, print Cyclic Dependency. - A separate onsite follow-up asks how multiplication and division would be supported; an explanation was sufficient for that extension. Examples The backend follow-up includes these failure cases: Notes - Whitespace handling matters: trailing spaces in names and expressions without spaces around operators can break token lookup. - Evaluating only one pass can leave valid dependency chains unfinished. Undefined names and cycles must not cause an endless loop. - One backend interview left less than ten minutes for both error-handling extensions. In another screen, a new dependency-chain test arrived only after the initial tests passed. - Confirm the accepted operators and error-output contract before implementing extensions; they differ across versions. Solution approach - Parse all assignments into a definition map before evaluating any variable. Tokenize names and numeric literals according to the agreed grammar rather than relying on spaces or host-language eval. - Use depth-first evaluation with unvisited, visiting, and completed states. A missing definition is unresolved; an edge to a visiting variable is a cycle; completed values are memoized. A variable may occur more than once in an expression, so sum its contribution each time even when its value is cached. If an input has both error types, clarify which error takes precedence. - With L input tokens, V variables, and E variable references, parsing plus memoized evaluation takes O(L + V + E) work under constant-time arithmetic and hash lookup. A deep chain may require an explicit stack. Multiplication and division require a precedence-aware parser and an agreed division/error policy. Preparation - In 25 minutes, implement tokenization and dependency evaluation for the stated operators, then run both examples and both error cases. - In 10 minutes, add checks for whitespace, repeated variable references, a long dependency chain, and a self-cycle; explain how operator precedence would affect an extension.

Variable Expression Evaluation — Applied Intuition Interview Question

Requirements

Accept a list of assignment expressions and return a mapping from every variable name to its computed value. Definitions can appear after their first use.
Support expressions containing more than one operator and chains of dependencies. The initial examples use addition; a JavaScript configuration-parser version also discusses subtraction.
Detect a dependency on a variable that is never defined. In the backend screen, print Unresolvable equations.
Detect a cycle between variable definitions. In that screen, print Cyclic Dependency.
A separate onsite follow-up asks how multiplication and division would be supported; an explanation was sufficient for that extension.

Examples

input: ["foo = bar + 5", "bar = 2", "abc = 3"]
output: {"foo": 7, "bar": 2, "abc": 3}

input: ["g = abc + foo", "foo = bar + 5", "bar = 2", "abc = 3"]
output: {"g": 10, "foo": 7, "bar": 2, "abc": 3}

The backend follow-up includes these failure cases:

foo: bar + 3
bar: abc + pqr + 2
=> Unresolvable equations

foo: bar + 3
bar: foo + 2
=> Cyclic Dependency

Notes

Whitespace handling matters: trailing spaces in names and expressions without spaces around operators can break token lookup.
Evaluating only one pass can leave valid dependency chains unfinished. Undefined names and cycles must not cause an endless loop.
One backend interview left less than ten minutes for both error-handling extensions. In another screen, a new dependency-chain test arrived only after the initial tests passed.
Confirm the accepted operators and error-output contract before implementing extensions; they differ across versions.

Solution approach

Parse all assignments into a definition map before evaluating any variable. Tokenize names and numeric literals according to the agreed grammar rather than relying on spaces or host-language eval.
Use depth-first evaluation with unvisited, visiting, and completed states. A missing definition is unresolved; an edge to a visiting variable is a cycle; completed values are memoized. A variable may occur more than once in an expression, so sum its contribution each time even when its value is cached. If an input has both error types, clarify which error takes precedence.
With L input tokens, V variables, and E variable references, parsing plus memoized evaluation takes O(L + V + E) work under constant-time arithmetic and hash lookup. A deep chain may require an explicit stack. Multiplication and division require a precedence-aware parser and an agreed division/error policy.

Preparation

In 25 minutes, implement tokenization and dependency evaluation for the stated operators, then run both examples and both error cases.
In 10 minutes, add checks for whitespace, repeated variable references, a long dependency chain, and a self-cycle; explain how operator precedence would affect an extension.

Requirements

Examples

Notes

Solution approach

Preparation

Comments