Katkat
Back

Implement an Alternating Tic-Tac-Toe Game

DatabricksSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design a robust state machine for a board game, focusing on efficient win-condition checking and clean API design.

Problem Statement

Implement a class TicTacToe that manages a standard 3x3 game. Two players, 'X' and 'O', take turns placing their marks on an empty cell. The game should detect a winner or a draw and prevent illegal moves.

Requirements

  1. __init__(): Initialize an empty 3x3 board.
  2. move(row: int, col: int, player: str) -> str:
    • Places the player's mark on the board.
    • Returns the result of the move: "Success", "Win", "Draw", or "Invalid".
    • A move is invalid if the coordinates are out of bounds, the cell is already occupied, or if it is not the correct player's turn.

Example

game = TicTacToe()
game.move(0, 0, 'X') # Returns "Success"
game.move(0, 1, 'O') # Returns "Success"
game.move(1, 1, 'X') # Returns "Success"
game.move(0, 2, 'O') # Returns "Success"
game.move(2, 2, 'X') # Returns "Win" (Diagonal X-X-X)

Constraints

  • Coordinates are always 0-indexed (0 to 2).
  • The game must strictly enforce that 'X' always goes first.

Edge Cases

  • Attempting to move after the game has already concluded.
  • Trying to overwrite an existing mark.
  • Filling the board without a winner (Draw).

Hints

Hint 1

Use a 2D list or a flat list to represent the board and a variable to track whose turn it is.

Hint 2

Instead of iterating the whole board after every move, check only the row, column, and two diagonals associated with the most recent move.

Hint 3

Maintain a move counter to easily identify when a 'Draw' condition is reached.

Follow-up questions

  • How would you modify your code to support an N x N board where the winning condition remains getting N marks in a row?
  • If this were a multi-threaded web service, how would you handle concurrent moves from two players?
  • How would you implement an 'undo' feature to revert the last move?