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 hard 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.

Implement a Tic-Tac-Toe game API | Databricks Coding Question

Implement a Tic-Tac-Toe game API

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

## Problem Design and implement a Tic-Tac-Toe game class that supports playing moves on an `n x n` board. ### Requirements - Two players, represented by integers `1` and `2`. - Method `move(row, col, player)` places the player's mark at `(row, col)`. - After each move, return: - `0` if there is no winner yet, - `1` if player 1 wins, - `2` if player 2 wins. ### Rules - A player wins if they fill an entire row, column, or either diagonal. - Moves are guaranteed to be valid (no repeats, within bounds). ### Constraints / Follow-ups - Aim for **O(1)** time per move (not O(n^2) scanning). - Use O(n) additional memory if possible. ### Example For `n = 3`: - `move(0,0,1) -> 0` - `move(0,2,2) -> 0` - `move(2,2,1) -> 0` - `move(1,1,2) -> 0` - `move(2,0,1) -> 0` - `move(1,0,2) -> 0` - `move(2,1,1) -> 1` (player 1 completes bottom row)

Quick Answer: This question evaluates implementation skills in data structures and algorithmic optimization, focusing on efficient state tracking and constant-time update strategies for game logic on an n×n Tic-Tac-Toe board.

Design the core logic for a Tic-Tac-Toe game on an n x n board. Instead of writing a class, write a function that simulates the API behavior. You are given the board size n and a list of moves. Each move is a tuple (row, col, player), representing a call to move(row, col, player). For each move, return: - 0 if no player has won yet, - 1 if player 1 wins on that move, - 2 if player 2 wins on that move. A player wins by filling an entire row, an entire column, the main diagonal, or the anti-diagonal. Your solution should aim for O(1) time per move rather than scanning the whole board after every move.

Constraints

1 <= n
0 <= len(moves) <= n^2
Each move is a tuple (row, col, player) with 0 <= row, col < n
player is either 1 or 2
Moves are valid: no cell is played more than once

Examples

Input: (3, [(0,0,1), (0,2,2), (2,2,1), (1,1,2), (2,0,1), (1,0,2), (2,1,1)])

Expected Output: [0, 0, 0, 0, 0, 0, 1]

Explanation: Player 1 completes the bottom row on the last move.

Input: (1, [(0,0,2)])

Expected Output: [2]

Explanation: On a 1 x 1 board, the first move fills the only row, column, and both diagonals, so player 2 wins immediately.

Input: (4, [(0,1,1), (0,0,2), (1,0,1), (1,1,2), (2,3,1), (2,2,2), (3,2,1), (3,3,2)])

Expected Output: [0, 0, 0, 0, 0, 0, 0, 2]

Explanation: Player 2 fills the main diagonal: (0,0), (1,1), (2,2), (3,3).

Input: (3, [(0,0,1), (0,2,2), (1,0,1), (1,1,2), (2,2,1), (2,0,2)])

Expected Output: [0, 0, 0, 0, 0, 2]

Explanation: Player 2 completes the anti-diagonal: (0,2), (1,1), (2,0).

Input: (3, [(0,1,2), (0,0,1), (1,1,2), (1,0,1), (2,2,2), (2,0,1)])

Expected Output: [0, 0, 0, 0, 0, 1]

Explanation: Player 1 completes column 0 with cells (0,0), (1,0), and (2,0).

Hints

You do not need to store the full board. Track counts for each row, each column, and the two diagonals.
Try adding +1 for player 1 and -1 for player 2. If any tracked count reaches n or -n, that player has won.

Quick Overview

This question evaluates implementation skills in data structures and algorithmic optimization, focusing on efficient state tracking and constant-time update strategies for game logic on an n×n Tic-Tac-Toe board.