Maximum-Product Simple Path in a Complete Directed Graph
Company: Two Sigma
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
You are given a **complete directed graph** with `n` nodes labeled `0` through `n - 1`. For every ordered pair of distinct nodes `(i, j)`, there is a directed edge from `i` to `j` with a **positive** weight `w[i][j]`. Weights are not necessarily symmetric (`w[i][j]` may differ from `w[j][i]`), and weights may be **less than 1**.
A **simple path** is a sequence of **two or more distinct** nodes `v1 -> v2 -> ... -> vk` (no node may appear more than once). The **score** of a simple path is the **product** of the weights of its edges:
$$\text{score} = \prod_{t=1}^{k-1} w[v_t][v_{t+1}]$$
Return the **maximum score** over all simple paths in the graph.
**Important:** because edge weights can be smaller than 1, extending a path can *decrease* its score. The optimal path may use any number of nodes from 2 up to `n` — it is **not** necessarily a Hamiltonian path. Both the best subset of nodes, their order, and where the path stops must be chosen.
**Input**
- `n`: the number of nodes.
- `w`: an `n x n` matrix of numbers. For `i != j`, `w[i][j] > 0` is the weight of the edge from `i` to `j`. Diagonal entries `w[i][i]` are given as `0` and represent no edge (self-loops do not exist and must not be used).
**Output**
- A single number: the maximum product of edge weights over all simple paths. Answers within a relative or absolute error of `1e-6` of the correct value are accepted.
**Constraints**
- `2 <= n <= 15`
- `0 < w[i][j] <= 100` for all `i != j`, given with at most 4 digits after the decimal point
- `w[i][i] = 0` for all `i`
**Example 1**
```
n = 3
w = [
[0, 2.0, 0.5],
[1.5, 0, 4.0],
[0.25, 3.0, 0 ]
]
```
Output: `8.0`
The path `0 -> 1 -> 2` has score `2.0 * 4.0 = 8.0`. No other simple path scores higher (e.g., `2 -> 1 -> 0` scores `3.0 * 1.5 = 4.5`, and extending `0 -> 1 -> 2` is impossible since all three nodes are already used).
**Example 2**
```
n = 3
w = [
[0, 5.0, 0.1],
[0.2, 0, 0.3],
[0.4, 0.6, 0 ]
]
```
Output: `5.0`
The two-node path `0 -> 1` scores `5.0`. Every extension multiplies by a weight below 1 and lowers the score (e.g., `0 -> 1 -> 2` scores `5.0 * 0.3 = 1.5`), so stopping early is optimal.
**Example 3**
```
n = 2
w = [
[0, 0.5],
[0.9, 0 ]
]
```
Output: `0.9`
The only simple paths are `0 -> 1` (score `0.5`) and `1 -> 0` (score `0.9`).
Quick Answer: This question evaluates skills in graph algorithms, multiplicative path optimization, and combinatorial dynamic programming, testing competency in reasoning about simple paths and product-based scoring in directed weighted graphs.
You are given a **complete directed graph** with `n` nodes labeled `0` through `n - 1`. For every ordered pair of distinct nodes `(i, j)` there is a directed edge from `i` to `j` with a **positive** weight `w[i][j]`. Weights are not necessarily symmetric (`w[i][j]` may differ from `w[j][i]`), and weights may be **less than 1**.
A **simple path** is a sequence of **two or more distinct** nodes `v1 -> v2 -> ... -> vk` (no node may appear more than once). The **score** of a simple path is the **product** of the weights of its edges:
score = w[v1][v2] * w[v2][v3] * ... * w[v_{k-1}][vk]
Return the **maximum score** over all simple paths in the graph.
**Important:** because edge weights can be smaller than 1, extending a path can *decrease* its score. The optimal path may use any number of nodes from 2 up to `n` — it is **not** necessarily a Hamiltonian path. The best subset of nodes, their order, and where the path stops must all be chosen.
**Input**
- `n`: the number of nodes.
- `w`: an `n x n` matrix of numbers. For `i != j`, `w[i][j] > 0` is the weight of the edge from `i` to `j`. Diagonal entries `w[i][i]` are `0` and represent no edge (self-loops do not exist and must not be used).
**Output**
- A single number: the maximum product of edge weights over all simple paths. Answers within a relative or absolute error of `1e-6` of the correct value are accepted.
**Example 1**
```
n = 3
w = [[0, 2.0, 0.5], [1.5, 0, 4.0], [0.25, 3.0, 0]]
```
Output: `8.0` — the path `0 -> 1 -> 2` scores `2.0 * 4.0 = 8.0`.
**Example 2**
```
n = 3
w = [[0, 5.0, 0.1], [0.2, 0, 0.3], [0.4, 0.6, 0]]
```
Output: `5.0` — the two-node path `0 -> 1` scores `5.0`; every extension multiplies by a weight below 1.
**Example 3**
```
n = 2
w = [[0, 0.5], [0.9, 0]]
```
Output: `0.9` — the only simple paths are `0 -> 1` (`0.5`) and `1 -> 0` (`0.9`).
Constraints
- 2 <= n <= 15
- 0 < w[i][j] <= 100 for all i != j, given with at most 4 digits after the decimal point
- w[i][i] = 0 for all i
- The graph is complete and directed; weights may be < 1, so a longer path can score lower than a shorter one.
- Answers within relative or absolute error 1e-6 are accepted.
Examples
Input: (3, [[0, 2.0, 0.5], [1.5, 0, 4.0], [0.25, 3.0, 0]])
Expected Output: 8.0
Explanation: Path 0 -> 1 -> 2 scores 2.0 * 4.0 = 8.0, beating 2 -> 1 -> 0 (3.0 * 1.5 = 4.5) and every 2-node edge.
Input: (3, [[0, 5.0, 0.1], [0.2, 0, 0.3], [0.4, 0.6, 0]])
Expected Output: 5.0
Explanation: The 2-node path 0 -> 1 scores 5.0; every extension multiplies by a weight below 1 (e.g. 0 -> 1 -> 2 = 5.0 * 0.3 = 1.5), so stopping early wins.
Hints
- n is at most 15 — that upper bound almost always points at an exponential O(2^n * poly(n)) bitmask DP over subsets of nodes (Held-Karp), not a polynomial algorithm.
- Define dp[mask][last] = the maximum product of a simple path that visits exactly the nodes in `mask` and ends at `last`. Seed every single-node path with product 1.0, then extend by one unused node at a time.
- Every edge weight is positive, so the best path ending somewhere equals the best shorter path extended by one edge — max-product has optimal substructure. Take the answer over every mask with at least two nodes (don't force a full Hamiltonian path). Equivalently, replace each weight by its log and it becomes an additive longest-path DP.