Katkat
Back

Simulate a Rank-Based Tournament

UberFrontend Engineer · Technical Screen
MediumFrontend EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to implement a single-elimination tournament simulation using queue-based structures and demonstrates competency in designing a relational database schema for tournament record-keeping.

Part 1: Tournament Simulation

You are tasked with simulating a single-elimination tournament. You are given a list of players, where each player is represented by an object { id: string, skill: number }.

In each round, players are paired consecutively: the player at index i plays against the player at index i + 1. The player with the higher skill wins and advances to the next round. If a round has an odd number of players, the last player automatically advances to the next round (a 'bye').

Implement a function simulateTournament(players) that returns a list of match results for every round until a single winner remains. A match result should be represented as { winnerId: string, loserId: string | null }.

Example

Input: [{id: 'A', skill: 10}, {id: 'B', skill: 20}, {id: 'C', skill: 15}] Round 1: A vs B (B wins), C has a bye. Round 2: B vs C (B wins). Result: [{winner: 'B', loser: 'A'}, {winner: 'B', loser: 'C'}]

Part 2: Database Design

Design a SQL schema to store the tournament matches generated in Part 1. Your design must support querying the 'path to victory' for any specific player (i.e., retrieving all matches that a specific player participated in, ordered by the round number).

Constraints

  • The input list size n will be between 2 and 1000.
  • Player IDs are unique.
  • Your solution should operate in O(n) time complexity.

Hints

Hint 1

Use a queue or a simple array to store current round participants and process them in pairs.

Hint 2

For the database schema, consider creating a `Matches` table with columns for the round number, winner_id, loser_id, and a tournament_id for scalability.

Hint 3

To retrieve the 'path to victory,' you will need a SQL query that uses an `OR` condition on both the winner_id and loser_id columns filtered by the specific player's ID.

Follow-up questions

  • How would you modify the simulation to support a 'Double Elimination' format?
  • What indices would you add to your SQL schema to optimize the 'path to victory' query?
  • How would you handle a scenario where two players have the exact same skill level?