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.

Handle invalid Lisp expression parsing

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

##### Question LeetCode 736. Parse Lisp Expression – Given a string representing a Lisp-like expression containing let/add/mult operations and variable bindings, evaluate the expression and return the integer result. In addition to the standard problem, the input string may be syntactically invalid; detect invalid cases (e.g., mismatched parentheses, unknown tokens) and return an error indicator. https://leetcode.com/problems/parse-lisp-expression/description/

Quick Answer: This question evaluates the ability to parse and evaluate nested Lisp-like expressions, manage variable bindings and scope resolution, and detect malformed input and syntax errors.

You are given a string `expression` representing a Lisp-like expression. Evaluate it and return its integer result. The grammar supports three operators and integer/variable atoms: - An **integer**: an optional leading `-` followed by one or more digits (e.g. `-12`, `7`). - A **variable**: a lowercase letter followed by zero or more lowercase letters or digits (e.g. `x`, `a1`). The names `let`, `add`, `mult` are reserved and are never variable names. - `(add e1 e2)` — evaluates `e1` and `e2` and returns their sum. - `(mult e1 e2)` — evaluates `e1` and `e2` and returns their product. - `(let v1 e1 v2 e2 ... vn en expr)` — binds each variable `vi` to the value of `ei` (evaluated left to right, with earlier bindings in scope for later ones), then returns the value of the trailing `expr`. A `let` always has at least the trailing expression. Variable scoping is lexical: an inner expression sees the innermost binding of a name. **The twist (Uber variant):** the input may be syntactically or semantically invalid. If the expression is malformed — mismatched/unbalanced parentheses, an unknown operator token, a reference to a variable that is not in scope, a malformed integer, an empty string, or trailing characters after a complete expression — your function must NOT crash. Instead it must return the sentinel string `"ERROR"`. Return the integer result for valid input, or the string `"ERROR"` for any invalid input.

Constraints

1 <= expression length (an empty string is treated as invalid -> 'ERROR').
Valid expressions follow the let/add/mult grammar described above.
All intermediate and final integer values for valid inputs fit in a 32-bit signed integer.
Invalid inputs (mismatched parentheses, unknown tokens, undefined variables, malformed integers, trailing characters) must return the string 'ERROR' rather than raising.
Variable names are lowercase-letter-initial; 'let', 'add', 'mult' are reserved keywords.

Examples

Input: ("(let x 2 (mult x (let x 3 y 4 (add x y))))",)

Expected Output: 14

Explanation: Outer x=2; inner let rebinds x=3, y=4, inner (add x y)=7; (mult 2 7)=14.

Input: ("(let x 3 x 2 x)",)

Expected Output: 2

Explanation: x is bound to 3, then rebound to 2; the trailing expression x evaluates to the latest binding, 2.

Input: ("(let x 1 y 2 x (add x y) (add x y))",)

Expected Output: 5

Explanation: x=1, y=2, then x is rebound to (add x y)=3; final (add x y)=3+2=5.

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

Expected Output: 3

Explanation: Simple addition of two integer literals.

Input: ("(mult 3 (add 2 3))",)

Expected Output: 15

Explanation: (add 2 3)=5, then (mult 3 5)=15.

Input: ("(let a1 3 b2 (add a1 1) b2)",)

Expected Output: 4

Explanation: Multi-character variable names: a1=3, b2=(add a1 1)=4; result is b2=4.

Input: ("(add 1 2",)

Expected Output: ERROR

Explanation: Missing closing parenthesis -> mismatched parentheses -> 'ERROR'.

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

Expected Output: ERROR

Explanation: 'sub' is not a known operator (only add/mult/let) -> unknown token -> 'ERROR'.

Input: ("(add x 2)",)

Expected Output: ERROR

Explanation: Variable x is referenced but never bound -> undefined variable -> 'ERROR'.

Input: ("",)

Expected Output: ERROR

Explanation: Empty input string is invalid -> 'ERROR'.

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

Expected Output: ERROR

Explanation: Extra trailing ')' leaves leftover characters after a complete expression -> 'ERROR'.

Input: ("(mult 2 3) extra",)

Expected Output: ERROR

Explanation: Trailing garbage tokens after a complete top-level expression -> 'ERROR'.

Hints

Use a recursive-descent parser with a single moving index into the string; evaluate `(add ...)`, `(mult ...)`, and `(let ...)` by their leading operator token after consuming '('.
For `let`, scan variable/value pairs left to right, layering bindings into a copy of the enclosing scope; the final token (or parenthesized sub-expression) before ')' is the result expression — distinguish it by peeking whether the next non-space char is ')'.
Wrap the whole evaluation in a try/except (or explicit error path): any structural problem — missing ')', unknown operator, unbound variable, leftover characters after the top-level expression — should produce the 'ERROR' sentinel instead of crashing.

Quick Overview

This question evaluates the ability to parse and evaluate nested Lisp-like expressions, manage variable bindings and scope resolution, and detect malformed input and syntax errors.