Implement Multi-Player Tic-Tac-Toe
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Implement Multi-Player Tic-Tac-Toe
Implement a game class for an `N` by `N` board and `K` players. Each player has a distinct one-character printable mark. The constructor receives the marks in fixed turn order.
```text
TicTacToe(n, player_marks)
play(player, row, col) -> Status
getStatus() -> Status
```
`player_marks` is a nonempty ordered list of distinct marks and its length is `K`. `player` is one of those marks. A `Status` is the JSON-safe object `{state, winner}`, where `state` is one of `INVALID`, `IN_PROGRESS`, `WIN`, or `TIE`; `winner` is the winning mark only when `state` is `WIN`, and is `null` otherwise.
Players take turns in constructor order. `play` validates that the game is still active, it is that player's turn, `0 <= row < N` and `0 <= col < N`, and the cell is empty. A rejected move—including an out-of-bounds coordinate—returns `{state: INVALID, winner: null}` without changing the board, turn, or persistent game status. An accepted move returns the new persistent status. `getStatus()` returns only that persistent status, so it never returns `INVALID`.
A player wins immediately after forming three consecutive marks horizontally, vertically, or along either diagonal. A run longer than three also wins. If the board becomes full with no winner, the result is `TIE`.
## Constraints
- `3 <= N <= 200`
- `2 <= K <= 16`
- At most `N * N` accepted moves.
- Aim to inspect only lines through the latest move.
## Example
For `TicTacToe(3, [X, O])`, plays `X(0,0)`, `O(1,0)`, `X(0,1)`, `O(1,1)`, `X(0,2)` end with `{state: WIN, winner: X}`.
## Clarifications
The winning length is fixed at three even when `N` is larger. Once a terminal status is reached, all later plays are invalid and `getStatus` remains terminal.
## Hints
Only four directions through the newest mark need to be checked, expanding in both directions.
## Extensions
- Reduce space when wins require an entire row, column, or diagonal.
- Support undo and replay.
- Generalize to a configurable winning length.
Quick Answer: Implement multi-player Tic-Tac-Toe on a configurable board with strict turn order, validated moves, and a fixed three-mark win condition. Define exact status behavior for invalid and terminal moves while covering longer runs, ties, large boards, replay, undo, and configurable extensions.
You are given the driver for a multi-player Tic-Tac-Toe game played on an `n` x `n` board by `K` players.
`playerMarks` holds the `K` distinct player marks in fixed turn order; each mark is a single printable ASCII character. The three parallel arrays `players`, `rows`, and `cols` describe `M` calls to `play(player, row, col)` in order: call `i` is `play(players[i], rows[i], cols[i])`.
The board starts empty and the persistent game status starts at `IN_PROGRESS`. Players move in `playerMarks` order, cycling: the expected mark for the `t`-th accepted move (0-indexed) is `playerMarks[t % K]`. Rejected calls never advance the turn.
A call to `play(player, row, col)` is **accepted** only when all four of these hold:
1. the persistent status is still `IN_PROGRESS` (not already `WIN` or `TIE`),
2. `player` is the expected mark for the current turn,
3. `0 <= row < n` and `0 <= col < n`,
4. cell `(row, col)` is empty.
Otherwise the call is **rejected**: it returns `INVALID` and leaves the board, the turn counter, and the persistent status completely unchanged. An out-of-bounds coordinate is a rejection, not an error.
An accepted call writes the mark into `(row, col)`, advances the turn, and updates the persistent status to:
- `WIN:<mark>` when the mark just placed lies in a run of **three or more** consecutive equal marks horizontally, vertically, or along either diagonal. A run longer than three also wins. The winning length is always three, no matter how large `n` is.
- otherwise `TIE` when all `n * n` cells are now occupied,
- otherwise `IN_PROGRESS`.
An accepted call returns that new persistent status. `getStatus()` reports only the persistent status, so it never returns `INVALID`, and once the status is `WIN:<mark>` or `TIE` it stays there forever.
Return a list with exactly one entry per `play` call, in call order. Entry `i` is the two-element list of strings `[playResult, statusAfter]`, where `playResult` is what call `i` returned and `statusAfter` is what `getStatus()` reports immediately after call `i`. Every status is exactly one of `"INVALID"`, `"IN_PROGRESS"`, `"TIE"`, or `"WIN:"` followed by the single winning mark (for example `"WIN:X"`). When `M` is 0, return an empty list.
### Example 1
```
n = 3
playerMarks = ["X", "O"]
players = ["X", "O", "X", "O", "X"]
rows = [ 0, 1, 0, 1, 0]
cols = [ 0, 0, 1, 1, 2]
-> [["IN_PROGRESS", "IN_PROGRESS"],
["IN_PROGRESS", "IN_PROGRESS"],
["IN_PROGRESS", "IN_PROGRESS"],
["IN_PROGRESS", "IN_PROGRESS"],
["WIN:X", "WIN:X"]]
```
X takes `(0,0)`, `(0,1)`, `(0,2)` — the entire top row — so the fifth call returns `WIN:X`.
### Example 2
```
n = 3
playerMarks = ["A", "B"]
players = ["B", "A", "A"]
rows = [ 0, 0, -1]
cols = [ 0, 0, 0]
-> [["INVALID", "IN_PROGRESS"],
["IN_PROGRESS", "IN_PROGRESS"],
["INVALID", "IN_PROGRESS"]]
```
The first call is out of turn (A moves first), so it changes nothing — A is still due, and the second call takes `(0,0)`. The third call names a negative row and is rejected. `getStatus()` never reports `INVALID`.
Constraints
- 3 <= n <= 200
- 2 <= K <= 16, where K == len(playerMarks)
- Every mark in playerMarks is a single printable ASCII character (code points 32..126), and the K marks are distinct
- 0 <= M <= 40000, where M == len(players) == len(rows) == len(cols)
- Every players[i] is one of the marks in playerMarks
- -10^9 <= rows[i], cols[i] <= 10^9 (coordinates outside [0, n) are rejected, never an error)
- At most n * n calls are accepted
- Every input value fits in a signed 32-bit integer
Examples
Input: (3, ['X', 'O'], [], [], [])
Expected Output: []
Input: (3, ['X', 'O'], ['X'], [1], [1])
Expected Output: [['IN_PROGRESS', 'IN_PROGRESS']]
Hints
- A rejected call must leave the game byte-for-byte unchanged, so check every acceptance condition before you write anything to the board.
- After a mark lands you only have to look at the four lines through that one cell, counting outward in both directions until the neighbour stops matching.
- Keep a running count of occupied cells so the tie test does not rescan the board after every move.