Skip to main content

91. Design Tic-Tac-Toe

mediumAsked at Workday

Design an efficient Tic-Tac-Toe game. Workday uses this for incremental-state-tracking — same shape as maintaining running sums for the 'all approvals received?' check across multi-axis approval matrices.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday workflow-team SDE2 onsite.

Problem

Assume the following rules are for the tic-tac-toe game on an n x n board between two players: a move is guaranteed to be valid; once a winning condition is reached, no more moves are allowed. Implement TicTacToe(n). int move(row, col, player) returns the current winning condition (0 if no one yet, 1 if player 1 wins, 2 if player 2 wins).

Constraints

  • 2 <= n <= 100
  • player is 1 or 2
  • Follow-up: Could you do better than O(n^2) per move?

Examples

Example 1

Input
n=3, move(0,0,1)=0, move(0,2,2)=0, move(2,2,1)=0, move(1,1,2)=0, move(2,0,1)=0, move(1,0,2)=0, move(2,1,1)=1
Output
0,0,0,0,0,0,1

Explanation: Player 1 wins via the bottom row.

Approaches

1. Scan board on each move

After each move, scan the affected row/col/diagonal.

Time
O(n) per move
Space
O(n^2) board)
// post-move scan of the relevant row, column, and possibly diagonals

Tradeoff: O(n) per move. Fine but the follow-up asks for O(1).

2. Incremental counters

Track per-row, per-col, anti-diagonal, and main-diagonal sum counters. Player 1 adds +1, player 2 adds -1. Counter hitting ±n means a win.

Time
O(1) per move
Space
O(n)
class TicTacToe {
  constructor(n) {
    this.n = n;
    this.rows = new Array(n).fill(0);
    this.cols = new Array(n).fill(0);
    this.diag = 0;
    this.anti = 0;
  }
  move(row, col, player) {
    const v = player === 1 ? 1 : -1;
    this.rows[row] += v;
    this.cols[col] += v;
    if (row === col) this.diag += v;
    if (row + col === this.n - 1) this.anti += v;
    const target = player === 1 ? this.n : -this.n;
    if (this.rows[row] === target || this.cols[col] === target || this.diag === target || this.anti === target) return player;
    return 0;
  }
}

Tradeoff: O(1) per move, O(n) memory. The signed counter trick handles both players in one variable per row/col/diagonal.

Workday-specific tips

Workday wants the O(1) per move version. The signed-counter (+1 for player 1, -1 for player 2) is the clever bit — articulate it before coding.

Common mistakes

  • Maintaining separate counters per player — works but doubles memory.
  • Forgetting the anti-diagonal (row + col == n - 1).
  • Scanning instead of tracking incrementally.

Follow-up questions

An interviewer at Workday may pivot to one of these next:

  • Tic-Tac-Toe with arbitrary number of players.
  • Connect Four (variable winning length).
  • Detect a tie before move limit.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why signed counters?

+1 / -1 lets one variable track both players. Sum == n means n moves by player 1 in that row; sum == -n means n moves by player 2.

What if the move is on a diagonal AND main row?

All applicable counters update. Each check is O(1), so multiple updates per move is still constant time.

Practice these live with InterviewChamp.AI

Drill Design Tic-Tac-Toe and other Workday interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →