DeepInterview

Description

Company: Databricks

Problem Statement

Create a Tic-Tac-Toe game class. It must follow these rules:

Requirements

Board Setup:

The board size is M x N. It might not be a square.
A player needs K marks in a row to win. K can be any number.

Main Functions:

Create a TicTacToe class. The constructor takes the board size and the winning number K.
Create a move(i, j) method. This method should:
- Put the current player's mark at row i and column j.
- Print the board.
- Print "Player X won" if someone wins.
- Return the winner (1 for Player 1, 2 for Player 2, or 0 if the game is still going).

Rules:

Player 1 and Player 2 take turns.
Assume all moves are valid (you do not need to check for errors).
Check if someone won after every move.
A player wins by connecting K marks in:
- A row
- A column
- The main diagonal (top-left to bottom-right)
- The anti-diagonal (bottom-left to top-right)

Usage Example

TicTacToe game = new TicTacToe(3, 4, 3); // 3x4 board, need 3 to win

game.move(0, 0); // Player 1
Board:
|  X  |     |     |     |
|     |     |     |     |
|     |     |     |     |

game.move(0, 1); // Player 2
Board:
|  X  |  O  |     |     |
|     |     |     |     |
|     |     |     |     |

game.move(1, 0); // Player 1
Board:
|  X  |  O  |     |     |
|  X  |     |     |     |
|     |     |     |     |

game.move(1, 1); // Player 2
Board:
|  X  |  O  |     |     |
|  X  |  O  |     |     |
|     |     |     |     |

game.move(2, 0); // Player 1
Board:
|  X  |  O  |     |     |
|  X  |  O  |     |     |
|  X  |     |     |     |
Player 1 won

Input Limits

M and N are between 2 and 100.
K is at least 2 and cannot be bigger than the board size.
Players are defined as 1 and 2.
i and j are valid coordinates inside the board.
Speed is not the main goal.

Solution Details

How It Works

Board Data: Use a 2D array. 0 is empty, 1 is Player 1, and 2 is Player 2.
Making a Move:
- Save the mark on the board.
- Show the board.
- Look in 4 directions from the new mark to see if the player won.
- If yes, return the winner.
Checking for a Win: After a move at (row, col), check for K connected marks in:
- Horizontal (Left + Right)
- Vertical (Up + Down)
- Diagonal (Top-Left + Bottom-Right)
- Anti-Diagonal (Bottom-Left + Top-Right)
Checking for a Draw: The game is a draw if the board is full and no one won.
Note: You do not need to check if a win is mathematically impossible early on. Just check if the board is full.

Time Performance

Constructor: O(M × N) to build the empty board.
move(): O(max(M, N)) to scan the lines for a winner.
Total: O(M × N) for the whole game.

Space Usage

O(M × N) to store the board in memory.

Code Implementation

class TicTacToe:
    def __init__(self, M: int, N: int, K: int):
        """
        Setup M x N board. Need K marks to win.
        """
        self.rows = M
        self.cols = N
        self.k = K
        self.board = [[0] * N for _ in range(M)]
        self.current_player = 1  # Player 1 goes first
        self.game_over = False

    def move(self, i: int, j: int) -> int:
        """
        Place mark at (i, j). Print board and check winner.
        Returns: 0 (no winner), 1 (player 1 wins), 2 (player 2 wins)
        """
        if self.game_over:
            print("Game is already over!")
            return 0

        # Place the mark
        self.board[i][j] = self.current_player

        # Print the board
        self._print_board()

        # Check for winner
        if self._check_win(i, j):
            print(f"Player {self.current_player} won")
            self.game_over = True
            return self.current_player

        # Switch player
        self.current_player = 3 - self.current_player  # Toggle between 1 and 2

        return 0

    def _print_board(self):
        """Print the board visually."""
        symbols = {0: '   ', 1: ' X ', 2: ' O '}
        print("\nBoard:")
        for row in self.board:
            print('|' + '|'.join(symbols[cell] for cell in row) + '|')
        print()

    def _check_win(self, row: int, col: int) -> bool:
        """
        Check if the last move at (row, col) caused a win.
        """
        player = self.current_player

        # Check all 4 directions
        directions = [
            (0, 1),   # Horizontal
            (1, 0),   # Vertical
            (1, 1),   # Main diagonal
            (1, -1)   # Anti-diagonal
        ]

        for dr, dc in directions:
            count = 1  # Count the current spot

            # Count going forward
            count += self._count_consecutive(row, col, dr, dc, player)

            # Count going backward
            count += self._count_consecutive(row, col, -dr, -dc, player)

            if count >= self.k:
                return True

        return False

    def _count_consecutive(self, row: int, col: int, dr: int, dc: int, player: int) -> int:
        """
        Count how many marks match in one direction.
        """
        count = 0
        r, c = row + dr, col + dc

        while 0 <= r < self.rows and 0 <= c < self.cols and self.board[r][c] == player:
            count += 1
            r += dr
            c += dc

        return count

