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

SeniorPrefer not to say

May 2026

Summary

Google SWE coding round with a hard backtracking problem. The variant twist on a classic LC problem made it feel less like rote prep and more like they wanted to see if you actually understood what was happening under the hood.

Questions Asked (1)

Given a string of digits and a target integer, insert +, -, or * operators between any adjacent digits (without reordering or skipping digits) so the resulting expression evaluates to the target. Return all valid expressions. Numbers in the expression cannot have leading zeros except for a standalone '0'.

Algorithms & Data Structures

Author's notes

The leading zero constraint is where I tripped up first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use backtracking to explore all possible ways to split the string into numbers and insert operators, maintaining the current expression and its evaluated value. To handle multiplication precedence, track the last operand and adjust the value accordingly. Prune branches early by checking if the remaining digits can possibly reach the target.

Pro tip: Clarify with the interviewer whether the target can be negative and whether the result should be sorted; also mention that using a mutable list for the current expression and backtracking avoids unnecessary string copying, which is crucial for performance.

1. Clarify constraints and edge cases

Ask about input size, allowed operators, leading zeros, and whether the target can be negative. Confirm that digits cannot be reordered or skipped.

2. Define recursive backtracking function

Design a function that takes the current index, current evaluated value, last operand, and current expression. At each step, try appending the next digit(s) as a number and then try each operator.

3. Handle multiplication precedence

When applying '*', compute new value as (current_value - last_operand) + (last_operand * current_number). Update last_operand to last_operand * current_number.

4. Prune and optimize

Prune branches where the remaining digits cannot possibly reach the target (e.g., if all remaining digits are 0 and target is not reachable). Also, avoid leading zeros by not forming numbers like '05'.

5. Collect and return results

When the end of the string is reached, check if the evaluated value equals the target. If so, add the expression to the result list. Return all valid expressions.

Key Points to Mention

Backtracking with state (index, current value, last operand, expression)
Handling operator precedence for multiplication by adjusting the last operand
Avoiding leading zeros in numbers (except '0' itself)
Time complexity analysis: O(4^n) in worst case, but pruning reduces it
Space complexity: O(n) for recursion stack and O(m) for results
Edge cases: empty string, target 0, all zeros, negative target

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