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.

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

Hints

  1. Only the latest valid move can create a new 3-in-a-row, so you never need to rescan the entire board.
  2. 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.

Loading coding console...