How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

This question is commonly asked for Frontend Engineer candidates at Uber during technical interviews.

Simulate a Rank-Based Tournament | Uber Coding Question

Quick Overview

This question evaluates ability to simulate tournament pairing and single-elimination progression using array manipulation and data structures while preserving original player identifiers, plus relational schema design and SQL querying for storing and retrieving match records.

Simulate a Rank-Based Tournament

Company: Uber

Role: Frontend Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given an array `ranks`, where `ranks[i]` is the rank of player `i` in the initial bracket order. A smaller rank value means a stronger player. The tournament is single elimination. In each round, the remaining players are paired from left to right; if there is an odd number of players, the last player receives a bye and advances automatically. In a match, the player with the smaller rank wins. Implement a function that returns `{ rounds, champion }`, where `rounds` is a list of rounds and each round contains match records such as `{ playerA, playerB, winner }`. Preserve the original player IDs in the output. Follow-up: propose a relational schema for storing tournaments and matches, and write example queries to retrieve all matches for a given player or all matches in a tournament in chronological order.

Quick Answer: This question evaluates ability to simulate tournament pairing and single-elimination progression using array manipulation and data structures while preserving original player identifiers, plus relational schema design and SQL querying for storing and retrieving match records.

Part 1: Simulate a Rank-Based Single-Elimination Tournament

Player i has original ID i and strength rank ranks[i], where a smaller rank means a stronger player. Simulate a single-elimination tournament using the initial left-to-right bracket order. In each round, pair remaining players from left to right. If a round has an odd number of players, the last player gets a bye and advances automatically. Record every pairing as [playerA, playerB, winner]. For a bye, use playerB = -1 and winner = playerA. Return [rounds, champion], where rounds is the list of rounds in order and champion is the winning player ID. If there are no players, return [[], -1].

Constraints

0 <= len(ranks) <= 200000
1 <= ranks[i] <= 10^9
All rank values are distinct
The original player IDs must be preserved in the output

Examples

Input: [3, 1, 4, 2]

Expected Output: [[[[0, 1, 1], [2, 3, 3]], [[1, 3, 1]]], 1]

Explanation: Round 1: player 1 beats 0, and player 3 beats 2. Final: player 1 beats player 3.

Input: [5, 2, 4]

Expected Output: [[[[0, 1, 1], [2, -1, 2]], [[1, 2, 1]]], 1]

Explanation: Player 2 gets a bye in round 1, then loses to player 1 in the final.

Input: [4, 1, 5, 3, 2]

Expected Output: [[[[0, 1, 1], [2, 3, 3], [4, -1, 4]], [[1, 3, 1], [4, -1, 4]], [[1, 4, 1]]], 1]

Explanation: This case shows multiple rounds with byes preserved in the output.

Input: []

Expected Output: [[], -1]

Explanation: No players means no rounds and no champion.

Input: [7]

Expected Output: [[], 0]

Explanation: A single player is already the champion, so there are no matches.

Hints

Keep each active player as a pair of (player_id, rank) so you never lose the original ID.
Build the next round while recording the current round. If one player is left over, record a bye as [player_id, -1, player_id].

Part 2: Emulate Relational Queries for Tournament Matches

A reasonable relational design for this domain is: tournaments(tournament_id PK, name), players(player_id PK, rank), and matches(match_id PK, tournament_id FK, round_number, match_order, played_at, playerA_id FK, playerB_id FK, winner_id FK). In this coding version, you are given only rows from the matches table. Each match row is [match_id, tournament_id, round_number, match_order, played_at, playerA, playerB, winner], where playerB = -1 means a bye. Implement a function that emulates two retrieval queries: (1) all matches involving a given player_id, and (2) all matches belonging to a given tournament_id. Return both result sets sorted chronologically by played_at; if two matches have the same played_at, sort by smaller match_id first.

Constraints

0 <= len(matches) <= 200000
Each row in matches has exactly 8 integers
match_id values are unique
player IDs and tournament IDs are non-negative, except playerB may be -1 for a bye
played_at is an integer timestamp and is not necessarily unique

Examples

Input: ([[101, 1, 1, 1, 10, 0, 1, 1], [102, 1, 1, 2, 20, 2, 3, 2], [103, 1, 2, 1, 30, 1, 2, 1], [201, 2, 1, 1, 15, 0, 4, 0]], 0, 1)

Expected Output: [[[101, 1, 1, 1, 10, 0, 1, 1], [201, 2, 1, 1, 15, 0, 4, 0]], [[101, 1, 1, 1, 10, 0, 1, 1], [102, 1, 1, 2, 20, 2, 3, 2], [103, 1, 2, 1, 30, 1, 2, 1]]]

Explanation: Player 0 appears in match 101 and 201. Tournament 1 contains matches 101, 102, and 103.

Input: ([[5, 3, 1, 1, 100, 7, 8, 7], [2, 3, 1, 2, 100, 9, 10, 10], [8, 3, 2, 1, 110, 7, 10, 7]], 10, 3)

Expected Output: [[[2, 3, 1, 2, 100, 9, 10, 10], [8, 3, 2, 1, 110, 7, 10, 7]], [[2, 3, 1, 2, 100, 9, 10, 10], [5, 3, 1, 1, 100, 7, 8, 7], [8, 3, 2, 1, 110, 7, 10, 7]]]

Explanation: Two tournament matches share the same timestamp, so the smaller match_id comes first.

Input: ([], 1, 99)

Expected Output: [[], []]

Explanation: With no rows, both query results are empty.

Input: ([[1, 1, 1, 1, 5, 3, -1, 3], [2, 1, 2, 1, 10, 3, 4, 3], [3, 2, 1, 1, 7, 8, 9, 8]], 4, 1)

Expected Output: [[[2, 1, 2, 1, 10, 3, 4, 3]], [[1, 1, 1, 1, 5, 3, -1, 3], [2, 1, 2, 1, 10, 3, 4, 3]]]

Explanation: The bye row is still a tournament match, but only the second row involves player 4.

Hints

This is the in-memory version of SQL WHERE plus ORDER BY.
Be careful with byes: playerB = -1 should not match any real player ID.

Quick Overview