Katkat
Back

Design a Tic-Tac-Toe Engine

DecagonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & 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 Engine

Design a class TicTacToe that manages an n x n game board. The class must handle move placement and determine if the current move results in a win.

Requirements

Implement the following interface:

class TicTacToe:
    def __init__(self, n: int):
        # Initialize the board of size n x n
        pass

    def move(self, row: int, col: int, player: int) -> int:
        # player is either 1 or 2
        # Return 0 if no one wins, 1 if player 1 wins, 2 if player 2 wins
        # Assume moves are valid and made on an empty cell
        pass

Constraints

  • n will be between 2 and 1000.
  • player is either 1 or 2.
  • You should aim for O(1) time complexity for the move function.

Example

# n = 3
ttt = TicTacToe(3)
ttt.move(0, 0, 1) # returns 0
ttt.move(0, 1, 2) # returns 0
ttt.move(1, 1, 1) # returns 0
ttt.move(0, 2, 2) # returns 0
ttt.move(2, 2, 1) # returns 1 (Player 1 wins diagonal)

Edge Cases

  • The game ends immediately when a player completes a row, column, or either of the two diagonals.
  • Ensure your design handles the primary and secondary diagonals correctly.

Hints

Hint 1

Instead of checking the entire board after each move, maintain arrays to track the count of moves for each player in each row, column, and the two main diagonals.

Hint 2

For row `i`, increment the count if player 1 moves there and decrement it if player 2 moves there; a win occurs when the absolute count reaches `n`.

Hint 3

The secondary diagonal can be tracked by checking if `row + col == n - 1`.

Follow-up questions

  • How would you adapt this design to support a 3D Tic-Tac-Toe game on an n x n x n cube?
  • If we wanted to undo a move, what changes would be necessary to your data structures?
  • How would you modify the implementation to handle an arbitrary winning length 'k' (where k <= n) instead of requiring a full row/column?