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 Meta.

What role is this question designed for?

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

Evaluate expression without stack, constant space

Quick Overview

Evaluate expression without stack, constant space evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

##### Question Given a string `s` representing a valid arithmetic expression of non-negative integers, the operators `+`, `-`, `*`, `/`, and spaces (there are **no parentheses**), evaluate the expression and return its integer value, respecting operator precedence (`*` and `/` bind tighter than `+` and `-`) and left-to-right associativity. Constraints and follow-ups the interviewer will push on: 1. **Single pass, constant space.** Solve it in a single left-to-right pass in O(n) time and O(1) extra space. You may **not** use an explicit stack, and you may **not** use recursion. 2. **Operator precedence without a stack.** Explain how you track the *last term* and a running *aggregated result* so that `*` and `/` are applied immediately while `+`/`-` are deferred — this is how you enforce precedence with no auxiliary data structure. 3. **Multi-digit numbers.** Explain how you accumulate multi-digit operands (e.g. `42`) as you scan, digit by digit. 4. **Integer division semantics.** Division is integer division that **truncates toward zero** (so `7/2 == 3` and `-7/2 == -3`), not floor division. 5. **Edge cases.** Handle interior and trailing spaces, single-number inputs, and the final pending term after the last character. Example: `"3+2*2"` evaluates to `7`; `" 3/2 "` evaluates to `1`; `" 3+5 / 2 "` evaluates to `5`.

Quick Answer: Evaluate expression without stack, constant space evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given a string `s` representing a valid arithmetic expression of non-negative integers with the operators `+`, `-`, `*`, `/`, and spaces (no parentheses), evaluate the expression and return its integer value. Respect operator precedence (`*` and `/` bind tighter than `+` and `-`) and left-to-right associativity. Solve it in a single left-to-right pass in O(n) time and O(1) extra space: you may NOT use an explicit stack and you may NOT use recursion. Key requirements: - Operator precedence is enforced by tracking the *last additive term* and a running *aggregated result*, so `*` and `/` are applied immediately while `+`/`-` are deferred. - Accumulate multi-digit operands digit by digit (e.g. `42`). - Integer division truncates toward zero (so `7/2 == 3` and `-7/2 == -3`), NOT floor division. - Handle interior and trailing spaces, single-number inputs, and the final pending term after the last character. Examples: `"3+2*2"` -> `7`; `" 3/2 "` -> `1`; `" 3+5 / 2 "` -> `5`.

Constraints

s is a valid arithmetic expression of non-negative integers
Operators are limited to +, -, *, / and the space character
There are no parentheses
* and / bind tighter than + and - (operator precedence)
Integer division truncates toward zero
Must run in O(n) time and O(1) extra space with no explicit stack and no recursion
All intermediate and final values fit in a 32/64-bit signed integer

Examples

Input: ("3+2*2",)

Expected Output: 7

Explanation: 2*2=4 is applied immediately (higher precedence), then 3+4=7.

Input: (" 3/2 ",)

Expected Output: 1

Explanation: Leading/trailing spaces are skipped; 3/2 truncates toward zero to 1.

Input: (" 3+5 / 2 ",)

Expected Output: 5

Explanation: 5/2 truncates to 2, then 3+2=5; interior spaces around the operator are ignored.

Input: ("42",)

Expected Output: 42

Explanation: Single multi-digit operand; the sentinel flush commits the final term.

Input: ("100-50/3*2+7",)

Expected Output: 75

Explanation: 50/3=16 (trunc), 16*2=32, so 100-32+7=75; the */ term is built in `last` before being committed.

Input: ("14-3/2",)

Expected Output: 13

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

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

Expected Output: 24

Explanation: Chained multiplication all extends the same term: ((2*3)*4)=24.

Input: (" 7 ",)

Expected Output: 7

Explanation: Only spaces and one number; padding spaces handled, single-number input returns the number.

Input: ("0",)

Expected Output: 0

Explanation: Boundary single-digit zero.

Input: ("1+1+1+1+1",)

Expected Output: 5

Explanation: Repeated additions; each + commits the prior additive term into result.

Input: ("10-2-3",)

Expected Output: 5

Explanation: Left-to-right associativity for subtraction: (10-2)-3=5.

Hints

With no parentheses the expression is a flat sum of products/quotients. You only ever defer additive terms, and their sum is a single number, so the unbounded stack collapses into one accumulator (result) plus one in-progress term (last).
Track four variables: result (sum of completed additive terms), last (signed value of the current term), cur (the number being parsed), and op (the operator preceding cur, initialized to '+').
Apply * and / immediately to `last`; commit `last` into `result` only when a +/- arrives. Append a sentinel '+' (or special-case the last index) so the final pending term is flushed.
Division must truncate toward zero. Python's // floors (-7 // 2 == -4), so use abs(last)//abs(cur) and re-apply the sign, giving -7/2 == -3.

Quick Overview