Остання активність 1794544815

Interview prep notes

Версія e7c49194068b04d9f6189e7f46923da9d2895c31

tictactoe.md Неформатований

Design Tic-Tac-Toe in O(1) per Move (LeetCode 348)

"Design Tic-Tac-Toe" looks trivial, but the follow-up, "can you check for a winner faster than O(n²) per move?", is what the interviewer is really after.

Naive approach

After each move, scan the move's row, its column and both diagonals: O(n) per move. Fine for 3x3, but the interviewer will push for better on an n x n board.

O(1) idea: running sums

Give player 1 the value 1 and player 2 the value -1. Keep:

  • rows[i]: the sum of the values in row i
  • cols[j]: the sum of the values in column j
  • diag and anti: the sums of the two diagonals

A player wins when any of these reaches n or -n.

class TicTacToe:
    def __init__(self, n):
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        self.diag = self.anti = 0

    def move(self, r, c, player):
        v = 1 if player == 1 else -1
        self.rows[r]  = v
        self.cols[c]  = v
        if r == c:
            self.diag  = v
        if r   c == self.n - 1:
            self.anti  = v
        n = self.n
        if n in (abs(self.rows[r]), abs(self.cols[c]),
                 abs(self.diag), abs(self.anti)):
            return player
        return 0

O(1) time per move and O(n) space, because we never store the board itself.

Assumptions to state

The problem guarantees valid moves (no overwriting a cell, no moves after a win). In a real game class you'd keep the board too, to validate moves and to render it.

Extending the design (OOD follow-ups)

  • Player, Board and Game classes, with Game owning turn order and win state.
  • Connect-K on a bigger board: the running-sum trick no longer works directly, so count consecutive pieces from the last move in each of four directions (still O(k)).
  • Undo: store the move history and subtract values when undoing.

Disclosure: I'm part of the Linkjob AI team (an AI interview assistant).