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.
Overview: 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.
Read the full Google Software Engineer interview experience this question came from
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.
Community answers
Answer by weian60333
class Solution {
public List> determined_rankings(int n, List> game_results) {
List> res = new ArrayList<>();
// 1. create reach matrix
boolean[][] reach = new boolean[n][n];
for (List result : game_results){
int win = result.get(0), lose = result.get(1);
reach[win][lose] = true;
}
// 2. use floyd warshall to process transitive relationship
// a win b, b win c -> a win c
for (int mid = 0; mid < n; mid++){
for (int player = 0; player < n; player++){
// player win mid must
if (!reach[player][mid]) continue;
for (int loser = 0; loser < n; loser++){
if (reach[mid][loser]){
reach[player][loser] = true;
}
}
}
}
// 3. calculate loseCnt and winCnt for player by reach matrix
for (int player = 0; player < n; player++){
// lower and higher for each player
int lower = 0;
int higher = 0;
for (int other = 0; other < n; other++){
if (reach[player][other]) lower++;
if (reach[other][player]) higher++;
}
if (lower + higher == n-1){
res.add(List.of(player, higher)); // zero based
}
}
return res;
}
}
``
Answer by shaheen.bhattacharya2010
def determined_rankings(n, game_results):
if n == 1:
return [(0,0)]
wadj = defaultdict(list)
ladj = defaultdict(list)
indegree = [0] * n
for u, v in game_results:
ladj[u].append(v)
wadj[v].append(u)
better = [0] * n # of people that are better than i
worse = [0] * n # of people that are worse than i
def reach(node, adj):
q = deque([node])
visited = set([node])
while q:
nd = q.popleft()
for nei in adj[nd]:
if nei in visited:
continue
visited.add(nei)
q.append(nei)
return len(visited) - 1
res = []
for i in range(n):
bet = reach(i, wadj)
wors = reach(i, ladj)
print(i, bet, wors)
if bet + wors == n-1:
res.append((i, bet))
return res