Quick Overview

A coding task that evaluates a list of variable assignments built from integers, other variables, addition and subtraction, where definitions may appear in any order. It asks for every resolvable value and flags variables that are undefined, cyclic or dependent on unresolvable ones, testing dependency resolution and cycle handling.

Resolve Variable Assignments With Addition and Subtraction, Flagging Unresolvable Ones

Company: Applied Intuition

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a list of assignment lines. Each line assigns to a variable either an integer or an expression that adds and subtracts integers and other variables. Determine the value of every variable that can be resolved, and identify every variable that cannot. The report gives the input of Example 1 without its expected output, and does not say how a variable assigned twice, a variable that is never assigned, or a cycle is treated; this version fixes those rules in Rules below. ### Function Signature ```python def resolve_variables(lines: list[str]) -> list[str]: ``` ### Rules - Every line has the form `name = term`, or `name = term op term ... op term`, with single spaces between tokens. Each `op` is `+` or `-`, and each term is a variable name or a non-negative integer literal. - The lines are definitions, not statements executed in order: a line may use a variable that is defined on a later line. - If several lines assign the same variable, only the last of those lines defines it, and the earlier ones are ignored. For example, with the line `x = 5` followed later by `x = x + 1`, the definition of x is `x = x + 1`, so x refers to itself and cannot be resolved. - A variable is resolved when it has a definition and every variable in that definition is resolved. Its value is the definition evaluated from left to right with exact integer arithmetic. - A variable cannot be resolved if it has no definition (it appears only on right-hand sides), if its definition depends on itself directly or through a cycle of definitions, or if its definition uses a variable that cannot be resolved. - Return one string for each distinct variable name that appears anywhere in `lines`, on either side of `=`, sorted by name in ascending lexicographic order. Each string has the form `name = value`, where value is the resolved value in decimal with a leading `-` when negative, or the word `UNRESOLVED` when the variable cannot be resolved. ### Constraints - `1 <= len(lines) <= 10^4` - Every right-hand side has between 1 and 50 terms, and all lines together have at most `10^5` terms. - A variable name is 1 to 10 lowercase English letters. - An integer literal is a decimal number from 0 to `10^9`, written without a sign and without leading zeros. - For every variable that can be resolved, its value and every left-to-right partial result while evaluating its definition lie within `[-10^15, 10^15]`. - Chains of definitions can be as long as the number of lines. - Every line is well formed. ### Examples **Example 1** ```text Input: lines = ["a = b + c", "d = d + 5", "c = 5", "d = 10"] Output: ["a = UNRESOLVED", "b = UNRESOLVED", "c = 5", "d = 10"] ``` The later line `d = 10` replaces `d = d + 5`, so d is 10, and c is 5. b is never assigned, so b cannot be resolved, and neither can a, which uses it. **Example 2** ```text Input: lines = ["x = y - 3", "y = 10 + z", "z = 2", "w = x - y + 1"] Output: ["w = -2", "x = 9", "y = 12", "z = 2"] ``` z is 2, so y = 10 + 2 = 12 and x = 12 - 3 = 9, even though x's line comes before y's. Then w = 9 - 12 + 1 = -2. **Example 3** ```text Input: lines = ["p = q + 1", "q = p - 1", "r = 4", "s = r + p", "t = 7 - 7"] Output: ["p = UNRESOLVED", "q = UNRESOLVED", "r = 4", "s = UNRESOLVED", "t = 0"] ``` p and q depend on each other, so neither can be resolved, and s uses p. t uses no variables and equals 0.

Overview: A coding task that evaluates a list of variable assignments built from integers, other variables, addition and subtraction, where definitions may appear in any order. It asks for every resolvable value and flags variables that are undefined, cyclic or dependent on unresolvable ones, testing dependency resolution and cycle handling.

Read the full Applied Intuition Software Engineer interview experience this question came from

You are given a list of assignment lines. Each line assigns to a variable either an integer or an expression that adds and subtracts integers and other variables. Determine the value of every variable that can be resolved, and identify every variable that cannot. Implement `resolve_variables(lines)`, which returns the report described below. ### Rules - Every line has the form `name = term`, or `name = term op term ... op term`, with single spaces between tokens. Each `op` is `+` or `-`, and each term is a variable name or a non-negative integer literal. - The lines are definitions, not statements executed in order: a line may use a variable that is defined on a later line. - If several lines assign the same variable, only the last of those lines defines it, and the earlier ones are ignored. For example, with the line `x = 5` followed later by `x = x + 1`, the definition of `x` is `x = x + 1`, so `x` refers to itself and cannot be resolved. - A variable is resolved when it has a definition and every variable in that definition is resolved. Its value is the definition evaluated from left to right with exact integer arithmetic. - A variable cannot be resolved if it has no definition (it appears only on right-hand sides), if its definition depends on itself directly or through a cycle of definitions, or if its definition uses a variable that cannot be resolved. - Return one string for each distinct variable name that appears anywhere in `lines`, on either side of `=`, sorted by name in ascending lexicographic order. Each string has the form `name = value`, where `value` is the resolved value in decimal with a leading `-` when negative, or the word `UNRESOLVED` when the variable cannot be resolved. Resolved values and the partial results while evaluating them can reach `10^15` in absolute value, which exceeds `2^31 - 1`: use 64-bit integers (`long` in Java, `long long` in C++). ### Examples **Example 1** ```text Input: lines = ["a = b + c", "d = d + 5", "c = 5", "d = 10"] Output: ["a = UNRESOLVED", "b = UNRESOLVED", "c = 5", "d = 10"] ``` The later line `d = 10` replaces `d = d + 5`, so `d` is 10, and `c` is 5. `b` is never assigned, so `b` cannot be resolved, and neither can `a`, which uses it. **Example 2** ```text Input: lines = ["x = y - 3", "y = 10 + z", "z = 2", "w = x - y + 1"] Output: ["w = -2", "x = 9", "y = 12", "z = 2"] ``` `z` is 2, so `y = 10 + 2 = 12` and `x = 12 - 3 = 9`, even though `x`'s line comes before `y`'s. Then `w = 9 - 12 + 1 = -2`. ### Constraints - `1 <= len(lines) <= 10^4` - Every right-hand side has between 1 and 50 terms, and all lines together have at most `10^5` terms. - A variable name is 1 to 10 lowercase English letters. - An integer literal is a decimal number from 0 to `10^9`, written without a sign and without leading zeros. - For every variable that can be resolved, its value and every left-to-right partial result while evaluating its definition lie within `[-10^15, 10^15]`. - Chains of definitions can be as long as the number of lines. - Every line is well formed.

Constraints

  • 1 <= len(lines) <= 10^4
  • Every right-hand side has between 1 and 50 terms, and all lines together have at most 10^5 terms.
  • A variable name is 1 to 10 lowercase English letters.
  • An integer literal is a decimal number from 0 to 10^9, written without a sign and without leading zeros.
  • For every variable that can be resolved, its value and every left-to-right partial result while evaluating its definition lie within [-10^15, 10^15].
  • Chains of definitions can be as long as the number of lines.
  • Every line is well formed.

Examples

Input: (['a = b + c', 'd = d + 5', 'c = 5', 'd = 10'],)

Expected Output: ['a = UNRESOLVED', 'b = UNRESOLVED', 'c = 5', 'd = 10']

Explanation: Example 1: the later d = 10 replaces the self-referencing d = d + 5; b is never assigned, so a, which uses b, is unresolved too.

Input: (['x = y - 3', 'y = 10 + z', 'z = 2', 'w = x - y + 1'],)

Expected Output: ['w = -2', 'x = 9', 'y = 12', 'z = 2']

Explanation: Example 2: forward references; strict left-to-right evaluation gives w = 9 - 12 + 1 = -2 (grouping from the right would give -4).

Hints

  1. Only the last line that assigns a name counts as its definition, yet every name that appears on any line, including lines that were overridden, must still be reported.
  2. Whether a variable can be resolved depends only on the variables named in its own definition, and a variable can reach itself through other definitions.
  3. Chains of definitions can be as long as the number of lines, so make sure your approach does not break on very deep dependencies.

Loading coding console...

Show the approach

Approach

Parse every line by splitting on single spaces: token 0 is the assigned name and the right-hand side alternates terms and operators. Store each right-hand side in a map keyed by name, overwriting earlier entries so that only the last line for a name is its definition, and collect every name that appears on either side of any line (overridden lines still contribute names).

Resolve with an iterative depth-first search over the definition graph using three states: unvisited, in progress (on the explicit stack) and done. Visiting a variable walks the variable terms of its definition in order. An unvisited term is pushed and finished first. A term that is still in progress means the current variable lies on a cycle through that term, and a term already finished as unresolved poisons the current variable; either way the current variable finishes as UNRESOLVED. A variable with no definition finishes as UNRESOLVED immediately. When every variable term has finished resolved, the definition is evaluated strictly from left to right and the variable finishes with that value.

Correctness, by induction on finishing order: a variable finished as resolved has a definition whose variables all finished resolved earlier, so it is resolved and its value is the left-to-right evaluation. A variable finished as UNRESOLVED either has no definition, uses a variable already shown unresolvable, or uses a variable that is still on the stack; in the last case that variable reaches the current one along the stack path, so the current variable depends on itself and cannot be resolved. The verdicts therefore do not depend on which variable the search starts from, and a variable that is merely reachable from a cycle (but does not depend on it) is still resolved.

The explicit stack avoids recursion-depth failures on definition chains as long as 10^4 lines. Each term is examined at most twice (before and after its dependency finishes), and the report lists the distinct names in sorted order. Edge cases: direct self-reference such as x = x, names that occur only on right-hand sides or only in overridden lines, a variable shared by several definitions (not a cycle), and values up to 10^15 in absolute value, which need 64-bit integers in Java and C++ (JavaScript numbers are exact below 2^53).

Time complexity:
O(T + V log V), where T is the total number of terms and V the number of distinct names
Space complexity:
O(T + V)