Katkat
Back

Design Tic-Tac-Toe With K Players

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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