List All Plus/Times Expressions Reaching a Target Under Operator Precedence
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
You are given a list of nonnegative integers and a target. Place either `+` or `*` between every pair of adjacent numbers, keeping the numbers in their original order, and return every resulting expression whose value equals the target.
This version uses standard operator precedence: all multiplications happen before any addition. For example, `2+3*4` evaluates to `2 + 12 = 14`.
This is a follow-up to a version of the problem that evaluated left to right and returned only a boolean. The interviewer asked for a new function, leaving the earlier one unchanged, that respects precedence and returns the matching expressions.
### Function Signature
```python
def find_expressions(nums: list[int], target: int) -> list[str]:
...
```
### Rules
- Exactly one operator, `+` or `*`, goes in each of the `len(nums) - 1` gaps. Numbers cannot be concatenated, reordered, skipped, or negated, and no parentheses can be added.
- Value of an expression: multiply together each maximal run of numbers joined by `*`, then add up those products.
- Write each expression as the numbers in standard decimal form with the chosen operator characters between them and no spaces. For example, `nums = [1, 2, 3]` with operators `+` and `*` is written `"1+2*3"`.
- If `nums` has one element, the only expression is that number in decimal form.
### Output
Return all matching expressions sorted in ascending lexicographic order by character code, the order Python's `sorted` produces. In this order `*` comes before `+`. Return an empty list if no expression matches. Each assignment of operators produces a different string, so the output never contains duplicates.
### Constraints
- `1 <= len(nums) <= 10`
- `0 <= nums[i] <= 30`
- `0 <= target <= 10^15`
- Intermediate and final values can exceed `2^31 - 1`, but they never exceed `30^10` (about `5.9 * 10^14`), so 64-bit integers are enough.
- There are at most `2^9 = 512` possible expressions.
### Examples
Input: `nums = [1, 2, 3], target = 7`
Output: `["1+2*3"]`
Input: `nums = [2, 2, 2], target = 6`
Output: `["2*2+2", "2+2*2", "2+2+2"]`
The only other assignment, `2*2*2`, equals `8`.
Input: `nums = [0, 5], target = 1`
Output: `[]`
Overview: Return every expression formed by placing plus or times between adjacent numbers, kept in order, that equals a target under standard operator precedence. Results are sorted lexicographically, testing enumeration of operator choices and correct handling of multiplication binding tighter than addition.
Read the full Pinterest Software Engineer interview experience this question came from