Solve Expression and Tree-List Problems
Company: Pinterest
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
The coding portion included two algorithm problems:
1. **Generate expressions with left-to-right evaluation**
Given a string `num` containing only digits and an integer `target`, insert the operators `+` and `*` between some digits, or choose to concatenate adjacent digits into multi-digit numbers. Return all expressions that evaluate to `target`.
Unlike normal arithmetic, expressions are evaluated strictly from left to right, with no operator precedence. For example, `2+3*2` is evaluated as `(2+3)*2 = 10`.
Additional constraints:
- Do not generate numbers with leading zeros unless the number itself is exactly `0`.
- Return every valid expression.
2. **Convert a binary search tree into a sorted doubly linked list**
Given the root of a binary search tree, rearrange the existing nodes in place to form a sorted, non-circular doubly linked list. Use each node's `left` pointer as `prev` and `right` pointer as `next`. The head of the list should be the smallest value.
Follow-up: given the head of the resulting sorted doubly linked list, insert a new node while keeping the list sorted.
Quick Answer: This question evaluates competency in string expression generation under a custom left-to-right evaluation rule and in-place binary search tree manipulation to form a sorted doubly linked list, covering expression evaluation, digit concatenation constraints, and pointer-based data structure transformations.