Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Google SWE coding round, one problem the whole time: parse and evaluate nested arithmetic expressions written in function-call syntax. Seemed manageable at first but the follow-up about variable-length arguments is where things got interesting.

Questions Asked (2)

Parse and evaluate a nested function-style arithmetic expression string like add(2, mul(3, pow(4, 5))) and return the numeric result. Expressions can be arbitrarily deeply nested.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was to try some kind of stack-based iterative approach and I spent probably five minutes going down that road before realizing I kept getting off-by-one errors on the parenthesis tracking.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the grammar and constraints, then discuss two main approaches: recursive descent parsing and stack-based iterative parsing. Emphasize handling arbitrary nesting, error cases, and operator precedence (though function calls avoid precedence issues).

Pro tip: Mention that you can avoid building an explicit AST by evaluating on the fly during parsing, which saves memory and simplifies the code. Also, discuss how to handle large numbers and potential stack overflow with deep recursion.

1. Clarify requirements and edge cases

Ask about input format, allowed functions, number types, error handling, and maximum nesting depth. Confirm expected output type.

2. Choose parsing strategy

Decide between recursive descent (simple, elegant) and iterative stack-based (avoids recursion depth limits). Explain trade-offs.

3. Design evaluation logic

For recursive descent, parse function name, then arguments recursively, evaluate and apply. For iterative, use stacks for operators and operands.

4. Handle errors and edge cases

Detect malformed input, unknown functions, wrong argument counts, division by zero, and overflow. Discuss error reporting.

5. Analyze complexity and optimize

Time O(n), space O(d) where d is nesting depth. Discuss tail recursion, memoization if repeated subexpressions, and iterative alternatives.

Key Points to Mention

Recursive descent parsing: straightforward but risks stack overflow for deep nesting.
Iterative stack-based parsing: avoids recursion limits, more complex to implement.
On-the-fly evaluation: no need to build an AST, reducing memory overhead.
Error handling: invalid syntax, unknown functions, argument count mismatches, division by zero.
Time and space complexity: O(n) time, O(d) space for recursion depth.
Potential optimizations: tail call optimization, memoization for repeated subexpressions, using arbitrary-precision arithmetic.

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

Follow-up: extend your solution to support variable-length argument lists, e.g. add(1, 2, 3, mul(4, 5, 6)) instead of assuming exactly two arguments per operator.

Algorithms & Data Structures

Author's notes

This part actually wasn't as bad as I expected.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the grammar and semantics of the extended expression, especially how to determine the number of arguments for each operator. Then, adapt your parser to consume arguments until the next operator or closing parenthesis, and update your evaluator to handle variable-length argument lists, likely using recursion or a stack-based approach.

Pro tip: Mention that variable-length arguments can be handled by treating the expression as a sequence of tokens and using a recursive descent parser that reads arguments until it encounters an operator or the end of the expression. Also, discuss how to handle nested expressions and ensure the solution remains efficient.

1. Clarify the grammar and semantics

Ask or state assumptions about how arguments are delimited (e.g., commas, spaces) and whether operators can be nested arbitrarily. Confirm that each operator can take one or more arguments.

2. Design the parsing strategy

Choose a parsing approach (e.g., recursive descent, shunting-yard) that can handle variable-length argument lists. For recursive descent, parse an operator, then parse arguments until the next operator or closing parenthesis.

3. Implement the evaluator

Modify the evaluation logic to accept a list of arguments for each operator. For example, 'add' sums all arguments, 'mul' multiplies all arguments, and handle nested expressions recursively.

4. Handle edge cases and test

Consider cases like single argument, empty argument list, deeply nested expressions, and operators with different arities. Test with examples like 'add(1, 2, 3, mul(4, 5, 6))'.

5. Analyze complexity and optimize

Discuss time and space complexity. If needed, suggest optimizations like iterative parsing or memoization for repeated subexpressions.

Key Points to Mention

Recursive descent parsing to handle nested expressions and variable arguments.
Tokenization: how to split the input into tokens (numbers, operators, parentheses, commas).
Argument collection: parsing arguments until a delimiter or operator is encountered.
Evaluation of variable-length argument lists (e.g., using reduce or loops).
Handling of nested expressions and operator precedence if applicable.
Edge cases: empty argument lists, single argument, deeply nested expressions.

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