Design an Online Tic-Tac-Toe Service with REST-Only APIs, Matchmaking and Multi-Region

Design an online Tic-Tac-Toe game. Two players are paired through online matchmaking and then play a game against each other, each from their own device. The interviewer set these requirements: - Clients must talk to the server through REST APIs. - Two players play one game online. - Online matchmaking pairs players into games. - The design must scale. - The design must be able to expand to multiple regions. ### Constraints and Clarifications - Treat the REST requirement as a hard constraint: clients send HTTP requests and receive responses, and the server has no separate channel for pushing updates to a client. Confirm this reading with the interviewer before relying on it. - Player counts and the set of regions are not given; state your assumptions. ### Clarifying Questions - Does "REST APIs only" rule out WebSockets and server-sent events entirely, or does it only describe the public game API? - Should matchmaking pair the first two waiting players, or take skill or location into account? - Do players have accounts, ratings and game history, or is play anonymous? - Is there a time limit per move, and what should happen when a player disconnects or stops responding? ### Part 1 — Game API and game state Design the REST API, the data model for a game, and the flow of one game from the first move to the result. Under the REST-only constraint, how does a player find out that the opponent has moved? ```hint The server is the referee Decide what the server must check before it accepts a move, and what happens when two requests for the same game arrive at nearly the same moment, or the same move is sent twice. ``` ```hint Without push If the server cannot contact the client, the client has to ask. Think about when it needs to ask, how often, and how to make each question cheap when nothing has changed. ``` #### What This Part Should Cover - Resource-oriented endpoints for games and moves, with request and response shapes - Server-side validation of turn, cell and game status, and detection of a win or a draw - Concurrency control and idempotency for move submissions - How clients learn about the opponent's move without server push, and the latency and load trade-off ### Part 2 — Online matchmaking How are players paired with an opponent online? ```hint One waiting player, two arrivals Two players ask for a match at the same moment and both see the same waiting player. Decide how to make sure that player ends up in only one game. ``` #### What This Part Should Cover - A waiting queue and an atomic pairing step - How a waiting client learns that it has been matched, using REST only - Cancellation, timeouts and players who leave while waiting ### Part 3 — Scalability and multiple regions How does the design scale to many concurrent games, and how would you extend it to multiple regions? ```hint What actually needs to be global Ask which data a game in one region ever needs from another region, and which data, if any, must be shared worldwide. ``` #### What This Part Should Cover - Stateless API servers, and game state partitioned by game - Where the request load really comes from, and how to reduce it - Region-local games and matchmaking versus global user data, with consistency and latency trade-offs - Routing players to a region, and what happens when a region fails ### What a Strong Answer Covers - A working design within the REST-only constraint, with its cost in polling load and latency made explicit - Server-authoritative game logic that rejects invalid, out-of-turn and duplicate moves - Race-free matchmaking that never puts one player into two games - A scaling plan driven by the actual request mix rather than by storage - A deliberate split between region-local and global data, with the trade-offs stated ### Follow-up Questions - A player closes the app in the middle of a game. How does the opponent find out, and how is the game resolved? - If the REST-only constraint were lifted, what would you change and what would you keep? - How would you pair players of similar skill without making them wait too long? - Two friends in different regions want to play each other. How does your multi-region design handle that?