Design an efficient Tic-Tac-Toe engine
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Quick Answer: This question evaluates a candidate's understanding of efficient algorithm design and minimal state management for a Tic-Tac-Toe engine on an n x n board, including constraints such as O(1) time per move and O(n) space.
Constraints
- 1 <= n <= 2000
- 1 <= len(operations) <= 2 * 10^5
- Each operation is one of ("move", row, col, player), ("undo",), or ("reset",)
- Winner detection after a move should be O(1) average time without rescanning the board
Examples
Input: (3, [("move", 0, 0, 1), ("move", 0, 0, 2), ("move", 3, 0, 1), ("undo",), ("undo",)])
Expected Output: ["NONE", "INVALID", "INVALID", "UNDONE", "INVALID"]
Explanation: The second move reuses an occupied cell, the third is out of bounds, the fourth undoes the only valid move, and the final undo fails because history is empty.
Input: (3, [("move", 0, 0, 1), ("move", 0, 1, 2), ("move", 1, 1, 1), ("move", 0, 2, 2), ("move", 2, 2, 1), ("move", 2, 0, 2)])
Expected Output: ["NONE", "NONE", "NONE", "NONE", "P1", "INVALID"]
Explanation: Player 1 completes the main diagonal on the fifth command. After a win, further moves are invalid until an undo or reset happens.
Input: (3, [("move", 0, 0, 1), ("move", 0, 1, 2), ("move", 0, 2, 1), ("move", 1, 1, 2), ("move", 1, 0, 1), ("move", 1, 2, 2), ("move", 2, 1, 1), ("move", 2, 0, 2), ("move", 2, 2, 1)])
Expected Output: ["NONE", "NONE", "NONE", "NONE", "NONE", "NONE", "NONE", "NONE", "DRAW"]
Explanation: All cells are filled without any row, column, or diagonal being completed by a single player.
Input: (1, [("move", 0, 0, 3), ("move", 0, 0, 2), ("undo",), ("move", 0, 0, 1)])
Expected Output: ["INVALID", "P2", "UNDONE", "P1"]
Explanation: Player 3 is invalid. On a 1x1 board, the first valid move wins immediately. Undo reopens the game, allowing the last move.
Input: (3, [("move", 0, 0, 1), ("move", 1, 1, 2), ("reset",), ("undo",), ("move", 2, 2, 1)])
Expected Output: ["NONE", "NONE", "RESET", "INVALID", "NONE"]
Explanation: Reset clears both the board and move history, so the following undo is invalid.
Input: (2, [("move", 0, 0, 1), ("undo", 1), ("foo",), ("reset",), ("move", 1, 1, 2)])
Expected Output: ["NONE", "INVALID", "INVALID", "RESET", "NONE"]
Explanation: Malformed and unknown commands are invalid and do not affect the board. Reset clears the earlier move.
Solution
def solution(n, operations):
def is_valid_int(x):
return isinstance(x, int) and not isinstance(x, bool)
size = max(n, 0)
rows = [0] * size
cols = [0] * size
row_ver = [0] * size
col_ver = [0] * size
diag = 0
anti = 0
diag_ver = 0
anti_ver = 0
version = 1
board = {}
history = []
moves = 0
game_over = False
results = []
for op in operations:
if not isinstance(op, (list, tuple)) or len(op) == 0:
results.append("INVALID")
continue
cmd = op[0]
if cmd == "move":
if len(op) != 4:
results.append("INVALID")
continue
row, col, player = op[1], op[2], op[3]
if not (is_valid_int(row) and is_valid_int(col) and is_valid_int(player)):
results.append("INVALID")
continue
if player not in (1, 2):
results.append("INVALID")
continue
if row < 0 or row >= n or col < 0 or col >= n:
results.append("INVALID")
continue
if game_over or (row, col) in board:
results.append("INVALID")
continue
delta = 1 if player == 1 else -1
if row_ver[row] != version:
rows[row] = 0
row_ver[row] = version
rows[row] += delta
row_total = rows[row]
if col_ver[col] != version:
cols[col] = 0
col_ver[col] = version
cols[col] += delta
col_total = cols[col]
diag_total = None
anti_total = None
if row == col:
if diag_ver != version:
diag = 0
diag_ver = version
diag += delta
diag_total = diag
if row + col == n - 1:
if anti_ver != version:
anti = 0
anti_ver = version
anti += delta
anti_total = anti
board[(row, col)] = delta
history.append((row, col, delta))
moves += 1
if row_total == n or col_total == n or diag_total == n or anti_total == n:
game_over = True
results.append("P1")
elif row_total == -n or col_total == -n or diag_total == -n or anti_total == -n:
game_over = True
results.append("P2")
elif moves == n * n:
game_over = True
results.append("DRAW")
else:
results.append("NONE")
elif cmd == "undo":
if len(op) != 1 or not history:
results.append("INVALID")
continue
row, col, delta = history.pop()
board.pop((row, col), None)
if row_ver[row] != version:
rows[row] = 0
row_ver[row] = version
rows[row] -= delta
if col_ver[col] != version:
cols[col] = 0
col_ver[col] = version
cols[col] -= delta
if row == col:
if diag_ver != version:
diag = 0
diag_ver = version
diag -= delta
if row + col == n - 1:
if anti_ver != version:
anti = 0
anti_ver = version
anti -= delta
moves -= 1
game_over = False
results.append("UNDONE")
elif cmd == "reset":
if len(op) != 1:
results.append("INVALID")
continue
version += 1
board = {}
history = []
moves = 0
game_over = False
results.append("RESET")
else:
results.append("INVALID")
return resultsTime complexity: O(len(operations)) total on average, with O(1) average work per command. Space complexity: O(n + k), where k is the number of currently occupied cells (and equivalently the current valid move history size).
Hints
- Track each row and column with a running balance: +1 for player 1 and -1 for player 2. If any absolute value reaches n, that player has won.
- For undo, store each valid move on a stack so you can subtract its contribution from the row, column, and diagonal counters.