FastPrepPath With Maximum Probability
Problem · Graph

Path With Maximum Probability

Learn this problem
● MediumSalesforce logoSalesforceFULLTIMEONSITE INTERVIEW
See Salesforce hiring insights

Problem statement

You are given an undirected graph with n nodes numbered from 0 through n - 1. Edge edges[i] connects two nodes and succeeds with probability probabilities[i].

The probability of a path is the product of the probabilities of its edges. Return the maximum probability of reaching end from start.

  • If no path exists, return 0.0.
  • If start == end, return 1.0.

Function

maxProbability(n: int, edges: int[][], probabilities: double[], start: int, end: int) → double

Examples

Example 1

n = 3edges = [[0,1],[1,2],[0,2]]probabilities = [0.5,0.5,0.2]start = 0end = 2return = 0.25

The path 0 -> 1 -> 2 has probability 0.5 * 0.5 = 0.25, which is greater than the direct edge probability 0.2.

Example 2

n = 3edges = [[0,1],[1,2],[0,2]]probabilities = [0.5,0.5,0.3]start = 0end = 2return = 0.3

The direct edge from 0 to 2 succeeds with probability 0.3, exceeding the two-edge path probability 0.25.

Example 3

n = 3edges = [[0,1]]probabilities = [0.5]start = 0end = 2return = 0.0

Node 2 is unreachable from node 0.

Constraints

  • 1 <= n <= 10^4
  • 0 <= edges.length = probabilities.length <= 2 * 10^4
  • Each edge contains two distinct valid node indices.
  • 0.0 <= probabilities[i] <= 1.0
  • 0 <= start, end < n
  • Parallel edges are allowed.

More Salesforce problems

drafts saved locally
public double maxProbability(int n, int[][] edges, double[] probabilities, int start, int end) {
    // write your code here
}
n3
edges[[0,1],[1,2],[0,2]]
probabilities[0.5,0.5,0.2]
start0
end2
expected0.25
checking account