[Google Virtual Interview] Determine Precise Player Rankings - Graph Theory Problem
- Location
- Virtual Interview
- Posted
- 26 Jun 2025
Summary
This post details a Google virtual interview question focused on determining precise player rankings in a chess tournament using graph theory, providing a comprehensive problem description, examples, constraints, and detailed algorithmic approaches.
How it went
Chess Tournament Ranking
Note: This problem is based on a Google interview question, with additional explanations and examples added for clarity.
Credits
- Original Problem Source: Google Technical Interview
- Enhanced by: Additional test cases, detailed explanations, and algorithmic analysis
- Problem Category: Graph Theory, Topological Sorting, Transitive Closure
If you found this problem interesting, consider exploring similar graph-based ranking problems or other Google interview questions involving partial ordering and transitive relationships.
Questions asked (1)
- 01
Determine Precise Player Rankings
Data Structures & Algorithms · Hard
Problem Description
In a chess tournament with
Nplayers, each player has a distinct rank from 1 to N (where rank 1 is the best player and rank N is the worst). In any game between two players, the higher-ranked player (lower rank number) always wins.Given the results of
Mgames in the format[winner, loser], determine which players' ranks can be precisely determined.A player's rank can be precisely determined if we can establish their exact position in the ranking through the transitive relationships from all game results.
Function Signature
vector<pair<int, int>> determineRanks(vector<vector<int>>& games, int n);Parameters:
games: A 2D array wheregames[i] = [winner, loser]represents that playerwinnerbeat playerlosern: The total number of players (numbered from 1 to n)
Returns:
- A vector of pairs
[player, rank]for players whose ranks can be precisely determined
Examples
Example 1:
Input: games = [[4,3],[4,2],[3,2],[1,2],[2,5]], n = 5 Output: [[2,4],[5,5]] Explanation: - Player 2 lost to players 1, 3, 4 and won against player 5 - Since we know 3 players beat player 2 and player 2 beats 1 player, player 2's rank is precisely 4 (3 + 1 = 4) - Player 5 lost to player 2, and we know player 2 lost to 3 other players - So player 5 is beaten by all other players, making their rank precisely 5Example 2:
Input: games = [[1,2],[2,3],[3,4],[3,5],[4,6],[5,6]], n = 6 Output: [[1,1],[2,2],[3,3],[6,6]] Explanation: - Player 1: beats everyone transitively (2,3,4,5,6), beaten by none → rank 1 - Player 2: beats (3,4,5,6), beaten by (1) → rank 2 - Player 3: beats (4,5,6), beaten by (1,2) → rank 3 - Player 6: beats none, beaten by everyone (1,2,3,4,5) → rank 6 - Players 4,5: both beat only (6) and beaten by (1,2,3), so 3+1+1=5≠6 They could be rank 4 or 5, cannot be precisely determinedConstraints
1 <= n <= 10000 <= games.length <= min(n*(n-1)/2, 2000)games[i].length == 21 <= games[i][0], games[i][1] <= ngames[i][0] != games[i][1]- No duplicate games
- All game results are consistent with some valid ranking