The machine runs a tic-tac-toe board of side n, and every move(row, col, player) must return the winner — 0, 1, or 2 — in O(1). The naive approach, rescanning the row, column, and diagonals after every move, is O(n) and fine for n=3, but the interview point is the counter trick that makes it O(1) regardless of n.
The machine keeps counter arrays rows[n], cols[n], plus two scalars for the main and anti-diagonals. Player 1 increments, player 2 decrements. After a move at (r, c), the machine adjusts rows[r], cols[c], and the diagonal counters when r == c or r + c == n − 1. A player has won exactly when one of the touched counters reaches +n or −n. Because a new mark only lands in empty cells and each counter tracks one line's imbalance, reaching magnitude n proves one player filled the whole line — nothing less produces it, and no mixed line reaches n.
The sign convention keeps it compact: one shared set of arrays, winner = 1 if a counter hit +n, 2 if −n. Only counters touched by this move can have changed, so the machine checks exactly those. Memory is O(n), every operation O(1).
Edge cases: the first move touches counters starting at zero; a move on both diagonals at once (the center cell on an odd-n board) updates three structures; moves after a win must not occur per the game contract — the machine returns the winner and stops. A full board with no winner returns 0 after every move, never a draw sentinel.
class TicTacToe:
def __init__(self, n):
self.n = n
self.rows = [0] * n
self.cols = [0] * n
self.diag = 0
self.anti = 0
def move(self, row, col, player):
d = 1 if player == 1 else -1
self.rows[row] += d
self.cols[col] += d
if row == col:
self.diag += d
if row + col == self.n - 1:
self.anti += d
if abs(self.rows[row]) == self.n or abs(self.cols[col]) == self.n \
or abs(self.diag) == self.n or abs(self.anti) == self.n:
return player
return 0