How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Databricks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Databricks during technical interviews.

Design an efficient Tic-Tac-Toe engine | Databricks Coding Question

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.

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.

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.

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.