Minimum-Product Path in a Directed Weighted Graph
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A directed graph has `n` nodes, numbered `0` to `n - 1`, and weighted edges. The cost of a path is the product of its edge weights, not their sum. Return the minimum cost of a path from `source` to `target`.
### Function Signature
```python
def min_product_path(n: int, edges: list[list[int]], source: int, target: int) -> int:
```
### Rules
- `edges[i] = [u, v, w]` is a directed edge from node `u` to node `v` with weight `w`. It can only be followed from `u` to `v`. There may be several edges from the same `u` to the same `v`.
- The cost of a path is the product of the weights of the edges on it.
- Return the minimum cost over all paths from `source` to `target`, or `-1` if `target` cannot be reached from `source`.
### Constraints
- `2 <= n <= 10^4`
- `0 <= len(edges) <= 5 * 10^4`
- `0 <= u, v < n` and `u != v` for every edge
- `1 <= w <= 10^6`, integers
- The product of all edge weights in the graph is at most `10^15`. Every path that uses each edge at most once therefore costs at most `10^15`, which is beyond 2^31 - 1 but below 2^53: use 64-bit integers.
- `0 <= source, target < n` and `source != target`
### Examples
**Example 1**
```text
Input: n = 4, edges = [[0, 1, 2], [1, 2, 2], [2, 3, 2], [0, 3, 7]], source = 0, target = 3
Output: 7
```
The path `0 -> 1 -> 2 -> 3` costs `2 * 2 * 2 = 8`, although its weights add up to only `6`. The direct edge `0 -> 3` costs `7`, which is the minimum.
**Example 2**
```text
Input: n = 5, edges = [[0, 1, 1], [1, 2, 1], [2, 3, 1], [3, 4, 3], [0, 4, 4]], source = 0, target = 4
Output: 3
```
The path `0 -> 1 -> 2 -> 3 -> 4` costs `1 * 1 * 1 * 3 = 3`, less than the direct edge's `4`, even though it has more edges and a larger weight sum.
**Example 3**
```text
Input: n = 3, edges = [[0, 1, 5], [2, 1, 1]], source = 0, target = 2
Output: -1
```
From node `0` only node `1` can be reached; the edge `2 -> 1` cannot be followed backwards.
Overview: A graph problem in which the cost of a path is the product of its edge weights rather than their sum. Given a directed graph with integer weights of at least one, return the minimum product from a source to a target, or -1 if the target is unreachable. It tests adapting shortest-path reasoning to a different cost function.
Read the full Google Software Engineer interview experience this question came from
A directed graph has `n` nodes, numbered `0` to `n - 1`, and a list of weighted edges. Each `edges[i] = [u, v, w]` is a directed edge from node `u` to node `v` with weight `w`. It can only be followed from `u` to `v`, never backwards. There may be several edges from the same `u` to the same `v`.
The cost of a path is the **product** of the weights of the edges on it, not their sum. Return the minimum cost over all paths from `source` to `target`, or `-1` if `target` cannot be reached from `source`.
The answer can exceed 2^31 - 1 (it is at most 10^15), so return it as a 64-bit integer: `long` in Java and `long long` in C++. It always stays below 2^53, so it is exact as a JavaScript number.
### Constraints
- `2 <= n <= 10^4`
- `0 <= len(edges) <= 5 * 10^4`
- `0 <= u, v < n` and `u != v` for every edge
- `1 <= w <= 10^6`, integers
- The product of all edge weights in the graph is at most `10^15`. Every path that uses each edge at most once therefore costs at most `10^15`, which is beyond 2^31 - 1 but below 2^53: use 64-bit integers.
- `0 <= source, target < n` and `source != target`
### Example 1
```text
Input: n = 4, edges = [[0, 1, 2], [1, 2, 2], [2, 3, 2], [0, 3, 7]], source = 0, target = 3
Output: 7
```
The path `0 -> 1 -> 2 -> 3` costs `2 * 2 * 2 = 8`, although its weights add up to only `6`. The direct edge `0 -> 3` costs `7`, which is the minimum.
### Example 2
```text
Input: n = 5, edges = [[0, 1, 1], [1, 2, 1], [2, 3, 1], [3, 4, 3], [0, 4, 4]], source = 0, target = 4
Output: 3
```
The path `0 -> 1 -> 2 -> 3 -> 4` costs `1 * 1 * 1 * 3 = 3`, less than the direct edge's `4`, even though it has more edges and a larger weight sum.
Constraints
- 2 <= n <= 10^4
- 0 <= len(edges) <= 5 * 10^4
- 0 <= u, v < n and u != v for every edge
- 1 <= w <= 10^6, integers
- The product of all edge weights in the graph is at most 10^15. Every path that uses each edge at most once therefore costs at most 10^15, which is beyond 2^31 - 1 but below 2^53: use 64-bit integers.
- 0 <= source, target < n and source != target
Examples
Input: (2, [], 0, 1)
Expected Output: -1
Explanation: Minimum graph: n = 2 with no edges, so target 1 is unreachable.
Input: (2, [[0, 1, 5]], 0, 1)
Expected Output: 5
Explanation: Minimum graph with one edge from source to target: the answer is that edge's weight.
Hints
- Every weight is at least 1, so extending a path by one more edge can never make its cost smaller.
- Neither the number of edges nor the sum of the weights decides the answer: in Example 2 a four-edge path with a larger weight sum beats the direct edge.
- Edges are one-way and the same pair of nodes can be joined by several edges with different weights; any path that repeats no edge costs at most 10^15, so 64-bit integers are enough.
Community answers
Answer by mail2sudatra
Dijkstra but use product instead of sum while edge relaxation. Also initialize with 1, instead of 0