Quick Overview

This question evaluates a candidate's ability to parse and evaluate assignment expressions, resolve inter-variable dependencies, and detect cycles or unsolvable references.

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.

Overview: 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

Hints

  1. Parse assignments into a map from variable name to its expression; let the last occurrence win.
  2. Use DFS with memoization to evaluate each variable once; keep a 'visiting' set to detect cycles.
  3. Scan expressions character-by-character: read optional '+'/'-' signs to determine the term's sign, then read either an integer literal or a variable name.

Loading coding console...

Show the approach

Approach

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.