Implement Tic Tac Toe
Filed under Microsoft
Free read 1 of 3Use arrays to track counts of moves per row, column, and two diagonals to achieve O(1) win checking.
The question
Design a class to represent a Tic Tac Toe game. Implement methods to make a move and check for a winner on an N x N board.
Constraints
- Board size N is configurable.
- Must handle invalid moves.
- Efficiency is key for large N.
Approach
Use arrays to track counts of moves per row, column, and two diagonals to achieve O(1) win checking.
Update the respective row/column/diagonal count based on the player's move.
If any count reaches N or -N, the current player has won.
Solution
O(1) time, O(N) space
class TicTacToe:
def __init__(self, n):
self.rows, self.cols = [0]*n, [0]*n
self.diag, self.anti = 0, 0
self.n = n
def move(self, r, c, p):
val = 1 if p == 1 else -1
self.rows[r] += val
self.cols[c] += val
if r == c: self.diag += val
if r + c == self.n - 1: self.anti += val
if abs(self.rows[r]) == self.n or abs(self.cols[c]) == self.n or abs(self.diag) == self.n or abs(self.anti) == self.n: return p
return 0
Tips
- What they are testing: Test for winning rows, columns, and both diagonals.
- Common mistake: Using O(N^2) to check for a winner after every move instead of O(N) or O(1).
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.