Tic-Tac-Toe
Design a tic-tac-toe game for any board size, with an O(1) winning check per move that uses line counters.
Requirements
Tic-tac-toe looks tiny, which is why interviewers use it: there is little to hide behind. Ask first, then fix the scope.
Questions worth asking:
- Is the board always 3x3, or any size N x N? (Design for N, it costs almost nothing.)
- How many players? (Two, taking turns, marks X and O.)
- What wins? (N of the same mark in one row, one column or one of the two diagonals.)
- What happens on an invalid move? (Reject it and let the same player try again.)
- Is there a UI? (Out of scope. We need a way to show the board, not a window.)
Scope for this lesson:
- Board of size N x N, two players, alternating turns.
- A move is a row and a column, counted from 0.
- The game ends in a win or a draw (board full, nobody won).
- Moves on a taken cell, off the board, or after the game ended are rejected.
Out of scope: network play, an AI opponent, undo, a graphical UI.
1 of 9