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
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.