Katkat
Back

Implement a Tic-Tac-Toe game API

DatabricksSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to design a state-tracking system for an n x n Tic-Tac-Toe board that allows for constant-time move validation and win detection.

Tic-Tac-Toe Game Engine

Design a TicTacToe class for an n x n board that allows two players to make moves. You need to implement the following function:

int move(int row, int col, int player)

  • The player is represented by an integer (e.g., 1 or 2).
  • The function should return:
    • 0 if the game continues.
    • 1 if player 1 wins.
    • 2 if player 2 wins.

Constraints

  • n is between 2 and 1000.
  • You must optimize the move function to run in O(1) time complexity.
  • You can use O(n) extra space to track the state.

Example

# Initialize a 3x3 board
game = TicTacToe(3)

# Player 1 moves to (0, 0)
game.move(0, 0, 1) # returns 0

# Player 2 moves to (0, 2)
game.move(0, 2, 2) # returns 0

# Player 1 moves to (1, 1)
game.move(1, 1, 1) # returns 0

# Player 2 moves to (1, 0)
game.move(1, 0, 2) # returns 0

# Player 1 moves to (2, 2)
game.move(2, 2, 1) # returns 1 (Player 1 wins diagonally)

Edge Cases

  • What happens if a player tries to move on an occupied square?
  • How do you handle the game logic for the anti-diagonal (top-right to bottom-left)?

Hints

Hint 1

Instead of iterating through the board to check for a winner, maintain an array for each row and each column to store the sum of moves made by each player.

Hint 2

For the two diagonals, use two separate variables or a small array to track the move counts for each player.

Hint 3

When a player makes a move, increment the count for that player in the corresponding row, column, and diagonal trackers; if any tracker reaches 'n', that player has won.

Follow-up questions

  • How would you modify your implementation to support a game that can end in a draw, and how would you track the number of moves made?
  • If the board size `n` was extremely large (e.g., 10^9), how would you store the board state if only a few moves were made?
  • How would you adapt this class to support a thread-safe implementation for a web service where multiple users might move simultaneously?