Tic Tac Toe Winner in O(n) | Dataford Interview Questions

Didi Labs wants to validate game states for a generalized Tic Tac Toe surface. Given an n x n board, determine whether X or O has won, whether the game is still pending, or whether the board is a draw.

A player wins when every cell in any complete row, column, or one of the two main diagonals contains that player's mark. The board is guaranteed to represent a valid game state, so both players cannot have winning lines simultaneously.

Formal Specification

Implement tic_tac_toe_winner(board), where board is a square list of lists containing only "X", "O", and ".". Return exactly one of "X", "O", "Pending", or "Draw".

Use at most O(n) auxiliary space. The input board itself does not count toward auxiliary space.

Constraints

1 <= n <= 10^5
board has exactly n rows and n columns
Each cell is one of "X", "O", or "."
The board represents a valid game state
Use at most O(n) auxiliary space

Function Signature

def tic_tac_toe_winner(board):

Your question is Tic Tac Toe Winner in O(n). Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem