PracHub
QuestionsLearningGuidesInterview Prep

Quick 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.

  • medium
  • Google
  • Coding & Algorithms
  • Software Engineer

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

  1. Compute every transitive better-than relationship.
  2. A player's rank is fixed exactly when it is comparable with every other player.
Last updated: Jul 15, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Count Overlapping Rectangle Updates on a Grid - Google (hard)
  • Find A Threshold-Limited Path With Minimum Required Safety - Google (medium)
  • Filter Repeated Robot Status Messages - Google (medium)
  • Minimize Direction Violations in a Directed Road Network - Google (medium)
  • Find the Largest Monotone Increasing Number - Google (medium)