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 Technical Screen rounds at Otter.Ai.

What role is this question designed for?

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

Implement an Arithmetic Expression Evaluator

Company: Otter.Ai

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement an arithmetic expression evaluator. Part 1: Given a string expression containing non-negative integers, spaces, and the operators '+', '-', '*', and '/', return the integer result of evaluating the expression. Multiplication and division have higher precedence than addition and subtraction. Integer division must truncate toward zero. You may assume the expression is valid and does not contain parentheses in Part 1. Part 2 follow-up: Extend your evaluator to support nested parentheses, such as '(2 + 3) * (4 - 1)'. Parentheses may appear anywhere a subexpression is valid. The expression is still guaranteed to be syntactically valid. Do not use built-in expression evaluation functions such as eval. Example 1: Input: "3+2*2" Output: 7 Example 2: Input: " 3/2 " Output: 1 Example 3: Input: "(2+6*3+5-(3*14/7+2)*5)+3" Output: -12

Quick Answer: This question evaluates expression parsing, operator precedence, tokenization, integer arithmetic semantics (including truncation), and handling of nested parentheses within the Coding & Algorithms domain.

Part 1: Evaluate Arithmetic Expressions Without Parentheses

Given a syntactically valid string expression containing non-negative integers, spaces, and the operators '+', '-', '*', and '/', return the integer result of evaluating the expression. Multiplication and division have higher precedence than addition and subtraction. Integer division must truncate toward zero. The expression does not contain parentheses in this part. Do not use built-in expression evaluation functions such as eval.

Constraints

1 <= len(expression) <= 100000
The expression contains digits, spaces, '+', '-', '*', and '/' only
The expression is syntactically valid
All numbers in the expression are non-negative integers
Division by zero will not occur
The final result fits in a 32-bit signed integer

Examples

Input: "3+2*2"

Expected Output:

Explanation: Multiplication happens before addition: 3 + (2 * 2) = 7.

Input: " 3/2 "

Expected Output:

Explanation: Integer division truncates toward zero, so 3 / 2 = 1.

Input: " 3+5 / 2 "

Expected Output:

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

Input: "42"

Expected Output:

Explanation: Edge case: a single number with no operators.

Input: "14-3/2"

Expected Output:

Explanation: 3 / 2 = 1, then 14 - 1 = 13.

Hints

Process the string from left to right while keeping track of the previous operator and the current number.
You do not need a full parser here: handle '+' and '-' by committing the previous term, and handle '*' and '/' immediately on the most recent term.

Part 2: Evaluate Arithmetic Expressions With Nested Parentheses

Given a syntactically valid string expression containing non-negative integers, spaces, the operators '+', '-', '*', and '/', and nested parentheses, return the integer result of evaluating the expression. Multiplication and division have higher precedence than addition and subtraction. Parentheses may appear anywhere a subexpression is valid and must be evaluated first. Integer division must truncate toward zero. Do not use built-in expression evaluation functions such as eval.

Constraints

1 <= len(expression) <= 100000
The expression contains digits, spaces, '+', '-', '*', '/', '(', and ')' only
The expression is syntactically valid
All numbers written in the expression are non-negative integers
Division by zero will not occur
The final result fits in a 32-bit signed integer

Examples

Input: "(2+6*3+5-(3*14/7+2)*5)+3"

Expected Output:

Explanation: This is the sample with nested parentheses and mixed operators.

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

Expected Output:

Explanation: Each parenthesized group is evaluated first: 5 * 3 = 15.

Input: "2*(5+5*2)/3+(6/2+8)"

Expected Output:

Explanation: Evaluate parentheses first, then apply operator precedence with truncating division.

Input: "7"

Expected Output:

Explanation: Edge case: a single number without any operators or parentheses.

Input: "((1))"

Expected Output:

Explanation: Edge case: deeply nested parentheses around a single value.

Hints

A recursive helper can evaluate one parenthesized subexpression and return both its value and the position where it ends.
Inside each recursive call, you can reuse the same precedence-handling idea from Part 1.

Quick Overview

This question evaluates expression parsing, operator precedence, tokenization, integer arithmetic semantics (including truncation), and handling of nested parentheses within the Coding & Algorithms domain.