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 Hebbia.

What role is this question designed for?

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

Implement Ultimate Tic-Tac-Toe | Hebbia Coding Question

Implement Ultimate Tic-Tac-Toe

Company: Hebbia

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design and implement a playable Tic-Tac-Toe system in two parts. ## Part 1: Standard Tic-Tac-Toe Implement a `TicTacToe` class for a standard 3x3 board. Required methods: - `make_move(row, col, player) -> bool` - Places the current player's mark at the given `row` and `col`. - `player` is either `'X'` or `'O'`. - Return `true` if the move is valid and successfully placed. - Return `false` if the move is invalid, such as an out-of-bounds position, an occupied cell, or an invalid player. - `check_winner()` - Checks whether the current board has a winner. - A player wins by occupying an entire row, column, or diagonal. - Return the winning player, or return `null`/`None` if there is no winner yet. - `display()` - Prints or returns a readable representation of the current board. ## Part 2: Ultimate Tic-Tac-Toe Implement Ultimate Tic-Tac-Toe. The game consists of a 3x3 grid of smaller boards. Each smaller board is itself a standard 3x3 Tic-Tac-Toe board. Rules: 1. A move is represented by: - Which small board the player chooses, identified by its big-board coordinates `(board_row, board_col)`. - Which cell inside that small board the player chooses, identified by `(cell_row, cell_col)`. 2. The relative cell position of the previous move determines where the next player must play. - For example, if a player places a mark at `(cell_row = 2, cell_col = 0)` inside any small board, then the next player must play in the small board located at `(board_row = 2, board_col = 0)`. 3. If the required next small board is already full or already won, then the next player may choose any small board that is not full and has not already been won. 4. When a player wins a small board, that small board is considered captured by that player. 5. The winner of the overall game is the player who captures three small boards in a row, column, or diagonal on the large 3x3 board. Design appropriate classes and methods to support legal move validation, move placement, small-board winner detection, large-board winner detection, and board display.

Quick Answer: This question evaluates object-oriented design, state management, rule validation, and algorithmic reasoning for both standard and Ultimate Tic-Tac-Toe, testing competencies in data structures, winner-detection logic, and hierarchical game modeling.

Part 1: Standard Tic-Tac-Toe Move Simulator

Simulate a standard 3x3 Tic-Tac-Toe board from a list of attempted moves. Each move is a string 'row,col,player'. Apply valid moves in order and ignore invalid ones. A move is invalid if the coordinates are out of bounds, the player is not 'X' or 'O', the target cell is occupied, or a winner has already been determined. Do not enforce alternating turns. Return per-move validity, the final winner, and a readable final board.

Constraints

0 <= len(moves) <= 100000
Board size is always 3x3
Malformed move strings must be treated as invalid
Do not enforce alternating turns; validate only against board state and the rules above

Examples

Input: []

Expected Output: ['', 'None', '...', '...', '...']

Explanation: Edge case: no moves, so the board stays empty and there is no winner.

Input: ['0,0,X']

Expected Output: ['1', 'None', 'X..', '...', '...']

Explanation: A single valid move places X in the top-left corner.

Input: ['0,0,X', '1,0,O', '0,1,X', '1,1,O', '0,2,X', '2,2,O']

Expected Output: ['111110', 'X', 'XXX', 'OO.', '...']

Explanation: X wins on the top row after the fifth move, so the sixth move is rejected.

Input: ['0,0,X', '0,0,O', '3,1,X', '1,1,Z', '1,1,O']

Expected Output: ['10001', 'None', 'X..', '.O.', '...']

Explanation: This includes an occupied cell, an out-of-bounds move, and an invalid player symbol.

Hints

Use a 3x3 array of characters initialized with '.'.
After each successful move, checking all 8 winning lines is still constant time.

Part 2: Ultimate Tic-Tac-Toe Move Simulator

Simulate Ultimate Tic-Tac-Toe from a list of attempted moves. The game consists of a 3x3 grid of small 3x3 Tic-Tac-Toe boards. Each move is a string 'board_row,board_col,cell_row,cell_col,player'. Apply valid moves only. The cell position of the previous valid move determines the small board where the next move must be played. If that required small board is already won or full, the next move may be played on any still-playable small board. A small board becomes captured and unplayable once won. The overall winner is the player who captures three small boards in a row, column, or diagonal. Do not enforce alternating turns.

Constraints

0 <= len(moves) <= 100000
There are always exactly 9 small boards, each of size 3x3
A move is invalid if it targets an out-of-bounds location, a non-playable small board, an occupied cell, an invalid player symbol, or the wrong forced board when one exists
Once a small board is won, it is captured and cannot be played again
Do not enforce alternating turns; validate only according to the game state and the rules above

Examples

Input: []

Expected Output: ['', 'None', '*', '.........', '.........', '.........', '.........', '.........', '.........', '.........', '.........', '.........']

Explanation: Edge case: an empty game has no winner, any playable board may be chosen next, and the 9x9 display is blank.

Input: ['0,0,1,2,X']

Expected Output: ['1', 'None', '1,2', '.........', '..X......', '.........', '.........', '.........', '.........', '.........', '.........', '.........']

Explanation: A single move in small board (0,0) at cell (1,2) forces the next player to small board (1,2).

Input: ['0,0,1,1,X', '0,0,0,0,O', '1,1,0,0,O']

Expected Output: ['101', 'None', '0,0', '.........', '.X.......', '.........', '...O.....', '.........', '.........', '.........', '.........', '.........']

Explanation: After the first valid move, the next move must be played in small board (1,1). The second move is rejected because it ignores that requirement. The third move is valid.

Input: ['1,1,0,0,X', '0,0,0,0,X', '0,0,0,1,X', '0,1,0,0,X', '0,0,0,2,X', '0,2,0,0,O']

Expected Output: ['111111', 'None', '*', 'XXXX..O..', '.........', '.........', '...X.....', '.........', '.........', '.........', '.........', '.........']

Explanation: The first five moves capture small board (0,0) for X. The last move sends the next player to (0,0), but that board is already won, so the next move may be made on any playable small board.

Input: ['1,1,0,0,X', '0,0,0,0,X', '0,0,0,1,X', '0,1,0,0,X', '0,0,0,2,X', '0,2,0,0,X', '1,1,0,1,X', '0,1,0,1,X', '0,1,0,2,X', '0,2,0,1,X', '1,2,0,2,X', '0,2,0,2,X']

Expected Output: ['111111111111', 'X', 'None', 'XXXXXXXXX', '.........', '.........', '...XX...X', '.........', '.........', '.........', '.........', '.........']

Explanation: X captures the three small boards across the top row of the large board, so X wins the overall game.

Hints

Track two layers of state: the 9 small boards themselves and a separate 3x3 grid that stores which small boards have been captured.
Keep a 'forced board' coordinate from the previous valid move. Only ignore it when that target small board is already full or captured.

Quick Overview

This question evaluates object-oriented design, state management, rule validation, and algorithmic reasoning for both standard and Ultimate Tic-Tac-Toe, testing competencies in data structures, winner-detection logic, and hierarchical game modeling.