How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Parse and evaluate nested expressions with validation

Quick Overview

This question evaluates a developer's ability to design and implement a robust parser and evaluator for a parenthesized expression language, testing parsing, lexical scoping and variable binding, operator semantics, error detection, and safe integer arithmetic.

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

Design and implement a parser/evaluator for a parenthesized expression language where the input string may be invalid. The language uses spaces as token separators and parentheses for grouping. Supported operators: sum, prod, set. Semantics: (sum e1 e2 ... ek) returns the sum of k>=2 subexpressions; (prod e1 e2 ... ek) returns the product of k>=2 subexpressions; (set x v body) binds variable x to the value of expression v within body and any nested scopes (lexical scoping, inner bindings shadow outer ones). Tokens: integer = optional leading '-' followed by digits; variable = lowercase letter followed by zero or more lowercase letters or digits. Implement a function evaluate(expr: string) -> int that computes the value if the expression is valid; otherwise it must report an error (e.g., throw/return InvalidExpression). The evaluator must: handle arbitrary nesting and extra spaces; support negative integers; maintain proper lexical scoping; and detect errors including mismatched or missing parentheses, unknown operators, wrong arity (e.g., set must have exactly 3 arguments with the first being a variable), undefined variable references, malformed numbers, empty expressions, and 32-bit signed integer overflow. Constraints: length(expr) <= 1e5, maximum nesting depth <= 1e4. Provide and explain two approaches (recursive descent vs. iterative stack-based) and analyze time/space complexity in terms of n = length(expr). Follow-ups: extend set to support multiple bindings like (set x 1 y 2 body); add a division operator with integer truncation and division-by-zero handling.

Quick Answer: This question evaluates a developer's ability to design and implement a robust parser and evaluator for a parenthesized expression language, testing parsing, lexical scoping and variable binding, operator semantics, error detection, and safe integer arithmetic.

Implement `evaluate(expr)` for a parenthesized expression language. Spaces separate tokens and parentheses group subexpressions. Operators: - `(sum e1 e2 ... ek)` returns the sum of k >= 2 subexpressions. - `(prod e1 e2 ... ek)` returns the product of k >= 2 subexpressions. - `(set x v body)` binds variable `x` to the value of expression `v` within `body` and any nested scopes (lexical scoping; inner bindings shadow outer ones). `set` takes exactly 3 arguments and the first must be a variable. Tokens: - integer = optional leading `-` followed by one or more digits. - variable = a lowercase letter followed by zero or more lowercase letters or digits. Return the integer value when `expr` is valid. When `expr` is invalid, signal an error — in this harness, return the sentinel string `"InvalidExpression"`. The evaluator must handle arbitrary nesting and extra spaces, support negative integers, maintain proper lexical scoping, and detect: mismatched or missing parentheses, unknown operators, wrong arity, undefined variable references, malformed numbers, empty expressions, and 32-bit signed integer overflow (any intermediate or final value outside [-2^31, 2^31-1] is invalid). Constraints: length(expr) <= 1e5, maximum nesting depth <= 1e4.

Constraints

length(expr) <= 1e5
maximum nesting depth <= 1e4
integer = optional leading '-' then one or more digits
variable = lowercase letter then zero or more lowercase letters/digits
sum/prod require k >= 2 subexpressions; set requires exactly 3 args with a variable first
all intermediate and final values must fit in a 32-bit signed integer; otherwise InvalidExpression

Examples

Input: ("(sum 1 2)",)

Expected Output: 3

Explanation: 1 + 2 = 3.

Input: ("(prod 2 3 4)",)

Expected Output: 24

Explanation: 2 * 3 * 4 = 24; prod accepts more than two args.

Input: ("(set x 3 (sum x 4))",)

Expected Output: 7

Explanation: Bind x = 3, then evaluate (sum x 4) = 3 + 4 = 7.

Input: ("(set x 1 (set x 2 (prod x x)))",)

Expected Output: 4

Explanation: Inner set shadows outer x with 2, so (prod x x) = 2 * 2 = 4.

Input: ("(sum -3 5)",)

Expected Output: 2

Explanation: Negative integers are valid: -3 + 5 = 2.

Input: ("(sum (prod 2 3) 4 )",)

Expected Output: 10

Explanation: Extra and trailing spaces are ignored: (prod 2 3) = 6, then 6 + 4 = 10.

Input: ("(set a 5 (set b 10 (sum a b)))",)

Expected Output: 15

Explanation: Nested bindings a = 5, b = 10, then a + b = 15.

Input: ("(sum 1 2",)

Expected Output: "InvalidExpression"

Explanation: Missing closing parenthesis.

Input: ("(sum 1)",)

Expected Output: "InvalidExpression"

Explanation: sum requires at least 2 arguments.

Input: ("(foo 1 2)",)

Expected Output: "InvalidExpression"

Explanation: Unknown operator 'foo'.

Input: ("(sum x 1)",)

Expected Output: "InvalidExpression"

Explanation: Variable x is referenced but never bound.

Input: ("(set x 1)",)

Expected Output: "InvalidExpression"

Explanation: set must have exactly 3 arguments (var, value, body); body is missing.

Input: ("",)

Expected Output: "InvalidExpression"

Explanation: Empty expression.

Input: ("(prod 2147483647 2)",)

Expected Output: "InvalidExpression"

Explanation: 2147483647 * 2 overflows the 32-bit signed range.

Input: ("(set 1 2 (sum 1 2))",)

Expected Output: "InvalidExpression"

Explanation: set's first argument must be a variable, not the integer 1.

Hints

Tokenize first: emit '(' and ')' as standalone tokens and collapse runs of non-space, non-paren characters into atom tokens. This makes extra/leading/trailing spaces trivial to handle.
Use recursive descent: parse() reads one expression (atom or compound); parse_compound() reads the operator then dispatches. Validate arity inside each operator branch and require the closing ')'.
For scoping, pass an immutable copy (or a parent-linked chain) into the body of set so inner bindings shadow outer ones without mutating the caller's scope.
Guard every add/multiply/literal with a 32-bit range check, and after the top-level parse confirm all tokens were consumed (a trailing token like an unmatched ')' means invalid).

Quick Overview