Pinterest·Machine Learning Engineer·Technical Phone Screen·Senior

Senior

Jul 2026

Summary

Pinterest MLE coding round, one problem that looks like a classic LC but with a twist that changes everything. Took me a bit too long to realize the left-to-right evaluation rule was the whole point of the problem.

Questions Asked (1)

Given a string of digits and a target integer, insert +, -, or * operators between digits (or no operator to form multi-digit numbers) so the resulting expression evaluates to the target. Operators have no precedence and the expression is evaluated strictly left-to-right. Return all valid expressions. Multi-digit numbers cannot have leading zeros.

Algorithms & Data Structures

Author's notes

I'd seen the LC 282 version before so I jumped straight into a backtracking approach and felt pretty good.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use backtracking to explore all possible ways to partition the digit string into numbers and insert operators between them. At each step, build the current expression and evaluate it left-to-right, pruning branches that cannot reach the target. Collect all valid expressions that evaluate to the target.

Pro tip: Emphasize the importance of pruning and handling edge cases like leading zeros and multi-digit numbers. Also, mention that since operators have no precedence, the evaluation is straightforward and can be done incrementally.

1. Understand the problem and constraints

Clarify that operators are evaluated left-to-right with no precedence, and that multi-digit numbers cannot have leading zeros. Identify that we need to return all valid expressions.

2. Design a backtracking approach

Recursively choose the next number (1 or more digits) from the remaining string, ensuring no leading zeros. At each step, try inserting '+', '-', or '*' (or no operator for the first number) and update the current evaluated value.

3. Implement pruning and evaluation

Since evaluation is left-to-right, maintain the current value and update it as you append operators and numbers. Prune branches where the current value cannot possibly reach the target (e.g., if all remaining operations are multiplication by positive numbers, etc.).

4. Collect and return results

When the entire string is consumed, check if the evaluated value equals the target. If so, add the expression to the result list. Return all such expressions.

5. Analyze complexity and optimize

Discuss time complexity (exponential in worst case) and potential optimizations like memoization or pruning based on bounds. Mention that the number of expressions can be large, so pruning is crucial.

Key Points to Mention

Backtracking with recursion to explore all partitions and operator combinations.
Handling leading zeros: skip numbers with leading zeros unless the number is exactly '0'.
Left-to-right evaluation: maintain current value and update with each operator.
Pruning strategies to reduce search space, such as checking if the target is reachable given remaining digits and operations.
Time and space complexity: exponential in the length of the string, but pruning can help in practice.
Edge cases: empty string, target not reachable, very long strings, and ensuring all valid expressions are returned without duplicates.

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