Skip to content

Create a Match Maker

Level: L3-L6 Topics: Sorted Data Structures, Online Algorithms, Greedy, Testing, System Design

Problem Statement

Design an online matchmaking system for a multiplayer game. Players enter a queue one at a time, each with a skill rating (an integer). Two players can be matched if the absolute difference in their skill ratings is at most a given threshold D.

Implement a MatchMaker class:

  • add_player(player_id, rating): Add a player to the waiting queue. If there is already a waiting player whose rating is within D of the new player's rating, immediately match them (remove both from the queue and start a game). If multiple waiting players qualify, match with the closest rating. If there is no valid match, the player waits in the queue.
  • Matching is eager: match immediately when a valid partner exists. Do not wait for a potentially better future match.

Background & Constraints

  • Skill ratings are integers (can be negative).
  • The difference threshold D is inclusive: players with ratings r1 and r2 can match if |r1 - r2| <= D.
  • When multiple waiting players are valid matches, pick the one with the smallest rating difference (break ties by earliest arrival or lowest rating — clarify with interviewer).
  • Player IDs are unique.
  • The system should handle a large number of concurrent waiting players efficiently.

Examples

D = 10
MatchMaker mm(D)

mm.add_player("Alice", 100)    → no match (queue: [Alice:100])
mm.add_player("Bob", 120)      → no match (|100-120|=20 > 10)
                                  (queue: [Alice:100, Bob:120])
mm.add_player("Carol", 105)    → matches with Alice (|100-105|=5 <= 10)
                                  (queue: [Bob:120])
mm.add_player("Dave", 115)     → matches with Bob (|120-115|=5 <= 10)
                                  (queue: [])

Hints & Common Pitfalls

  • A sorted data structure is key. Use a balanced BST (e.g., TreeMap in Java, std::set / std::map in C++, SortedList in Python via third-party library).
  • When a new player arrives, search for the nearest rating in the sorted set. If the closest waiting player is within D, match them.
  • Using a sorted structure, add_player is O(log N) where N is the number of waiting players.
  • A common mistake is using a list and scanning linearly — this gives O(N) per operation.
  • Another pitfall: not removing the matched player from the queue before continuing.
  • Handle edge cases: what if two waiting players have the same rating? What if a player disconnects before being matched?

Follow-Up Questions

  1. Write tests with a mock GameServer: Design a GameServer interface with a start_game(player1, player2) method. Write unit tests for MatchMaker that verify correct matching behavior using a mock GameServer. What edge cases should your tests cover? (Same rating, boundary of threshold, multiple valid matches, no valid match, etc.)
  2. N-player matches: Generalize to matches of N players (e.g., 4-player games). All players in a match must be pairwise within D of each other. Why does a greedy approach (greedily adding players to a group) fail? Consider a case where three players have ratings 1, 6, 11 with D=5: any pair is within range, but the group of three is not (|1-11|=10 > 5). What algorithmic approach handles this correctly?