Report the Winner After Every Move on an n x n Tic-Tac-Toe Board
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Two players play tic-tac-toe on an `n × n` board, a generalization of the classic `3 × 3` game. Player 1 makes the first move and the players then alternate; each move places the mover's mark on an empty cell. A player wins as soon as their marks fill an entire row, an entire column, the main diagonal or the anti-diagonal.
Given `n` and the moves in the order they are played, report the state of the game after every move.
### Function Signature
```python
def winner_after_each_move(n: int, moves: list[list[int]]) -> list[int]:
```
`moves[i] = [row, col]` is the cell, 0-indexed, taken by move `i`. Move `i` is made by player 1 when `i` is even and by player 2 when `i` is odd.
### Rules
- The main diagonal is the cells `(i, i)` and the anti-diagonal is the cells `(i, n - 1 - i)`, for `0 <= i < n`.
- The result after a move is the number of the player who has won (1 or 2), or 0 if nobody has won yet.
- The game stops at the first winning move: the input never contains a move after it, so only the last result can be nonzero.
- If the moves end without a winner (including a full board, which is a draw), every result is 0.
- When `n = 1`, the first move fills a whole row, so player 1 wins immediately.
- Return exactly one result per move, in move order.
### Constraints
- `1 <= n <= 1000`
- `1 <= len(moves) <= min(n * n, 100000)`
- `0 <= row, col < n`, and no two moves use the same cell
- No move follows a winning move
### Examples
**Example 1**
```text
Input: n = 3, moves = [[0, 0], [1, 1], [0, 1], [2, 2], [0, 2]]
Output: [0, 0, 0, 0, 1]
```
Player 1 takes `(0, 0)`, `(0, 1)` and `(0, 2)` on moves 0, 2 and 4, completing the top row on the last move. Player 2's cells `(1, 1)` and `(2, 2)` lie on the main diagonal, but `(0, 0)` belongs to player 1.
**Example 2**
```text
Input: n = 4, moves = [[0, 0], [0, 3], [1, 1], [1, 3], [2, 2], [2, 3], [3, 0], [3, 3]]
Output: [0, 0, 0, 0, 0, 0, 0, 2]
```
After move 4, player 1 holds three of the four main-diagonal cells, which is not a win on a `4 × 4` board. Player 2's last move completes column 3: `(0, 3)`, `(1, 3)`, `(2, 3)` and `(3, 3)`.
**Example 3**
```text
Input: n = 3, moves = [[0, 0], [1, 1], [0, 2], [0, 1], [2, 1], [1, 2], [1, 0], [2, 0], [2, 2]]
Output: [0, 0, 0, 0, 0, 0, 0, 0, 0]
```
The board fills up without a winner. The final position, by player number, is:
```text
1 2 1
1 2 2
2 1 1
```
Overview: Process a sequence of alternating tic-tac-toe moves on an n x n board and report, after every move, whether player 1 or player 2 has just completed a full row, column, main diagonal or anti-diagonal. Tests efficient incremental win detection, diagonal indexing and correct handling of draws.
Read the full Databricks Software Engineer interview experience this question came from
Two players play tic-tac-toe on an `n x n` board, a generalization of the classic `3 x 3` game. Player 1 makes the first move and the players then alternate; each move places the mover's mark on an empty cell. A player wins as soon as their marks fill an entire row, an entire column, the main diagonal or the anti-diagonal.
You are given `n` and the list `moves` in the order the moves are played. `moves[i] = [row, col]` is the cell, 0-indexed, taken by move `i`. Move `i` is made by player 1 when `i` is even and by player 2 when `i` is odd.
Return a list with exactly one result per move, in move order. The result after a move is the number of the player who has won (`1` or `2`), or `0` if nobody has won yet.
### Rules
- The main diagonal is the cells `(i, i)` and the anti-diagonal is the cells `(i, n - 1 - i)`, for `0 <= i < n`.
- The game stops at the first winning move: the input never contains a move after it, so only the last result can be nonzero.
- If the moves end without a winner (including a full board, which is a draw), every result is `0`.
- When `n = 1`, the first move fills a whole row, so player 1 wins immediately.
### Constraints
- `1 <= n <= 1000`
- `1 <= len(moves) <= min(n * n, 100000)`
- `moves[i] = [row, col]` with `0 <= row, col < n`, and no two moves use the same cell
- No move follows a winning move
- Every input value and every result fits in a 32-bit signed integer
### Example 1
```text
Input: n = 3, moves = [[0, 0], [1, 1], [0, 1], [2, 2], [0, 2]]
Output: [0, 0, 0, 0, 1]
```
Player 1 takes `(0, 0)`, `(0, 1)` and `(0, 2)` on moves 0, 2 and 4, completing the top row on the last move. Player 2's cells `(1, 1)` and `(2, 2)` lie on the main diagonal, but `(0, 0)` belongs to player 1.
### Example 2
```text
Input: n = 4, moves = [[0, 0], [0, 3], [1, 1], [1, 3], [2, 2], [2, 3], [3, 0], [3, 3]]
Output: [0, 0, 0, 0, 0, 0, 0, 2]
```
After move 4, player 1 holds three of the four main-diagonal cells, which is not a win on a `4 x 4` board. Player 2's last move completes column 3: `(0, 3)`, `(1, 3)`, `(2, 3)` and `(3, 3)`.
Constraints
- 1 <= n <= 1000
- 1 <= len(moves) <= min(n * n, 100000)
- moves[i] = [row, col] with 0 <= row, col < n, and no two moves use the same cell
- No move follows a winning move, so only the last result can be nonzero
- Every input value and every result fits in a 32-bit signed integer
Examples
Input: (3, [[0, 0], [1, 1], [0, 1], [2, 2], [0, 2]])
Expected Output: [0, 0, 0, 0, 1]
Explanation: Source Example 1: player 1 completes the top row on move 4 (row win by player 1).
Input: (4, [[0, 0], [0, 3], [1, 1], [1, 3], [2, 2], [2, 3], [3, 0], [3, 3]])
Expected Output: [0, 0, 0, 0, 0, 0, 0, 2]
Explanation: Source Example 2: player 1 holds 3 of 4 main-diagonal cells (no win); player 2 completes column 3 on move 7.
Hints
- A move can only complete a line that passes through the cell it takes: its row, its column, and a diagonal only when the cell lies on that diagonal.
- A line is won only when all n of its cells belong to one player; a line holding marks from both players can never be won, and n - 1 cells are not enough.
- On an odd board the center cell lies on both diagonals; on an even board the two diagonals share no cell.