Katkat
Back

Implement Multi-Player Tic-Tac-Toe

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests object-oriented design and grid traversal logic by requiring the implementation of a generic N-player Tic-Tac-Toe game where win conditions are evaluated based on a specific run-length.

Multi-Player Tic-Tac-Toe

Design a class TicTacToeGame that manages a game board of size N x N for M players. Each player is assigned a unique ID from 1 to M. The goal is to be the first to place K consecutive marks (horizontally, vertically, or diagonally).

Requirements

Implement the following methods:

  1. move(row, col, playerID): Places a mark for playerID at the specified position.
    • Return 1 if the player wins.
    • Return 0 if the move is valid and the game continues.
    • Return -1 if the move is invalid (out of bounds, position already occupied, or it is not that player's turn).
    • Return -2 if the game is already finished.
  2. getBoardState(): Returns a representation of the current board (e.g., a 2D array).
  3. undo(): Reverts the last valid move and switches the turn back to the previous player.

Constraints

  • 1 2 -> ... -> M -> 1...

Example

# 3x3 board, 2 players, win condition: 3 in a row
game = TicTacToeGame(3, 2, 3)
game.move(0, 0, 1) # Returns 0
game.move(1, 1, 2) # Returns 0
game.move(0, 1, 1) # Returns 0
game.move(2, 2, 2) # Returns 0
game.move(0, 2, 1) # Returns 1 (Player 1 wins)

Hints

Hint 1

Instead of scanning the entire board after every move, track the count of marks in each row, column, and the two main diagonals for every player.

Hint 2

Use a stack to keep track of previous moves to facilitate the undo operation efficiently.

Hint 3

For the turn logic, use the modulo operator `(total_moves % M)` to determine which player should move next.

Follow-up questions

  • How would you optimize the `move` method if the board size is very large (e.g., 10,000 x 10,000) and moves are sparse?
  • How would you adapt the system to support a 'team' mode where two players share a mark ID?
  • If this were a real-time web application, what components would you add to handle concurrent moves from multiple clients?