Bytedance·Backend Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Bytedance backend round, one algorithmic question that looked simple on the surface but had a real gotcha in the space constraint. Managed to get through it but spent too long second-guessing myself on the operator precedence handling.

Questions Asked (1)

Given a string representing a valid arithmetic expression with non-negative integers and +, -, *, / operators separated by spaces (no parentheses), evaluate it and return the integer result. Integer division should truncate toward zero. Can you do it in O(n) time?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was stack, which works fine, but they pushed back asking if I could do it with O(1) space.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a stack to evaluate the expression in one pass, handling operator precedence by deferring addition/subtraction and immediately applying multiplication/division. Alternatively, parse the string into tokens and use two passes: first handle * and /, then + and -. Emphasize O(n) time and O(n) space, and discuss trade-offs.

Pro tip: Mention that you can achieve O(1) space by using a running total and a last operand, but clarify that the stack approach is simpler and still O(n). Also, explicitly handle integer division truncation toward zero, especially for negative results.

1. Clarify requirements and edge cases

Confirm that the expression is valid, contains only non-negative integers and +, -, *, / separated by spaces, and that division truncates toward zero. Ask about input size and whether negative intermediate results are possible.

2. Choose an approach

Decide between a stack-based single-pass evaluation or a two-pass approach. Explain that the stack method handles precedence by pushing numbers and applying * and / immediately, while + and - are pushed as signed numbers.

3. Walk through the algorithm

Describe the steps: initialize a stack, parse tokens, maintain a current operator (default '+'), and for each number, apply the operator: for + push num, for - push -num, for * or / pop the top, compute, and push the result. Finally, sum the stack.

4. Analyze complexity and trade-offs

State that time complexity is O(n) because each character is processed once, and space is O(n) for the stack. Mention that an O(1) space solution exists using a running total and last operand, but it's more complex.

5. Test with examples

Walk through a sample expression like '3 + 2 * 2' to show the stack evolution and final result. Also test edge cases like division truncation (e.g., '7 / -2' if allowed) and large numbers.

Key Points to Mention

Operator precedence: multiplication and division have higher precedence than addition and subtraction.
Stack usage: push numbers, apply * and / immediately, and handle + and - by pushing signed numbers.
Integer division truncation toward zero: use int(a / b) or adjust for negative numbers.
Time complexity O(n) and space complexity O(n) for the stack; mention O(1) space alternative.
Edge cases: single number, leading/trailing spaces, division by zero (though problem says valid expression).
Parsing tokens: split by spaces or iterate character by character to build numbers.

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