PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates a candidate's ability to design a class-based data structure that tracks game state and efficiently detects a win condition after each move. It tests object-oriented design and algorithmic thinking around incremental state updates, a common focus in coding interviews for object design problems. The question requires practical implementation skill rather than purely theoretical knowledge.

  • medium
  • Databricks
  • Coding & Algorithms
  • Software Engineer

Design an n x n Tic-Tac-Toe Game

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Design an n x n Tic-Tac-Toe Game Implement a class that powers a game of Tic-Tac-Toe on an `n x n` board for two players. Two players take turns placing their marks on empty cells of the board. After each move you must report whether the move that was just played won the game. A player **wins** as soon as they place `n` of their own marks in a straight line — that is, any single move that completes: - an entire **row**, or - an entire **column**, or - the **main diagonal** (top-left to bottom-right), or - the **anti-diagonal** (top-right to bottom-left). A move never needs to be validated for being "out of turn"; assume the caller alternates players correctly and never plays the same cell twice. ### Class interface Implement a class `TicTacToe` with the following methods: - `TicTacToe(n)` — initializes the game on an empty `n x n` board. - `move(row, col, player) -> int` — the given `player` places a mark at cell `(row, col)` (0-indexed). Return: - `player` (either `1` or `2`) if this move causes that player to win, or - `0` if the game does not yet have a winner after this move. ### Constraints - `2 <= n <= 1000` - `0 <= row, col < n` - `player` is either `1` or `2`. - Each call to `move` is on a previously empty cell. - There can be up to `10^5` calls to `move`. - Once a winning move occurs the game is over; the grader will not call `move` again after a win. ### Example ```text Input: TicTacToe(3) move(0, 0, 1) -> 0 // player 1 plays top-left move(0, 2, 2) -> 0 // player 2 plays top-right move(2, 2, 1) -> 0 // player 1 move(1, 1, 2) -> 0 // player 2 plays center move(2, 0, 1) -> 0 // player 1 move(1, 0, 2) -> 0 // player 2 move(2, 1, 1) -> 1 // player 1 completes the bottom row -> player 1 wins Output (return values, in order): 0, 0, 0, 0, 0, 0, 1 ``` ### Output format For each `move` call, return the integer described above (the winning player number, or `0`). A correct solution that simply scans the affected row, column, and diagonals after each move is acceptable. Aim for a clean, working implementation; an `O(1)`-per-move counting approach is a nice optimization but is not required.

Quick Answer: This question evaluates a candidate's ability to design a class-based data structure that tracks game state and efficiently detects a win condition after each move. It tests object-oriented design and algorithmic thinking around incremental state updates, a common focus in coding interviews for object design problems. The question requires practical implementation skill rather than purely theoretical knowledge.

Implement a class that powers a game of Tic-Tac-Toe on an `n x n` board for two players. Two players take turns placing their marks on empty cells. After each move, report whether the move just played won the game. A player **wins** as soon as they place `n` of their own marks in a straight line — completing an entire **row**, an entire **column**, the **main diagonal** (top-left to bottom-right), or the **anti-diagonal** (top-right to bottom-left). Assume the caller alternates players correctly and never plays the same cell twice; you do not need to validate turns. ### Class interface - `TicTacToe(n)` — initializes the game on an empty `n x n` board. - `move(row, col, player) -> int` — `player` places a mark at cell `(row, col)` (0-indexed). Return `player` (1 or 2) if this move causes that player to win, otherwise `0`. ### Harness driver This console drives your class through a `solution(operations, arguments)` function. `operations` is a list of method names (`"TicTacToe"` then a series of `"move"`), and `arguments` is a parallel list of argument lists (`[n]` for the constructor, `[row, col, player]` for each move). Return a list whose i-th entry is the constructor result (`None`/`null`) or the value returned by `move`. ### Example ```text operations = ["TicTacToe","move","move","move","move","move","move","move"] arguments = [[3],[0,0,1],[0,2,2],[2,2,1],[1,1,2],[2,0,1],[1,0,2],[2,1,1]] returns -> [None, 0, 0, 0, 0, 0, 0, 1] ``` Player 1 completes the bottom row on the final move and wins.

Constraints

  • 2 <= n <= 1000
  • 0 <= row, col < n
  • player is either 1 or 2
  • Each move() call targets a previously empty cell
  • Up to 10^5 calls to move()
  • No move() is called after a winning move

Examples

Input: (['TicTacToe','move','move','move','move','move','move','move'], [[3],[0,0,1],[0,2,2],[2,2,1],[1,1,2],[2,0,1],[1,0,2],[2,1,1]])

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

Explanation: The worked example: player 1 completes the bottom row (2,0),(2,1),(2,2) on the final move and wins.

Input: (['TicTacToe','move','move','move','move','move','move'], [[3],[0,0,1],[0,1,2],[1,0,1],[1,1,2],[2,2,1],[2,1,2]])

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

Explanation: Player 2's marks at (0,1),(1,1),(2,1) complete column 1, so the last move returns 2.

Input: (['TicTacToe','move','move','move','move','move'], [[3],[0,0,1],[0,1,2],[1,1,1],[0,2,2],[2,2,1]])

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

Explanation: Player 1 fills the main diagonal (0,0),(1,1),(2,2); the third of those moves wins.

Input: (['TicTacToe','move','move','move','move','move','move'], [[3],[0,0,1],[0,2,2],[1,0,1],[1,1,2],[2,1,1],[2,0,2]])

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

Explanation: Player 2 completes the anti-diagonal (0,2),(1,1),(2,0), so the final move returns 2.

Input: (['TicTacToe','move','move','move'], [[2],[0,0,1],[1,0,2],[0,1,1]])

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

Explanation: Boundary n=2: player 1's (0,0) and (0,1) complete row 0, so the last move wins.

Input: (['TicTacToe','move'], [[3],[1,1,1]])

Expected Output: [None, 0]

Explanation: Minimal case: a single central move on a 3x3 board cannot complete any line of length 3, so it returns 0.

Hints

  1. You do not need to store the full board. Track a running total per row and per column, plus one for each diagonal.
  2. Encode player 1 as +1 and player 2 as -1. A line is complete for player 1 when its sum reaches +n and for player 2 when it reaches -n, so check abs(sum) == n.
  3. Cell (row, col) is on the main diagonal when row == col, and on the anti-diagonal when row + col == n - 1. Update those counters only when the move lands on them.
  4. After updating the four affected counters, the move wins if any of them hits magnitude n — return the player; otherwise return 0.
Last updated: Jul 1, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • IPv4 CIDR Range Membership Queries - Databricks (medium)
  • Optimal Commute: Nearest Transit Distance in a City Grid - Databricks (medium)
  • Choose the Best Travel Mode - Databricks (medium)
  • Implement an Alternating Tic-Tac-Toe Game - Databricks (hard)
  • Implement a Snapshot Set Iterator - Databricks (medium)