Evaluate dependent variable expressions
Company: Instacart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
Given a target variable name and a list of assignment strings of the form 'Ti = expression' where the expression is either a number, a single variable, or arithmetic (+, −) over variables/numbers, compute the numeric value of the target variable. Extend to handle expressions that reference other variables recursively; detect cycles or unsolvable references and report an error.
Quick Answer: This question evaluates a candidate's ability to parse and evaluate assignment expressions, resolve inter-variable dependencies, and detect cycles or unsolvable references.
You are given a target variable name and a list of assignment strings of the form 'name = expression'. Each expression consists only of integer literals and variable names combined using '+' and '-' with optional whitespace; no parentheses or other operators exist. A unary '+' or '-' may precede any term. Variable names match [A-Za-z_][A-Za-z0-9_]* and are case-sensitive. Evaluate the target variable by recursively resolving dependencies. If a variable is assigned multiple times, the last assignment takes precedence. Return the integer value of the target if it can be computed. Return 'ERROR' if there is a cyclic dependency, if the target or any referenced variable is undefined, or if an expression is syntactically invalid.
Constraints
- 1 <= len(assignments) <= 10^4
- Total length of all assignment strings <= 2 * 10^5
- Variable names match [A-Za-z_][A-Za-z0-9_]*
- Expressions contain only integers, variable names, '+', '-', and spaces; no parentheses
- A leading '+' or '-' may appear before any term (number or variable)
- If a variable is assigned multiple times, the last assignment is used
- Return 'ERROR' on cyclic dependencies or undefined variables
Examples
Input:
Expected Output: ERROR
Input:
Expected Output: ERROR
Solution
import re
class EvaluationError(Exception):
pass
VAR_RE = re.compile(r'^[A-Za-z_][A-Za-z0-9_]*$')
def evaluate_target(target: str, assignments: list[str]) -> int | str:
# Build mapping: last assignment wins
mapping: dict[str, str] = {}
for line in assignments:
if not isinstance(line, str) or "=" not in line:
return "ERROR"
left, right = line.split("=", 1)
var = left.strip()
expr = right.strip()
if not var or not VAR_RE.match(var):
return "ERROR"
mapping[var] = expr
memo: dict[str, int] = {}
visiting: set[str] = set()
def eval_var(name: str) -> int:
if name in memo:
return memo[name]
if name in visiting:
raise EvaluationError("cycle")
if name not in mapping:
raise EvaluationError("undefined")
visiting.add(name)
try:
val = eval_expr(mapping[name])
finally:
visiting.remove(name)
memo[name] = val
return val
def eval_expr(expr: str) -> int:
i = 0
n = len(expr)
total = 0
saw_term = False
def skip_spaces():
nonlocal i
while i < n and expr[i].isspace():
i += 1
while True:
skip_spaces()
if i >= n:
if not saw_term:
raise EvaluationError("empty expr")
break
sign = 1
# Read one or more leading signs for the next term
while i < n and expr[i] in "+-":
if expr[i] == '-':
sign *= -1
i += 1
skip_spaces()
if i >= n:
raise EvaluationError("trailing operator")
c = expr[i]
if c.isdigit():
num = 0
while i < n and expr[i].isdigit():
num = num * 10 + (ord(expr[i]) - 48)
i += 1
total += sign * num
saw_term = True
elif c.isalpha() or c == '_':
j = i + 1
while j < n and (expr[j].isalnum() or expr[j] == '_'):
j += 1
name = expr[i:j]
val = eval_var(name)
total += sign * val
i = j
saw_term = True
else:
raise EvaluationError("invalid char")
skip_spaces()
if i >= n:
break
if expr[i] not in "+-":
raise EvaluationError("missing operator")
# loop continues to read the next signed term
return total
try:
return eval_var(target)
except EvaluationError:
return "ERROR"
Explanation
Build a map from variable names to their expressions (last assignment wins). Evaluate the target using DFS with memoization: to compute a variable, parse and evaluate its expression. During evaluation, when encountering another variable, recursively evaluate it. Maintain a 'visiting' set of variables currently in the recursion stack to detect cycles. The expression parser scans characters, accumulates optional leading '+'/'-' signs as a multiplier, then reads either an integer literal or a variable name. Any reference to an undefined variable or the presence of a cycle raises an error, causing the function to return 'ERROR'.
Time complexity: O(A + L), where A is the number of assignments and L is the total length of all expressions (each variable evaluated once due to memoization).. Space complexity: O(A) for the mapping, memoization, and recursion stack..
Hints
- Parse assignments into a map from variable name to its expression; let the last occurrence win.
- Use DFS with memoization to evaluate each variable once; keep a 'visiting' set to detect cycles.
- Scan expressions character-by-character: read optional '+'/'-' signs to determine the term's sign, then read either an integer literal or a variable name.