โ† Microsoft questions

Implement Tic Tac Toe

Filed under Microsoft

Free read 1 of 3

Use 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

  1. Use arrays to track counts of moves per row, column, and two diagonals to achieve O(1) win checking.

Solution

O(1) time, O(N) space

Python
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.