Find Players with Uniquely Determined Rankings
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Find Players with Uniquely Determined Rankings
## Problem
There are `n` players numbered `0` through `n - 1`. Each result `(winner, loser)` states that the winner is strictly better ranked than the loser. Smaller rank numbers are better, and all results are consistent with at least one total ordering of the players.
Results imply transitive comparisons: if `a` beat `b` and `b` beat `c`, then `a` must rank above `c` even if they did not play directly.
A player's rank is uniquely determined if that player occupies the same zero-based rank in every total ordering consistent with all results.
Implement:
```python
def determined_rankings(n: int, game_results: list[tuple[int, int]]) -> list[tuple[int, int]]:
...
```
Return `(player_id, rank)` pairs for all uniquely determined players, sorted by `player_id` ascending.
## Constraints
- `1 <= n <= 500`
- `0 <= len(game_results) <= n * (n - 1) / 2`
- `winner != loser`
- Duplicate results may appear and should not change the answer.
- The comparison graph is acyclic.
## Example
```python
n = 5
game_results = [(0, 1), (1, 2), (2, 3), (2, 4), (3, 4)]
```
The result is:
```python
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
```
## Discussion
Explain why direct win and loss counts are insufficient, and state how your algorithm detects exactly when a rank is fixed rather than merely bounded to a range.
Quick Answer: Given consistent winner-loser results, find players whose positions are fixed in every valid total ranking. Account for transitive comparisons, duplicate results, and the difference between a uniquely determined rank and a merely bounded one.
Given consistent winner-before-loser constraints, return each player whose zero-based rank is identical in every compatible total ordering.
Constraints
- 1 <= n <= 500
- The comparison graph is acyclic
- Duplicate results are harmless
Examples
Input: {'n': 1, 'game_results': []}
Expected Output: [(0, 0)]
Explanation: The only player has fixed rank zero.
Input: {'n': 3, 'game_results': []}
Expected Output: []
Explanation: No player's position is fixed without comparisons.
Hints
- Compute every transitive better-than relationship.
- A player's rank is fixed exactly when it is comparable with every other player.