Quick Overview

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.

Design an efficient Tic-Tac-Toe engine

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Design a Tic-Tac-Toe engine on an n x n board. Implement move(row, col, player) -> result where result indicates no winner, player1 wins, player2 wins, or invalid move. Achieve O( 1) time per move and O(n) space by maintaining minimal state. Extend the API to support reset() and an optional undo(). Write comprehensive tests for edge cases (repeated moves, out-of-bounds, early wins, and filled board with no winner).

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.

Design a Tic-Tac-Toe engine for an n x n board. Implement a function solution(n, operations) that processes engine commands in order and returns the result of each command. Supported commands: - ("move", row, col, player): place player 1 or player 2 at (row, col). - ("undo",): remove the last valid move. - ("reset",): clear the board and the move history. Return values: - "NONE": valid move, no winner yet. - "P1": player 1 wins on this move. - "P2": player 2 wins on this move. - "DRAW": the board becomes full and nobody wins. - "INVALID": invalid command or invalid move. - "UNDONE": undo succeeded. - "RESET": reset succeeded. A move is invalid if: - row or col is out of bounds, - the cell is already occupied, - player is not 1 or 2, - or the game has already ended in a win or draw. Turn order is not enforced; the player number is supplied in each move command. Your engine must detect wins efficiently without scanning entire rows, columns, or diagonals after every move. The classic win-tracking state should be O(n), while repeated-move detection and undo support may store occupied cells and move history.

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.

Hints

  1. 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.
  2. For undo, store each valid move on a stack so you can subtract its contribution from the row, column, and diagonal counters.

Loading coding console...