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 easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at OpenAI.

What role is this question designed for?

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

Simulate a Turn-Based Two-Player Game | OpenAI Coding Question

Quick Overview

This question evaluates API design, state management, move validation, board representation, and correctness guarantees for a turn-based game simulator. It falls under the Coding & Algorithms domain and is commonly asked to assess edge-case handling, time/space complexity awareness and practical application of algorithmic thinking and software design at the implementation level.

Simulate a Turn-Based Two-Player Game

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

Design and implement a simulator for a two-player turn-based board game similar to tic-tac-toe. Requirements: - The game is played on an `n x n` board. - Two players, `A` and `B`, take turns placing a mark on an empty cell. - A move is invalid if it is outside the board, targets an occupied cell, or is made after the game has already ended. - After each move, the program should report one of four states: `A wins`, `B wins`, `draw`, or `game continues`. - The interface should support both processing moves one at a time and evaluating a full sequence of moves to predict the final winner. Focus on clean API design, correctness, and reasonable time and space complexity.

Quick Answer: This question evaluates API design, state management, move validation, board representation, and correctness guarantees for a turn-based game simulator. It falls under the Coding & Algorithms domain and is commonly asked to assess edge-case handling, time/space complexity awareness and practical application of algorithmic thinking and software design at the implementation level.

Implement a simulator for a two-player turn-based board game played on an n x n grid. Each attempted move is given as a tuple (player, row, col), where player is either 'A' or 'B', and row/col are 0-indexed coordinates. Player A always starts, and turns must alternate between A and B. A move is valid only if: - it is that player's turn, - the coordinates are inside the board, - the target cell is empty, - and the game has not already ended. Invalid moves are ignored: they do not change the board, do not change the turn, and do not change the current game result. After every attempted move, record the current game state as exactly one of these strings: - 'A wins' - 'B wins' - 'draw' - 'game continues' Return a tuple (states, final_state): - states is a list where states[i] is the game state after the i-th attempted move, - final_state is the game state after all moves have been processed. This single API supports both use cases: - step-by-step processing through the states list, - full-sequence evaluation through final_state. A player wins by filling an entire row, column, main diagonal, or anti-diagonal with their own marks. If the board becomes full with no winner, the game is a draw.

Constraints

1 <= n <= 100000
0 <= len(moves) <= 200000
Each move is a tuple (player, row, col) where player is usually 'A' or 'B'; invalid values should be treated as invalid moves
row and col may be outside the board and should then be treated as an invalid move

Examples

Input: (3, [('A', 0, 0), ('B', 1, 0), ('A', 0, 1), ('B', 1, 1), ('A', 0, 2)])

Expected Output: (['game continues', 'game continues', 'game continues', 'game continues', 'A wins'], 'A wins')

Explanation: A fills the entire top row on the fifth move.

Input: (2, [('A', 0, 0), ('A', 1, 1), ('B', 1, 1), ('A', 0, 1)])

Expected Output: (['game continues', 'game continues', 'game continues', 'A wins'], 'A wins')

Explanation: The second move is invalid because it is A's turn only once. The invalid move is ignored, B then moves, and A wins on the last move.

Input: (3, [('A', 0, 0), ('B', 0, 1), ('A', 0, 2), ('B', 1, 1), ('A', 1, 0), ('B', 1, 2), ('A', 2, 1), ('B', 2, 0), ('A', 2, 2)])

Expected Output: (['game continues', 'game continues', 'game continues', 'game continues', 'game continues', 'game continues', 'game continues', 'game continues', 'draw'], 'draw')

Explanation: All 9 cells are filled without any player completing a row, column, or diagonal.

Input: (3, [('A', 0, 0), ('B', 1, 0), ('A', 0, 1), ('B', 1, 1), ('A', 0, 2), ('B', 2, 2), ('A', 2, 1)])

Expected Output: (['game continues', 'game continues', 'game continues', 'game continues', 'A wins', 'A wins', 'A wins'], 'A wins')

Explanation: A wins on move 5. All later moves are invalid because the game has already ended, so the reported state stays 'A wins'.

Input: (3, [])

Expected Output: ([], 'game continues')

Explanation: No moves were made, so the game has not ended.

Input: (1, [('A', 0, 0), ('B', 0, 0)])

Expected Output: (['A wins', 'A wins'], 'A wins')

Explanation: On a 1 x 1 board, A wins immediately with the first valid move. Any later move is ignored.

Input: (3, [('A', 0, 0), ('B', 0, 0), ('B', 3, 1), ('B', 1, 1)])

Expected Output: (['game continues', 'game continues', 'game continues', 'game continues'], 'game continues')

Explanation: The second move targets an occupied cell, the third is outside the board, and only the fourth attempted move is a valid move by B.

Hints

You do not need to scan the whole board after every move. Track counts for rows, columns, and the two diagonals.
Be careful with invalid moves: they should not change the board, should not advance the turn, and should not undo a finished game.

Quick Overview