Determine and print expression to reach target
Company: Snapchat
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given four numbers and a target T (e.g.,
24). Using +, −, ×, ÷ and parentheses, and using each number exactly once, determine whether you can form an expression that evaluates to T. Return a boolean. Follow-up: if it is possible, output one valid expression string. Clarify how to handle division by zero and floating-point tolerance; discuss algorithmic approach (e.g., backtracking with pruning), complexity, and how you would extend the method to N numbers or different operator sets.
Quick Answer: This question evaluates skill in constructing and evaluating arithmetic expressions, handling numerical stability (including division-by-zero and floating-point tolerance), and reasoning about combinatorial permutations of numbers and operators.
You are given a list of numbers `nums` and a target value `target`. Using the four arithmetic operators `+`, `-`, `*`, `/` and parentheses, and using each number in `nums` exactly once, determine whether you can build an expression that evaluates to `target`.
Return `true` if such an expression exists, otherwise `false`. The classic instance of this problem is the "24 game" (four numbers, target 24).
Rules and clarifications:
- Each number must be used exactly once; numbers may be combined in any order.
- Any intermediate result may be a non-integer (division can produce fractions), and intermediate/final results are compared with a floating-point tolerance of `1e-6`.
- Division by zero is not allowed: you may only divide by a value whose absolute value exceeds the tolerance.
- An empty input cannot reach any target, so return `false`.
- A single number `x` reaches `target` only if `x` equals `target` (within tolerance).
This generalizes naturally to N numbers and to arbitrary operator sets; the reference approach is backtracking that repeatedly collapses two values into one until a single value remains.
Constraints
- Each number in nums must be used exactly once.
- Allowed operators: + - * / and parentheses (any grouping).
- Intermediate and final values are compared with a floating-point tolerance of 1e-6.
- Division is only permitted when the divisor's absolute value exceeds 1e-6 (no division by zero).
- An empty nums list returns false.
Examples
Input: ([4, 1, 8, 7], 24)
Expected Output: True
Explanation: (8 - 4) * (7 - 1) = 4 * 6 = 24, so the target is reachable.
Input: ([1, 2, 1, 2], 24)
Expected Output: False
Explanation: No combination of 1, 2, 1, 2 with + - * / reaches 24.
Hints
- Think of the problem as repeatedly replacing two values by the result of one operation, until a single value remains; if that value equals the target (within tolerance) you've found an expression.
- Try every ordered pair (a, b) so that both a-b and b-a, and a/b and b/a, are explored. Guard division by checking |b| > 1e-6.
- Use a small epsilon (1e-6) for all equality and division-by-zero checks, because intermediate division can produce non-integers.