FastPrepDetermine Player Rankings

Determine Player Rankings

Google logoGoogle● MediumFULLTIMENEW GRADPHONE SCREENONSITE INTERVIEW
Learn

Problem statement

There are n players indexed from 0 through n - 1, with unique strict ranks from 1 (strongest) through n (weakest). Each result [winner, loser] means the winner is stronger than the loser. Strength relationships are transitive.

A player's rank is determinable when, for every other player, exactly one of the two players can reach the other through transitive win results. If two players can reach each other because of contradictory cyclic results, that relation is not strict and neither direction may be used to establish determinability between those two players.

Return one row [player, rank] for every determinable player, ordered by increasing player index. A determinable player's rank is 1 + the number of players that can reach that player.

Function

determinablePlayerRanks(n: int, wins: int[][]) → int[][]

Examples

Example 1

n = 3wins = [[0,1],[1,2]]return = [[0,1],[1,2],[2,3]]

The chain determines every pair. Player 0 has no stronger player, player 1 has one, and player 2 has two.

Example 2

n = 3wins = [[0,1]]return = []

Every player has at least one unknown relation, so no exact rank can be established.

Example 3

n = 3wins = [[0,1],[1,0],[1,2]]return = [[2,3]]

Players 0 and 1 are mutually reachable and therefore not strictly ordered. Both reach player 2, whose relation to each other player is one-way, so player 2 is determinably third.

Constraints

  • 1 <= n <= 300.
  • 0 <= wins.length <= 100000.
  • Every result contains two distinct valid player indices.
  • Duplicate results may appear.

More Google problems

See Google hiring insights
public int[][] determinablePlayerRanks(int n, int[][] wins) {
    // write your code here
}
n3
wins[[0,1],[1,2]]
expected[[0,1],[1,2],[2,3]]
Checking account…