[Google Virtual Interview] Determine Precise Player Rankings - Graph Theory Problem

Location
Virtual Interview
Posted
26 Jun 2025
355 reads

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)

  1. 01

    Determine Precise Player Rankings

    Data Structures & Algorithms · Hard

    Problem Description

    In a chess tournament with N players, 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 M games 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 where games[i] = [winner, loser] represents that player winner beat player loser
    • n: 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 5
    

    Example 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 determined
    

    Constraints

    • 1 <= n <= 1000
    • 0 <= games.length <= min(n*(n-1)/2, 2000)
    • games[i].length == 2
    • 1 <= games[i][0], games[i][1] <= n
    • games[i][0] != games[i][1]
    • No duplicate games
    • All game results are consistent with some valid ranking

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Google recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!