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

What role is this question designed for?

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

Design a Tic-Tac-Toe Engine | Decagon Coding Question

Design a Tic-Tac-Toe Engine

Company: Decagon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement an `n x n` Tic-Tac-Toe game engine for two players. Support a method `move(row, col, player)` that records a move and returns whether that move causes the player to win. Discuss two versions: 1. A straightforward implementation that stores the full board and checks rows, columns, and diagonals after each move. 2. An optimized implementation that avoids storing the entire board and updates the winner status in constant time per move. Assume all moves are valid and no move is made after the game has already been won.

Quick Answer: This question evaluates algorithm design and data structure competency, emphasizing state representation, time-space trade-offs, and techniques for achieving constant-time updates in a two-player n×n Tic-Tac-Toe engine.

Part 1: Straightforward Tic-Tac-Toe Engine with Full Board

Implement a straightforward n x n Tic-Tac-Toe engine for two players. You are given a sequence of valid moves. For each move, place the player's mark on a full board, then determine whether that move causes that player to win by checking the affected row, affected column, and applicable diagonals. Return the win result after every move. Assume all moves are valid, no cell is played twice, players are represented by 1 and 2, and no moves occur after a winning move.

Constraints

1 <= n <= 500
0 <= len(moves) <= n * n
Each move is a triple (row, col, player)
0 <= row, col < n
player is either 1 or 2
All moves are valid: no duplicate cell is played
No move is made after a player has already won

Examples

Input: (3, [])

Expected Output: []

Explanation: No moves are made, so there are no win results.

Input: (1, [(0, 0, 2)])

Expected Output: [True]

Explanation: On a 1 x 1 board, the first move immediately completes a row, column, and diagonal.

Input: (3, [(0, 0, 1), (1, 0, 2), (0, 1, 1), (1, 1, 2), (0, 2, 1)])

Expected Output: [False, False, False, False, True]

Explanation: Player 1 wins on the final move by filling row 0.

Input: (3, [(0, 2, 1), (0, 0, 2), (1, 1, 1), (1, 0, 2), (2, 0, 1)])

Expected Output: [False, False, False, False, True]

Explanation: Player 1 wins on the final move by filling the anti-diagonal.

Input: (4, [(0, 1, 2), (0, 0, 1), (1, 1, 2), (1, 0, 1), (2, 1, 2), (2, 0, 1), (3, 1, 2)])

Expected Output: [False, False, False, False, False, False, True]

Explanation: Player 2 wins on the final move by filling column 1.

Hints

After placing a move, only that move's row, column, and possibly diagonals can have changed.
You can scan a row or column to see if every cell equals the current player.

Part 2: Optimized Tic-Tac-Toe Engine with Constant-Time Moves

Implement an optimized n x n Tic-Tac-Toe engine for two players. You are given a sequence of valid moves. For each move, determine whether that move causes the current player to win, but do not store the full n x n board. Instead, maintain enough state so that each move can be processed in O(1) time. Assume all moves are valid, no cell is played twice, players are represented by 1 and 2, and no moves occur after a winning move.

Constraints

1 <= n <= 100000
0 <= len(moves) <= min(n * n, 200000)
Each move is a triple (row, col, player)
0 <= row, col < n
player is either 1 or 2
All moves are valid: no duplicate cell is played
No move is made after a player has already won
The solution should not allocate an n x n board

Examples

Input: (5, [])

Expected Output: []

Explanation: No moves are made, so there are no win results.

Input: (1, [(0, 0, 1)])

Expected Output: [True]

Explanation: On a 1 x 1 board, the first move immediately wins.

Input: (2, [(0, 0, 1), (0, 1, 2), (1, 1, 1)])

Expected Output: [False, False, True]

Explanation: Player 1 wins on the final move by completing the main diagonal.

Input: (4, [(0, 0, 1), (0, 1, 2), (1, 1, 1), (0, 2, 2), (2, 2, 1), (1, 2, 2), (3, 3, 1)])

Expected Output: [False, False, False, False, False, False, True]

Explanation: Player 1 wins on the final move by filling the main diagonal of a 4 x 4 board.

Input: (5, [(0, 4, 2), (0, 0, 1), (1, 4, 2), (1, 0, 1), (2, 4, 2), (2, 0, 1), (3, 4, 2), (3, 0, 1), (4, 4, 2)])

Expected Output: [False, False, False, False, False, False, False, False, True]

Explanation: Player 2 wins on the final move by filling column 4.

Hints

A player wins when one row, column, or diagonal contains exactly n of that player's marks.
Try representing player 1 as +1 and player 2 as -1. Then a line is won when its absolute counter value reaches n.

Quick Overview

This question evaluates algorithm design and data structure competency, emphasizing state representation, time-space trade-offs, and techniques for achieving constant-time updates in a two-player n×n Tic-Tac-Toe engine.