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.

Evaluate Arithmetic Expressions | Otter.Ai Coding Question

Evaluate Arithmetic Expressions

Company: Otter.Ai

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a function that evaluates a string arithmetic expression. Base problem: - The input is a string `s` containing non-negative integers, spaces, and the operators `+`, `-`, `*`, and `/`. - The expression is valid. - Division should truncate toward zero. - Operator precedence must be respected: multiplication and division have higher precedence than addition and subtraction. - Parentheses are not included in the base version. Return the integer value of the expression. Example: ```text Input: "3+2*2" Output: 7 Input: " 3/2 " Output: 1 Input: " 3+5 / 2 " Output: 5 ``` Follow-up: Extend the evaluator to support nested parentheses, such as: ```text Input: "2*(5+5*2)/3+(6/2+8)" Output: 21 ```

Quick Answer: This question evaluates understanding and implementation of expression parsing, operator precedence, tokenization of numeric and operator tokens, and correct integer arithmetic semantics including truncating division.

Part 1: Evaluate Arithmetic Expressions Without Parentheses

Given a valid arithmetic expression string `s`, evaluate and return its integer result. The string contains non-negative integers, spaces, and the operators `+`, `-`, `*`, and `/`. Rules: - Multiplication and division have higher precedence than addition and subtraction. - Division truncates toward zero. - The expression is valid. - Parentheses do not appear in this version. Your task is to compute the final integer value.

Constraints

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

Examples

Input: "3+2*2"

Expected Output:

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

Input: " 3/2 "

Expected Output:

Explanation: Spaces should be ignored. `3 / 2` truncates toward zero, so the result is `1`.

Input: " 3+5 / 2 "

Expected Output:

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

Input: "42"

Expected Output:

Explanation: Edge case: the expression contains only a single number.

Input: "0-3/2"

Expected Output:

Explanation: `3 / 2 = 1`, then `0 - 1 = -1`. This also checks truncation toward zero behavior.

Hints

Scan the string once while building the current number. When you reach an operator, apply the previous operator to the current number.
You do not need to store every number. A running total plus the most recent multiplicative term is enough to handle precedence.

Part 2: Evaluate Arithmetic Expressions With Nested Parentheses

Given a valid arithmetic expression string `s`, evaluate and return its integer result. The string contains non-negative integers, spaces, the operators `+`, `-`, `*`, and `/`, and parentheses `(` and `)`. Rules: - Parentheses may be nested. - Multiplication and division have higher precedence than addition and subtraction. - Parentheses override normal precedence. - Division truncates toward zero. - The expression is valid. Your task is to compute the final integer value.

Constraints

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

Examples

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

Expected Output:

Explanation: Evaluate the parenthesized parts first, then apply normal precedence.

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

Expected Output:

Explanation: This checks nested parentheses, spaces, and operator precedence together.

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

Expected Output:

Explanation: `(4-1)=3`, then `3*3=9`, then `2+9=11`, and `1-11=-10`.

Input: "(0-3)/2"

Expected Output:

Explanation: The parenthesized expression becomes `-3`, and `-3 / 2` truncates toward zero to `-1`.

Input: "7"

Expected Output:

Explanation: Edge case: the expression is just a single number.

Hints

Think in layers: an expression is made of terms joined by `+` and `-`, and a term is made of factors joined by `*` and `/`.
A recursive parser works naturally here: when you see `(`, evaluate the full subexpression inside it before continuing.

Quick Overview

This question evaluates understanding and implementation of expression parsing, operator precedence, tokenization of numeric and operator tokens, and correct integer arithmetic semantics including truncating division.