FastPrepKnockout Tournament Win Probability

Knockout Tournament Win Probability

Google logoGoogle● HardFULLTIMEPHONE SCREEN
Learn

Problem statement

There are n teams numbered from 0 to n - 1, where n is a power of two. Their positions in a fixed single-elimination bracket are their numeric order.

The matrix winProbability gives the outcome probability of every possible match: winProbability[i][j] is the probability that team i defeats team j. Match outcomes are independent.

In round one, teams 0 and 1 play, teams 2 and 3 play, and so on. In every later round, the winner of the left half of each bracket block plays the winner of its right half. Return the probability that team target wins the tournament.

Function

tournamentWinProbability(winProbability: double[][], target: int) → double

Examples

Example 1

winProbability = [[0.0,0.7],[0.3,0.0]]target = 0return = 0.7

The tournament has one match, which team 0 wins with probability 0.7.

Example 2

winProbability = [[0.0,1.0,0.6,0.8],[0.0,0.0,0.5,0.5],[0.4,0.5,0.0,1.0],[0.2,0.5,0.0,0.0]]target = 0return = 0.6

Teams 0 and 2 win their first-round matches with probability 1. Team 0 then defeats team 2 with probability 0.6.

Example 3

winProbability = [[0.0,0.5,0.8,0.4],[0.5,0.0,0.5,0.5],[0.2,0.5,0.0,0.25],[0.6,0.5,0.75,0.0]]target = 0return = 0.25

Team 0 reaches the final with probability 0.5. Team 2 reaches it with probability 0.25 and team 3 with probability 0.75, so the result is 0.5 * (0.25 * 0.8 + 0.75 * 0.4) = 0.25.

Constraints

  • 1 <= n <= 128 and n is a power of two.
  • winProbability.length = n and every row has length n.
  • 0 <= winProbability[i][j] <= 1.
  • For distinct teams, winProbability[i][j] + winProbability[j][i] = 1.
  • winProbability[i][i] = 0.
  • 0 <= target < n.

More Google problems

See Google hiring insights
public double tournamentWinProbability(double[][] winProbability, int target) {
    // Write your code here.
}
winProbability[[0.0,0.7],[0.3,0.0]]
target0
expected0.7
Checking account…