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 HR Screen rounds at Instacart.

What role is this question designed for?

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

Evaluate arithmetic expression using DFS | Instacart Coding Question

Quick Overview

This question evaluates a candidate's understanding of expression parsing and evaluation using depth-first traversal, covering competencies in recursive descent or stack-based DFS, operator precedence, unary operators, and 64-bit integer division semantics with truncation toward zero.

Evaluate arithmetic expression using DFS

Company: Instacart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: HR Screen

Given a string representing an arithmetic expression with non-negative integers, +, -, *, /, parentheses, and optional spaces, evaluate its value. Use depth-first traversal (recursive descent or a stack-based DFS simulation). Support unary minus and operator precedence. Return a 64-bit integer with division truncating toward zero. Analyze time and space complexity and discuss recursion depth limits and an iterative alternative.

Quick Answer: This question evaluates a candidate's understanding of expression parsing and evaluation using depth-first traversal, covering competencies in recursive descent or stack-based DFS, operator precedence, unary operators, and 64-bit integer division semantics with truncation toward zero.

Given a string `expression` representing an arithmetic expression made up of non-negative integers, the binary operators `+`, `-`, `*`, `/`, parentheses `(` `)`, and optional spaces, evaluate the expression and return its value as a 64-bit integer. Requirements: - Standard operator precedence: `*` and `/` bind tighter than `+` and `-`. - Parentheses override precedence. - Support unary minus (and a permissive unary plus), e.g. `-3 + 5` and `-(3 + 4)`. - Integer division `/` truncates toward zero (so `7 / 2 == 3` and `-7 / 2 == -3`, NOT floor division). - Spaces may appear anywhere and must be ignored. Use a depth-first traversal of the expression grammar (recursive descent, equivalently a stack-based DFS simulation). The natural grammar is: ``` expr := term ( ('+' | '-') term )* term := factor ( ('*' | '/') factor )* factor := ('+' | '-') factor | '(' expr ')' | integer ``` Return the final value. You may assume the input is a well-formed expression with no division by zero. Follow-up: analyze time and space complexity, note the recursion-depth limit (proportional to the maximum parenthesis nesting depth) and describe an iterative alternative using two explicit stacks (one for values, one for operators) that applies higher-precedence operators eagerly.

Constraints

The expression contains only digits, '+', '-', '*', '/', '(', ')', and spaces.
All integer literals are non-negative; negative values arise only from unary minus.
The expression is well-formed (balanced parentheses, no division by zero).
Division truncates toward zero, not toward negative infinity.
The result fits in a 64-bit signed integer.

Examples

Input: "1 + 2 * 3"

Expected Output: 7

Explanation: Multiplication binds tighter than addition: 2*3=6, then 1+6=7.

Input: "(1 + 2) * 3"

Expected Output: 9

Explanation: Parentheses force the addition first: (1+2)=3, then 3*3=9.

Input: "10 - 2 - 3"

Expected Output: 5

Explanation: Subtraction is left-associative: (10-2)-3 = 8-3 = 5.

Input: "2 * 3 + 4 * 5"

Expected Output: 26

Explanation: Each product is evaluated before the sum: 6 + 20 = 26.

Input: "-3 + 5"

Expected Output: 2

Explanation: Leading unary minus produces -3, then -3+5 = 2.

Input: "-(3 + 4)"

Expected Output: -7

Explanation: Unary minus applied to a parenthesized subexpression: -(7) = -7.

Input: "7 / 2"

Expected Output: 3

Explanation: Integer division truncates toward zero: 7/2 = 3.

Input: "-7 / 2"

Expected Output: -3

Explanation: Truncation toward zero, not floor: -7/2 = -3 (floor would give -4).

Input: "3 + 5 / 2"

Expected Output: 5

Explanation: 5/2 truncates to 2, then 3+2 = 5.

Input: "2 * (3 + (4 - 1))"

Expected Output: 12

Explanation: Nested parentheses: (4-1)=3, (3+3)=6, 2*6 = 12.

Input: "42"

Expected Output: 42

Explanation: A bare integer evaluates to itself.

Input: " 10 + 20 "

Expected Output: 30

Explanation: Leading, trailing, and interior spaces are ignored: 10+20 = 30.

Input: "10 / 3 * 3"

Expected Output: 9

Explanation: Left-to-right within the same precedence: (10/3)=3 then 3*3 = 9, showing intermediate truncation.

Hints

Define three mutually recursive parse functions following the grammar: parse_expr handles + and -, parse_term handles * and /, and parse_factor handles unary signs, parentheses, and integer literals. This naturally encodes precedence.
Maintain a single shared cursor index into the string (e.g. a one-element list in Python or a class field) so all parse functions advance the same position. Skip spaces before reading each token.
For truncate-toward-zero division, compute abs(a)//abs(b) and negate the quotient when exactly one operand is negative — Python's // floors, which differs for negatives (e.g. -7//2 == -4 but truncation gives -3).
Recursion depth equals the maximum parenthesis nesting; for adversarial inputs convert to an iterative two-stack algorithm (values + operators) and pop/apply whenever the incoming operator has lower-or-equal precedence.

Quick Overview