Jane Street·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Jane Street SWE interview with a pretty gnarly combinatorics/search problem. The kind of question where the constraints look small and you think you're fine, then you realize the search space is way weirder than it looks because of rational arithmetic and arbitrary parenthesization.

Questions Asked (1)

Given an array of integers (length up to 5) and a target integer, determine whether any subset of the array can be combined using +, -, *, / and any parenthesization to produce exactly the target value. Division is exact rational division, not floating point. You must use at least one element and each element at most once.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was to just try all subsets and permutations and slap operators between them left to right, which completely ignores parenthesization.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use recursive backtracking to explore all possible ways to combine numbers with the four operations, reducing the set by one element at each step. Represent numbers as exact rationals (numerator/denominator) to avoid floating-point errors, and prune branches early when possible. Since the array length is at most 5, the search space is small enough for a brute-force approach with memoization or pruning.

Pro tip: Emphasize exact rational arithmetic and discuss how you would handle division by zero and duplicate states to avoid redundant work. Mention that the small input size allows a straightforward exhaustive search, but you should still consider optimizations like memoization or symmetry reduction to show depth.

1. Clarify requirements and constraints

Confirm that each element can be used at most once, at least one element must be used, and operations include +, -, *, / with exact rational division. Ask about input size (up to 5) and whether the target is an integer.

2. Choose representation for exact arithmetic

Use a pair of integers (numerator, denominator) or a Fraction class to represent numbers exactly. Implement operations that maintain reduced form and handle division by zero.

3. Design recursive search

Recursively pick two numbers from the current list, apply each operation, and replace them with the result. Continue until one number remains; check if it equals the target. Also consider subsets by allowing the recursion to stop early if the target is met with a subset.

4. Handle subsets and base cases

Since any subset can be used, at each step you can either include the current number or skip it. Alternatively, iterate over all non-empty subsets and run the recursive combination on each. Ensure base case: if the list has one number, compare to target.

5. Optimize and test

Prune branches where the absolute value exceeds a bound (if target is integer) or use memoization on sorted tuples of rationals. Test edge cases: single element, division by zero, negative numbers, and target zero.

Key Points to Mention

Exact rational arithmetic to avoid floating-point precision issues.
Recursive backtracking with reduction of the set by combining two numbers at a time.
Handling all four operations, including division by zero checks.
Considering all non-empty subsets (or incorporating subset selection into recursion).
Pruning and memoization to reduce redundant computations, especially for duplicate numbers.
Time complexity analysis: O(4^(n-1) * n!) for n up to 5, which is feasible.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.