Decide target via subsequence plus/multiply expression
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Quick Answer: 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.
Constraints
- 0 <= len(A) <= 30
- 1 <= A[i] <= 2^31 - 1
- -2^31 <= target <= 2^31 - 1
- The chosen subsequence must be non-empty.
- Expressions are evaluated from left to right, so 2+3*4 evaluates as (2+3)*4 = 20.
Examples
Input: ([1, 9, 8, 7, 10, 3, 1], 25)
Expected Output: [True, '8*3+1']
Explanation: Choose the subsequence [8, 3, 1]. Left-to-right evaluation gives 8*3 = 24, then 24+1 = 25.
Input: ([2, 3, 4], 20)
Expected Output: [True, '2+3*4']
Explanation: With equal precedence, 2+3*4 is evaluated as (2+3)*4 = 20.
Input: ([], 7)
Expected Output: [False, '']
Explanation: The subsequence must be non-empty, so no expression can be formed from an empty list.
Input: ([10], 10)
Expected Output: [True, '10']
Explanation: A single chosen number is a valid expression, and it equals the target.
Input: ([2, 4, 6], 5)
Expected Output: [False, '']
Explanation: No non-empty subsequence with '+' and '*' evaluated left to right can produce 5.
Input: ([1, 1, 1], 3)
Expected Output: [True, '1+1+1']
Explanation: This tests duplicates and ones. Choosing all three numbers with addition gives 3.
Input: ([2147483647, 2], 2147483647)
Expected Output: [True, '2147483647']
Explanation: This tests a 32-bit boundary value. The first number alone equals the target.
Solution
def solution(A, target):
if target <= 0 or not A:
return [False, '']
nums = list(A)
n = len(nums)
memo = {}
def dfs(end, t):
# Can we build a non-empty expression using only nums[0..end]
# that evaluates to t?
if end < 0 or t <= 0:
return None
key = (end, t)
if key in memo:
return memo[key]
# Prefer a single-number expression when possible.
for i in range(end, -1, -1):
if nums[i] == t:
memo[key] = str(nums[i])
return memo[key]
# Choose nums[i] as the last number in the expression.
# Elements after i are skipped. Recursion uses only earlier elements.
for i in range(end, -1, -1):
x = nums[i]
# Undo a final '+ x': previous value must be t - x.
remaining = t - x
if remaining > 0:
prev_expr = dfs(i - 1, remaining)
if prev_expr is not None:
memo[key] = prev_expr + '+' + str(x)
return memo[key]
# Undo a final '* x': previous value must be exactly t / x.
if x != 0 and t % x == 0:
previous_value = t // x
if previous_value > 0:
prev_expr = dfs(i - 1, previous_value)
if prev_expr is not None:
memo[key] = prev_expr + '*' + str(x)
return memo[key]
memo[key] = None
return None
expression = dfs(n - 1, target)
if expression is None:
return [False, '']
return [True, expression]Time complexity: O(n * S), where S is the number of distinct memoized (end_index, remaining_target) states; in the worst case S can be exponential in n.. Space complexity: O(S + n), excluding the returned expression, where S is the number of memoized states and n is the recursion depth bound..
Hints
- Try working backward from target. If the last chosen number is x and the last operator was '+', the previous value must have been target - x.
- If the last operator was '*', the current target must be exactly divisible by x. Memoize states like (rightmost_allowed_index, remaining_target) to avoid repeating equivalent searches.