How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Databricks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Databricks during technical interviews.

Design BFS to detect forced win in Tic-Tac-Toe

Quick Overview

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.

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.

Input: (["X.O", "...", "..."], "O", 3, 0)

Expected Output: False

Explanation: O does not already have a winning line, and with t = 0 it cannot make any move.

Input: (["OOO", "X..", "..."], "X", 3, 2)

Expected Output: False

Explanation: The opponent already has a winning line, so the answer is False before any search.

Input: (["XXX", "OOO", "..."], "X", 3, 1)

Expected Output: True

Explanation: By the stated rule, if the current player already has a winning line, return True even if the opponent also has one.

Input: (["X..", ".O.", "..."], "X", 3, 1)

Expected Output: False

Explanation: X cannot complete three in a row with only one move from this position.

Input: (["."], "X", 1, 1)

Expected Output: True

Explanation: With k = 1, placing X in the only cell wins immediately.

Solution

def solution(board, player, k, t):
    from collections import deque
    from functools import lru_cache

    n = len(board)
    board = tuple(board)
    opponent = 'O' if player == 'X' else 'X'

    @lru_cache(None)
    def has_win(state, mark):
        for i in range(n):
            for j in range(n):
                if state[i][j] != mark:
                    continue
                if j + k <= n and all(state[i][j + d] == mark for d in range(k)):
                    return True
                if i + k <= n and all(state[i + d][j] == mark for d in range(k)):
                    return True
                if i + k <= n and j + k <= n and all(state[i + d][j + d] == mark for d in range(k)):
                    return True
                if i + k <= n and j - k + 1 >= 0 and all(state[i + d][j - d] == mark for d in range(k)):
                    return True
        return False

    if has_win(board, player):
        return True
    if has_win(board, opponent):
        return False
    if t == 0:
        return False

    root = (board, player, t)
    queue = deque([root])
    visited = {root}
    order = []
    children = {}

    while queue:
        state = queue.popleft()
        order.append(state)
        state_board, turn, rem = state

        if has_win(state_board, player) or has_win(state_board, opponent) or rem == 0:
            children[state] = []
            continue

        empties = []
        for i in range(n):
            for j, cell in enumerate(state_board[i]):
                if cell == '.':
                    empties.append((i, j))

        if not empties:
            children[state] = []
            continue

        next_turn = opponent if turn == player else player
        next_states = []

        for i, j in empties:
            rows = list(state_board)
            row = rows[i]
            rows[i] = row[:j] + turn + row[j + 1:]
            child_board = tuple(rows)
            child_rem = rem - 1 if turn == player else rem
            child = (child_board, next_turn, child_rem)
            next_states.append(child)
            if child not in visited:
                visited.add(child)
                queue.append(child)

        children[state] = next_states

    value = {}
    for state in reversed(order):
        state_board, turn, rem = state

        if has_win(state_board, player):
            value[state] = True
            continue
        if has_win(state_board, opponent):
            value[state] = False
            continue
        if rem == 0:
            value[state] = False
            continue
        if not any('.' in row for row in state_board):
            value[state] = False
            continue

        if turn == player:
            value[state] = any(value[child] for child in children[state])
        else:
            value[state] = all(value[child] for child in children[state])

    return value[root]

Time complexity: O(S * n^3), where S is the number of reachable states explored within the move limit. Space complexity: O(S * n^2).

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.

Quick Overview