Design Tic-Tac-Toe
Asked at Databricks
Problem
Design a Tic-Tac-Toe game that supports the player moves and determines the winner after each move in constant time.
Asked At
| Company | Difficulty | |
|---|---|---|
| Databricks | Medium | View all Databricks questions → |
How to Think About It
Brute force: after every move, scan the entire board checking all rows, columns, and diagonals. Time per move is O(n^2) for an n x n board.
Track the count of pieces per row, per column, and for both diagonals for each player. A player wins when any of their counts reaches n.
Use two arrays of size n for rows, two for columns, and two scalar variables for diagonals. One player adds +1, the other adds -1.
After placing a mark, check if the corresponding row, column, or diagonal count has absolute value n. If so, that player wins.
The anti-diagonal index for cell (r, c) in an n x n board is r + c == n - 1. Track it separately from the main diagonal where r == c.
Example on 3x3: Player 1 places at (0,0), (1,1), (2,2). Row counts: [1,1,1]. Col counts: [1,1,1]. Main diag count: 3. Winner detected at third move.
Optimal Approach
Step 1: Maintain arrays rows[n] and cols[n] initialized to zero, plus diag and antiDiag scalars.
Step 2: On move (row, col) by player p, add +1 if player 1 or -1 if player 2 to rows[row], cols[col], and the relevant diagonal(s).
Step 3: After updating, check if any of rows[row], cols[col], diag, or antiDiag has absolute value n. If so, return the player number.
Step 4: If no win condition is met, return 0.
Step 5: Example walkthrough on 3x3: Player 1 at (0,0) -> rows=[1,0,0], cols=[1,0,0], diag=1. Player 2 at (0,1) -> rows=[0,0,0], cols=[1,-1,0], diag=1. Player 1 at (1,1) -> rows=[0,1,0], cols=[1,-1,1], diag=2. Player 2 at (0,2) -> rows=[0,0,0], cols=[1,-1,0], diag=2, antiDiag=0. Player 1 at (2,2) -> diag=3, absolute value equals n, player 1 wins.
Time: O(1) per move. Space: O(n) for the row and column arrays.
What Trips People Up in Real Interviews
Scanning the whole board after each move instead of using counters. That gives O(n^2) per move instead of O(1).
Forgetting that a row, column, or diagonal is only a win if it is entirely filled by one player, not just partially occupied.
Mixing up which player increments vs decrements the counters. Establish the convention early and stick to it.
Not handling the anti-diagonal correctly. Remember the condition is r + c == n - 1, not r + c == n.
Trying to use a HashSet of positions per player and then scanning all combinations, which is unnecessary overhead.
Solution Code
class TicTacToe:
def __init__(self, n: int):
self.n = n
self.rows = [0] * n
self.cols = [0] * n
self.diag = 0
self.anti_diag = 0
def move(self, row: int, col: int, player: int) -> int:
val = 1 if player == 1 else -1
self.rows[row] += val
self.cols[col] += val
if row == col:
self.diag += val
if row + col == self.n - 1:
self.anti_diag += val
if (abs(self.rows[row]) == self.n or
abs(self.cols[col]) == self.n or
abs(self.diag) == self.n or
abs(self.anti_diag) == self.n):
return player
return 0Frequently Asked Questions
What is the Design Tic-Tac-Toe problem?
Design a Tic-Tac-Toe game that supports the player moves and determines the winner after each move in constant time.
How do you solve Design Tic-Tac-Toe?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Design Tic-Tac-Toe?
Design Tic-Tac-Toe is asked at Databricks. It is a medium difficulty problem.
What are common mistakes on Design Tic-Tac-Toe?
- Scanning the whole board after each move instead of using counters. That gives `O(n^2)` per move instead of `O(1)`.
- Forgetting that a row, column, or diagonal is only a win if it is entirely filled by one player, not just partially occupied.
- Mixing up which player increments vs decrements the counters. Establish the convention early and stick to it.
- Not handling the anti-diagonal correctly. Remember the condition is `r + c == n - 1`, not `r + c == n`.
- Trying to use a HashSet of positions per player and then scanning all combinations, which is unnecessary overhead.