# Example usage
if __name__ == "__main__":
    game = TicTacToe(3, 4, 3)

    game.move(0, 0)  # Player 1
    game.move(0, 1)  # Player 2
    game.move(1, 0)  # Player 1
    game.move(1, 1)  # Player 2
    game.move(2, 0)  # Player 1 wins

Extension: Adding an AI

Add an AI player that plays automatically.

New Requirements

Update Constructor:

Add a parameter isAI.
Signature: TicTacToe(int M, int N, int K, boolean isAI).

AI Logic:

If isAI is true, Player 2 is the computer.
The AI picks a valid empty spot.
The game ends when someone wins or draws.

Update `move()`:

When a human plays (Player 1), the AI should immediately play afterwards (Player 2).

Draws:

If the board is full and no one wins, print "Draw".

AI Logic

The AI decides where to move in this order:

Win: If the AI can win right now, take that spot.
Block: If the human can win on their next turn, block that spot.
Random: If neither of the above, pick a random empty spot.

Code Implementation

import random
from typing import Optional, Tuple

class TicTacToeWithAI:
    def __init__(self, M: int, N: int, K: int, isAI: bool = False):
        """
        Setup board. If isAI is True, Player 2 is computer.
        """
        self.rows = M
        self.cols = N
        self.k = K
        self.board = [[0] * N for _ in range(M)]
        self.current_player = 1  # Player 1 starts (human)
        self.game_over = False
        self.is_ai_enabled = isAI
        self.ai_player = 2  # AI is Player 2

    def move(self, i: int, j: int) -> int:
        """
        Human move at (i, j). If AI is on, AI moves immediately after.
        """
        if self.game_over:
            print("Game is already over!")
            return 0

        # Place the mark
        result = self._make_move(i, j)

        if result != 0:  # Game ended (win or draw)
            return result

        # If AI is enabled and it's now AI's turn, make AI move
        if self.is_ai_enabled and self.current_player == self.ai_player:
            return self._ai_move()

        return 0

    def _make_move(self, i: int, j: int) -> int:
        """
        Helper to place mark and check result.
        """
        # Place the mark
        self.board[i][j] = self.current_player

        # Print the board
        self._print_board()

        # Check for winner
        if self._check_win(i, j):
            print(f"Player {self.current_player} won")
            self.game_over = True
            return self.current_player

        # Check for draw
        if self._is_board_full():
            print("Draw")
            self.game_over = True
            return -1

        # Switch player
        self.current_player = 3 - self.current_player

        return 0

    def _ai_move(self) -> int:
        """
        AI logic: Win -> Block -> Random.
        """
        print(f"AI (Player {self.ai_player}) is thinking...")

        # Strategy 1: Try to win
        move = self._find_winning_move(self.ai_player)
        if move:
            print(f"AI plays at ({move[0]}, {move[1]})")
            return self._make_move(move[0], move[1])

        # Strategy 2: Block opponent from winning
        opponent = 3 - self.ai_player
        move = self._find_winning_move(opponent)
        if move:
            print(f"AI blocks at ({move[0]}, {move[1]})")
            return self._make_move(move[0], move[1])

        # Strategy 3: Random move
        move = self._get_random_empty_cell()
        if move:
            print(f"AI plays at ({move[0]}, {move[1]})")
            return self._make_move(move[0], move[1])

        return 0

    def _find_winning_move(self, player: int) -> Optional[Tuple[int, int]]:
        """
        Look for a move that wins immediately for 'player'.
        """
        for i in range(self.rows):
            for j in range(self.cols):
                if self.board[i][j] == 0:  # Empty cell
                    # Try this move
                    self.board[i][j] = player
                    wins = self._check_win(i, j, player)
                    self.board[i][j] = 0  # Undo

                    if wins:
                        return (i, j)

        return None

    def _get_random_empty_cell(self) -> Optional[Tuple[int, int]]:
        """
        Pick any empty spot.
        """
        empty_cells = []
        for i in range(self.rows):
            for j in range(self.cols):
                if self.board[i][j] == 0:
                    empty_cells.append((i, j))

        return random.choice(empty_cells) if empty_cells else None

    def _is_board_full(self) -> bool:
        """Check if board is full."""
        for row in self.board:
            if 0 in row:
                return False
        return True

    def _print_board(self):
        """Print the board."""
        symbols = {0: '   ', 1: ' X ', 2: ' O '}
        print("\nBoard:")
        for row in self.board:
            print('|' + '|'.join(symbols[cell] for cell in row) + '|')
        print()

    def _check_win(self, row: int, col: int, player: Optional[int] = None) -> bool:
        """
        Check if 'player' won after a move at (row, col).
        """
        if player is None:
            player = self.current_player

        # Check all 4 directions
        directions = [
            (0, 1),   # Horizontal
            (1, 0),   # Vertical
            (1, 1),   # Main diagonal
            (1, -1)   # Anti-diagonal
        ]

        for dr, dc in directions:
            count = 1  # Count the current position

            # Count in positive direction
            count += self._count_consecutive(row, col, dr, dc, player)

            # Count in negative direction
            count += self._count_consecutive(row, col, -dr, -dc, player)

            if count >= self.k:
                return True

        return False

    def _count_consecutive(self, row: int, col: int, dr: int, dc: int, player: int) -> int:
        """
        Count consecutive marks in one direction.
        """
        count = 0
        r, c = row + dr, col + dc

        while 0 <= r < self.rows and 0 <= c < self.cols and self.board[r][c] == player:
            count += 1
            r += dr
            c += dc

        return count

