Design BFS to detect forced win in Tic-Tac-Toe
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an n×n Tic-Tac-Toe–like board and a target k (1 ≤ k ≤ n). From the current board state and the player to move, design an algorithm to determine whether the current player can force a win within at most t moves. Use a breadth-first search over game states: specify the state representation, successor generation, win/draw detection, and how you avoid revisiting equivalent states (e.g., hashing or symmetry reduction). Describe any pruning or move-ordering heuristics you would apply. Analyze the worst-case time and space complexity in terms of n, k, t, and the branching factor, and also provide the complexities for the standard 3×3, k=3 case.
Quick Answer: This question evaluates algorithm design and search-space reasoning, focusing on BFS-based game-tree exploration, state representation, symmetry reduction and hashing, win/draw detection, pruning and move-ordering heuristics, and time/space complexity analysis in terms of n, k, t, and the branching factor within the Coding & Algorithms domain.
You are given an n x n Tic-Tac-Toe-like board, the player to move, a target length k, and a limit t. Two players alternate placing their mark in an empty cell. A player wins as soon as they create k consecutive identical marks horizontally, vertically, or diagonally. Return whether the current player can force a win within at most t of their own moves, assuming both sides play optimally. If the current player already has a winning line, return True. If the opponent already has one, return False. Use the provided player as the side to move even if the counts of 'X' and 'O' on the board are unusual. A strong solution expands reachable states breadth-first up to the depth limit, hashes or canonicalizes states to avoid revisits, and then evaluates states from deepest to shallowest: on the current player's turn, one winning child is enough; on the opponent's turn, every child must still be winning. Early terminal checks and symmetry reduction are valid pruning ideas.
Constraints
- 1 <= n <= 4 and 1 <= k <= n
- 0 <= t <= 3
- board is square, contains only '.', 'X', and 'O', and the input position has at most one winner already present
Examples
Input: (["XX.", "OO.", "..."], "X", 3, 1)
Expected Output: True
Explanation: X places at the last cell of the top row to form XXX immediately.
Input: (["X..", ".O.", "..X"], "X", 3, 2)
Expected Output: True
Explanation: X can play in the top-right corner (or symmetrically bottom-left), creating two separate one-move threats. O can block only one, so X wins on its second move.
Hints
- Build the game graph level by level only up to the move limit, then evaluate it backward. On your turn use any(...); on the opponent's turn use all(...).
- A board plus whose turn it is is a state. To avoid repeated work, hash states; for extra pruning, canonicalize the board under the 8 rotations/reflections of a square.