Katkat
Back

Decide target via subsequence plus/multiply expression

PinterestSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

A Pinterest software-engineer coding screen: given positive 32-bit integers and a target, decide whether some subsequence with '+'/'*' operators evaluated strictly left to right (equal precedence) hits the target, and return a valid expression. The answer spans forward backtracking, monotonicity-based pruning, a divisibility-guided reverse search from the target, complexity analysis, and 32-bit overflow handling.

Question

Given a sequence of positive 32-bit integers A and an integer target, determine whether there exists a subsequence of A (preserving order, using each element at most once) and a placement of + and * operators between the chosen numbers such that, evaluating the expression strictly from left to right with equal precedence (i.e., + and * are applied in order, ignoring normal math precedence), the resulting value equals target.

Example: For A = [1, 9, 8, 7, 10, 3, 1] and target = 25, one valid expression is 8*3+1 (evaluated left to right: 8*3 = 24, then 24+1 = 25).

Implement a function that returns true/false and, if true, also returns one valid expression. Then discuss:

  1. A backtracking / combinatorial search that builds a subsequence and enforces left-to-right evaluation without normal operator precedence.
  2. Pruning heuristics to accelerate the search (e.g., stop a branch when the partial value already exceeds reasonable bounds, avoid revisiting equivalent states, and apply early-termination rules).
  3. A reverse search starting from target, undoing operators with subtraction and division: continue a subtraction branch only while the remaining target stays >= 0, and take a division branch only when the current target is exactly divisible by the chosen number. Explain the correctness conditions and the order in which elements must be consumed.
  4. The time and space complexity of your approach and its worst-case behavior.
  5. How to handle 32-bit overflow of intermediate results, plus other edge cases.

Follow-up: Propose additional pruning techniques to further accelerate the search.