Evaluate arithmetic expression with variables
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement an expression evaluator for a string expr containing non-negative integers, variables (alphabetic names), operators +, -, *, /, parentheses '()' and spaces. Given a dictionary mapping variable names to integer values, compute the signed 64-bit result using standard operator precedence (*/ before +-), left-to-right associativity, and support unary +/-. Division truncates toward zero. The evaluator must run in O(L) time where L is the length of expr and use O(L) extra space. Return an error for invalid tokens or mismatched parentheses. Follow-ups: extend to exponentiation '^' (right-associative) and a function max(a,b).
Quick Answer: This question evaluates implementation skills for a linear-time expression parser and evaluator, covering tokenization, variable substitution, operator precedence and associativity (including unary +/−), parentheses handling, integer arithmetic semantics (division truncation), error detection, and adherence to O(L) time and space constraints.
Implement an expression evaluator. You are given a string `expr` containing non-negative integers, variables (alphabetic names), the operators `+ - * /`, parentheses `()`, and spaces, together with a dictionary `variables` mapping each variable name to an integer value.
Compute and return the result as a signed 64-bit integer using:
- Standard operator precedence: `*` and `/` bind tighter than `+` and `-`.
- Left-to-right associativity for operators of equal precedence.
- Unary `+` and `-` (e.g. `-a + 5`, `+-+5`).
- Integer division that truncates toward zero (so `-7 / 2 == -3`, not `-4`).
- Spaces may appear anywhere and are ignored.
The evaluator must run in O(L) time and O(L) extra space, where L is the length of `expr`.
If the expression is invalid — an unknown variable, an invalid token, a trailing/dangling operator, or mismatched parentheses — return the string `"ERROR"` instead of a number.
Return type: the integer result on success, or the string `"ERROR"` on any invalid input.
Follow-ups to discuss (not graded here): add right-associative exponentiation `^`, and a two-argument function `max(a, b)`.
Constraints
- 0 <= len(expr) <= 10^5
- Integer operands are non-negative; the final result fits in a signed 64-bit integer (wrap on overflow).
- Variable names are non-empty alphabetic strings; values are integers.
- Division truncates toward zero (e.g. -7 / 2 = -3).
- Invalid input (unknown variable, invalid token, dangling operator, mismatched parentheses) returns the string "ERROR".
Examples
Input: ('a + b * 2', {'a': 3, 'b': 4})
Expected Output: 11
Explanation: b*2 = 8 binds before +, then a + 8 = 11 (precedence).
Input: ('(a + b) * 2', {'a': 3, 'b': 4})
Expected Output: 14
Explanation: Parentheses force (3+4)=7 first, then 7*2 = 14.
Hints
- Use recursive descent with three precedence levels: parse_expr handles + and -, parse_term handles * and /, and parse_factor handles unary signs, parentheses, numbers, and variables.
- Track a single index into the string and a skip_spaces helper so whitespace never reaches the operator logic.
- For truncate-toward-zero division, compute abs(a) // abs(b) and negate when the operand signs differ — Python's // floors toward negative infinity, which gives the wrong answer for negatives.
- After the top-level parse, if the index hasn't reached the end of the string the input had trailing garbage — return ERROR.