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 Technical Screen rounds at Google.

What role is this question designed for?

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

Design Tic-Tac-Toe With K Players | Google Coding Question

Design Tic-Tac-Toe With K Players

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design and implement a Tic-Tac-Toe game engine. You are given: - `k` players, each with a unique player ID or mark. - An `n x n` board, initially empty. - Players take turns placing their own mark on an empty cell. Unlike classic Tic-Tac-Toe, a player wins as soon as they form **3 consecutive marks** in a straight line, regardless of how large `n` is. A straight line may be horizontal, vertical, diagonal down-right, or diagonal down-left. Implement a class or set of functions that supports making moves and returns the game status after each move, such as: - `"Game Over"` if a move is attempted after the game has ended. - `"<player> won"` when the latest move causes that player to have 3 consecutive marks. - A non-terminal status such as `"Continue"` if the game should keep going. Your implementation should handle invalid moves, such as placing a mark outside the board or on an occupied cell. Discuss the time and space complexity of your approach, especially for large `n`.

Quick Answer: This question evaluates a candidate's ability to design and implement a game engine, manage board state and turn logic, validate moves, and apply efficient data structures and algorithms for win detection within the Coding & Algorithms domain.

Design a Tic-Tac-Toe game engine for k players on an n x n board. The board starts empty, and players must play in cyclic order: player 1, player 2, ..., player k, then back to player 1. A player wins immediately when their latest valid move creates 3 consecutive marks in a straight line. A straight line may be horizontal, vertical, diagonal down-right, or diagonal down-left. For this problem, implement a function that processes a list of move attempts and returns the status after each attempt. Each move is given as [player, row, col] using 0-based indexing. Return one status string per move: - "Game Over" if a move is attempted after someone has already won. - "Invalid move" if the move is not legal. A move is invalid if: - the player ID is not in [1, k] - it is not that player's turn - the cell is outside the board - the cell is already occupied - "<player> won" if the move is valid and causes that player to have 3 consecutive marks - "Continue" if the move is valid and the game should continue Important: an invalid move does not change the board and does not advance the turn. You do not need to detect draws. If no one wins, valid moves simply return "Continue".

Constraints

1 <= n <= 10^9
1 <= k <= 10^5
0 <= len(moves) <= 2 * 10^5
Each move is a list of three integers: [player, row, col]
Row and column in the input may be outside the board and should then be treated as an invalid move
Your approach should be efficient for large n, so avoid scanning the whole board after every move

Examples

Input: (3, 2, [])

Expected Output: []

Explanation: No moves are made, so there are no statuses to report.

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

Expected Output: ['Continue', 'Continue', 'Continue', 'Continue', '1 won', 'Game Over']

Explanation: Player 1 forms three consecutive marks horizontally at (0,0), (0,1), and (0,2). Any later move returns 'Game Over'.

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

Expected Output: ['Continue', 'Invalid move', 'Continue', 'Continue', 'Invalid move', 'Continue', 'Continue']

Explanation: The second move is invalid because the cell is occupied. Since invalid moves do not advance the turn, the fifth move is also invalid because it is still player 2's turn.

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

Expected Output: ['Continue', 'Continue', 'Continue', 'Continue', 'Continue', 'Continue', '1 won']

Explanation: Player 1 wins on the down-left diagonal with marks at (0,4), (1,3), and (2,2).

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

Expected Output: ['Continue', 'Invalid move', 'Continue', 'Continue']

Explanation: The second move is outside the 2x2 board. Since the board is smaller than 3x3, no player can ever form 3 consecutive marks.

Hints

Only the latest valid move can create a new 3-in-a-row, so you never need to rescan the entire board.
For large boards, store only occupied cells in a hash map keyed by (row, col), then check the 4 line directions around the new move.

Quick Overview

This question evaluates a candidate's ability to design and implement a game engine, manage board state and turn logic, validate moves, and apply efficient data structures and algorithms for win detection within the Coding & Algorithms domain.