Determine All Players with Fixed Rankings

Quick Overview

There are N players and directed match results. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.

Determine All Players with Fixed Rankings

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

# Determine All Players with Fixed Rankings There are N players and directed match results. A pair [a, b] means player a defeated player b. Results are transitive: if a defeated b and b defeated c, then a is known to rank above c. A player's ranking is determined when, for every other player, the results imply either that player is above the other player or below the other player. Return all players with determined rankings in ascending identifier order. ## Function Contract Implement `determined_players(n, winners, losers) -> list[int]`. Player identifiers are 0 through n - 1, and corresponding winner and loser entries form one result. ## Constraints - 1 <= n <= 500. - 0 <= number of results <= n * (n - 1). - No result has the same winner and loser. - The input is assumed consistent: no pair is reachable in both directions. ## Examples ```text n = 5, winners = [0, 1, 2, 3], losers = [1, 2, 3, 4] output = [0, 1, 2, 3, 4] ``` ```text n = 3, winners = [0], losers = [1] output = [] ``` ```hint Compute reachability For each player, count everyone reachable below and everyone that can reach the player. ``` ```hint Check the full relation A fixed ranking requires a known comparison with exactly n - 1 other players. ```

Quick Answer: There are N players and directed match results. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.

|Home/Coding & Algorithms/Google
Google logo
Google
Aug 1, 2026, 12:00 AM
mediumSoftware EngineerOnsiteCoding & Algorithms
0
0

Determine All Players with Fixed Rankings

There are N players and directed match results. A pair [a, b] means player a defeated player b. Results are transitive: if a defeated b and b defeated c, then a is known to rank above c. A player's ranking is determined when, for every other player, the results imply either that player is above the other player or below the other player. Return all players with determined rankings in ascending identifier order.

Function Contract

Implement determined_players(n, winners, losers) -> list[int]. Player identifiers are 0 through n - 1, and corresponding winner and loser entries form one result.

Constraints

  • 1 <= n <= 500.
  • 0 <= number of results <= n * (n - 1).
  • No result has the same winner and loser.
  • The input is assumed consistent: no pair is reachable in both directions.

Examples

n = 5, winners = [0, 1, 2, 3], losers = [1, 2, 3, 4]
output = [0, 1, 2, 3, 4]
n = 3, winners = [0], losers = [1]
output = []

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...