Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Uber coding screen for a software engineer role, one question, ran out of time. The problem looked trivial at first glance and absolutely was not.

Questions Asked (1)

Write a parser that evaluates nested add/sub expressions given as strings, e.g. 'add(1, sub(3,1))' should return 3.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Burned myself on the comma-splitting approach.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the grammar and constraints first, then choose a recursive descent parser or a stack-based iterative approach. Implement the parser with careful handling of nested expressions, and test with edge cases like negative numbers and whitespace.

Pro tip: Mention that you would first define a formal grammar (e.g., expression -> 'add(' expression ',' expression ')' | 'sub(' expression ',' expression ')' | number) to guide the implementation and ensure correctness.

1. Clarify requirements and constraints

Ask about input format, allowed operations, number types, whitespace handling, and error cases. Confirm whether the parser should handle only add/sub or be extensible.

2. Define grammar and parsing strategy

Write a simple grammar for the expressions and decide between recursive descent, stack-based, or regex-based parsing. Explain why recursive descent is natural for nested structures.

3. Implement the parser

Code the parser with a function that parses an expression, handling 'add' and 'sub' by recursively parsing arguments. Use an index or token stream to track position.

4. Test with edge cases

Test with simple expressions, deeply nested ones, negative numbers, and whitespace variations. Verify that evaluation returns correct results.

5. Discuss trade-offs and extensions

Talk about time/space complexity, potential stack overflow for deep nesting, and how to extend to more operations or variables.

Key Points to Mention

Recursive descent parsing is intuitive for nested expressions and mirrors the grammar.
Time complexity is O(n) where n is the length of the string, as each character is processed once.
Space complexity is O(d) for recursion depth d, which could be O(n) in worst case.
Handling whitespace and negative numbers requires careful tokenization or parsing logic.
Error handling for malformed input (e.g., missing parentheses) should be considered.
Iterative stack-based approach avoids recursion limits but is more complex to implement.

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