Katkat
Back

Evaluate expression without stack, constant space

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.