Katkat
Back

Design an n x n Tic-Tac-Toe Game

DatabricksSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to design an efficient class to manage game state, focusing on constant-time win condition checking using auxiliary data structures.

Design an n x n Tic-Tac-Toe Game

Design a class TicTacToe that allows two players to play an n x n game. The game should be able to determine the winner after every move efficiently.

Requirements

Implement the TicTacToe class with the following interface:

  • __init__(n: int): Initializes the game board of size n x n.
  • move(row: int, col: int, player: int) -> int: Places a mark for the given player (1 or 2) at the specified (row, col). Returns 0 if there is no winner, 1 if player 1 wins, or 2 if player 2 wins. You may assume that the move is valid and that players take turns correctly.

Efficiency Goal

  • The move function should run in O(1) time complexity.

Example

# n = 3
game = TicTacToe(3)
game.move(0, 0, 1) # Returns 0
game.move(0, 2, 2) # Returns 0
game.move(2, 2, 1) # Returns 0
game.move(1, 1, 2) # Returns 0
game.move(2, 0, 1) # Returns 0
game.move(1, 0, 2) # Returns 0
game.move(2, 1, 1) # Returns 1 (Player 1 wins)

Considerations

  • Avoid iterating over the entire board or rows/columns to check for a win.
  • Think about what information needs to be stored to identify if a row, column, or diagonal is completed by the current player.

Hints

Hint 1

Instead of a 2D array, maintain tracking variables for the count of moves made by each player in every row and every column.

Hint 2

Use two additional variables to track the two diagonals (the main diagonal and the anti-diagonal).

Hint 3

If a player places a mark at (r, c), increment their count in row r and column c, and check if that count equals n; perform similar checks for diagonals if the move lands on one.

Follow-up questions

  • How would you modify your design if the board size were dynamically resizable during the game?
  • If the game allowed for an arbitrary number of players, how would your data structures change?
  • What changes are required to support a 'undo move' functionality that reverts the board state?