Two Sigma·Data Scientist·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jul 2026

Summary

Got a coding problem from Two Sigma for a Data Scientist role that looked like a graph question but had a nasty twist with fractional weights. The kind of problem where your first instinct is completely wrong and you have to back out of it.

Questions Asked (1)

You have a complete directed graph with n nodes (up to 15). Every pair of distinct nodes has a directed edge with a positive weight, and weights can be less than 1. The score of a simple path is the product of its edge weights. Find the maximum score over all simple paths in the graph. The optimal path might stop early since multiplying by a weight under 1 shrinks the product.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was to just find the longest path or something Hamiltonian, which is completely wrong once you think about weights below 1.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize this as a longest path problem in a directed graph with multiplicative weights, which is NP-hard in general. Given n ≤ 15, propose a dynamic programming solution over subsets (Held-Karp style) that tracks the maximum product ending at each node for each subset, and note that the optimal path may stop early due to weights < 1. Discuss the trade-off between exact exponential-time DP and potential heuristics or approximations for larger n.

Pro tip: Mention that taking logarithms converts the product to a sum, but since weights can be < 1, the log is negative, so maximizing the product is equivalent to maximizing the sum of logs (which may be negative). This transformation allows using standard longest path DP, but be careful: the optimal path might be a single edge if all weights < 1, so initialize the DP with the best single edge.

1. Clarify problem and constraints

Confirm that the graph is complete, directed, with positive weights possibly < 1, and that we seek the maximum product over simple paths. Note n ≤ 15, so exponential algorithms are feasible.

2. Identify problem class and complexity

Explain that finding the longest simple path is NP-hard, but the small n allows a subset DP. Mention that the product objective can be transformed to a sum using logarithms, but negative logs require careful handling.

3. Design DP state and transition

Define dp[mask][v] as the maximum product of a simple path that visits exactly the nodes in mask and ends at v. Initialize with single-node paths (product 1) and single edges. Transition by adding an unvisited node u: dp[mask|1<<u][u] = max(dp[mask|1<<u][u], dp[mask][v] * w(v,u)).

4. Handle early stopping and final answer

Since weights < 1 can shrink the product, the optimal path may not use all nodes. Track the maximum product over all dp states (including single edges) as the answer. Also consider that the empty path (product 1) might be optimal if all weights < 1, but typically a single edge is better.

5. Analyze time and space complexity

State that the DP takes O(2^n * n^2) time and O(2^n * n) space, which is feasible for n=15 (about 500k states). Discuss potential optimizations like pruning or using logarithms to avoid floating-point underflow.

Key Points to Mention

NP-hardness of longest simple path problem
Dynamic programming over subsets (Held-Karp algorithm)
Logarithm transformation to convert product to sum
Handling weights < 1 and early stopping
Time and space complexity: O(2^n * n^2) and O(2^n * n)
Floating-point precision and underflow concerns

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