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.
Players are numbered from 0 through `n - 1`. Each corresponding `winners[i]` and `losers[i]` pair means the winner ranks above the loser. Results are transitive. A player's ranking is fixed when the results imply a direction of comparison between that player and every other player. Return all such player identifiers in ascending order.
Constraints
- 1 <= n <= 500; player identifiers are 0 through n - 1.
- 0 <= len(winners) = len(losers) <= n * (n - 1), and no result is a self-match.
- The results are consistent: no pair of distinct players is reachable in both directions.
Examples
Input: (1, [], [])
Expected Output: [0]
Explanation: The sole player is vacuously comparable with every other player.
Input: (5, [0, 1, 2, 3], [1, 2, 3, 4])
Expected Output: [0, 1, 2, 3, 4]
Explanation: A complete transitive chain determines every ranking.
Hints
- Test a complete chain, two disconnected chains, and a branching order with incomparable siblings.
- Check the single-player case and a player that is incomparable with exactly one other player.
- Include duplicate direct results and results that repeat facts already implied by other matches.