Meta·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Meta SWE coding round, one problem but the interviewer kept layering on constraints until I was basically rewriting my solution from scratch. The no-stack, single-pass requirement was the part that actually tripped me up.

Questions Asked (1)

Evaluate a string arithmetic expression containing non-negative integers and the operators +, -, *, / (no parentheses), respecting standard operator precedence and left-to-right associativity. Then do it in a single pass with O(1) extra space, no stack, no recursion.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I had a working stack-based solution in my head pretty fast, then they said no stack.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem constraints and edge cases (e.g., division by zero, integer division truncation). Then, explain the standard two-pass approach using a stack, and finally present the single-pass O(1) space solution by maintaining a running total and a current term, applying multiplication/division immediately and deferring addition/subtraction.

Pro tip: Emphasize that the O(1) space solution is not just about avoiding a stack but about recognizing that only the last term's value and operator need to be remembered; this demonstrates deep understanding of expression evaluation and memory optimization.

1. Clarify Requirements and Edge Cases

Ask about integer division behavior (truncation toward zero), division by zero, and whether the expression is guaranteed valid. Confirm that operators have standard precedence and left-to-right associativity.

2. Outline Standard Stack-Based Approach

Describe the typical two-pass method: parse numbers and operators, use a stack to handle precedence by evaluating * and / immediately, then sum the stack for + and -. Mention time O(n) and space O(n).

3. Derive Single-Pass O(1) Space Solution

Explain that we can avoid a stack by keeping a running total (result) and a current term. When encountering + or -, add the current term to result and start a new term with the sign. When encountering * or /, update the current term by applying the operator to the last number and the next number.

4. Walk Through an Example

Trace the algorithm on a sample expression like '3+2*2' to show how result and current term are updated step by step, ensuring clarity and correctness.

5. Analyze Complexity and Trade-offs

State that the solution runs in O(n) time and O(1) extra space, and discuss trade-offs: the single-pass approach is more memory-efficient but slightly more complex to implement than the stack-based method.

Key Points to Mention

Operator precedence: * and / have higher precedence than + and -, and evaluation is left-to-right.
Integer division truncates toward zero (e.g., 3/2 = 1, -3/2 = -1).
Handling of multi-digit numbers and skipping whitespace if present.
The role of the 'current term' variable in deferring addition/subtraction until the next operator.
Edge cases: division by zero (if allowed), leading/trailing operators, and empty string.
Time and space complexity: O(n) time, O(1) extra space for the single-pass solution.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.