# Example usage
if __name__ == "__main__":
    print("=== Game with AI ===")
    game = TicTacToeWithAI(3, 3, 3, isAI=True)

    # Human player makes moves, AI responds automatically
    game.move(0, 0)  # Human (Player 1)
    # AI automatically responds

    game.move(0, 1)  # Human (Player 1)
    # AI automatically responds

    game.move(0, 2)  # Human (Player 1) tries to win
    # Game ends

Example Output

=== Game with AI ===

Board:
| X |   |   |
|   |   |   |
|   |   |   |

AI (Player 2) is thinking...
AI plays at (1, 1)

Board:
| X |   |   |
|   | O |   |
|   |   |   |

Board:
| X | X |   |
|   | O |   |
|   |   |   |

AI (Player 2) is thinking...
AI blocks at (0, 2)

Board:
| X | X | O |
|   | O |   |
|   |   |   |

Performance Overview

Basic Game
- Time: O(M × N) maximum. Each move takes O(max(M, N)).
- Space: O(M × N) to hold the grid.
With AI
- Time: The AI is slower. It might take O(M × N × K) because it checks every empty spot to see if it's a winning move.
- Space: Same as above, O(M × N).

Special Cases

Full board (Draw): Return -1 or print "Draw" correctly.
Small games: If K=2 and the board is 2x2, the game ends very fast.
Impossible K: If K is larger than the board rows or columns, no one can win.
Non-square boards: If M and N are different sizes, diagonals might be shorter.
AI trapped: If the AI has no moves, handle the draw logic carefully.

Important Takeaways

Evaluation Points

The Basics:
- Did you set up the board correctly?
- Do players switch turns correctly?
- Do you check all 4 directions for a win?
Win Logic:
- You must check from the last move.
- Count marks going "forward" and "backward" from that spot.
- Common mistake: Only looking one way (like only looking right, but forgetting left).
Code Style:
- Keep logic separate (one function for moves, one for checking wins).
- Use clear names for variables.

Common Errors

Bad Win Check: Not checking the negative direction (e.g., checking up but not down).
Counting Errors: Forgetting to include the piece you just placed in the count.
Board Data: Storing strings like "X" and "O" is okay, but numbers (1, 2) are often easier to manage.
AI Loops: If the board is full, the AI might loop forever if you don't check for a draw first.

Discussion Topics

Detecting Draws Early: Can we tell it's a draw before the board is full?
- Yes, but it is hard to code. You would need to check if enough empty spots exist in a line to make K. For a simple interview, checking for a full board is enough.
Large Boards: How to handle a 1000x1000 board?
- Don't use a 2D array. Use a HashMap to store only the moves made.
- When checking for a win, only look at spots near the last move.
Smarter AI:
- Use the Minimax algorithm. It looks ahead at future turns to find the perfect move.

Description

Problem Statement

Requirements

Board Setup:

Main Functions:

Rules:

Usage Example

Input Limits

Solution Details

How It Works

Time Performance

Space Usage

Code Implementation

Extension: Adding an AI

New Requirements

Update Constructor:

AI Logic:

Update move():

Draws:

AI Logic

Code Implementation

Example Output

Performance Overview

Special Cases

Important Takeaways

Evaluation Points

Common Errors

Discussion Topics

Update `move()`: