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 Take-home Project rounds at Airbnb.

What role is this question designed for?

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

Implement Connect Four with win detection

Quick Overview

This question evaluates a candidate's ability to design efficient data structures and algorithms for real-time game state management, including win detection, API design, time/space complexity analysis, and handling edge cases such as full or out-of-range columns.

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

Implement a Connect Four game engine. Support a general m×n board (default 6× 7) and a win condition of k in a row (default 4). Provide an API: ConnectFour(m, n, k), move(column, player)->status where status returns 0 (no win), 1 or 2 (player wins), -1 (invalid move), and a separate method isDraw(). Discs fall to the lowest available cell in the chosen column. After each move, detect wins horizontally, vertically, and both diagonals. Design data structures to achieve O( 1) or near O( 1) time per move for win checking, and analyze time/space complexity. Extend the design to support reset() and optional undo() efficiently, and discuss how you would test edge cases (full columns, out-of-range columns, early wins).

Quick Answer: This question evaluates a candidate's ability to design efficient data structures and algorithms for real-time game state management, including win detection, API design, time/space complexity analysis, and handling edge cases such as full or out-of-range columns.

Implement a generalized Connect Four game engine for an m x n board with a win condition of k in a row. For the standard game, use m = 6, n = 7, and k = 4. Process a list of operations against a single game instance: - ("move", column, player): Drop a disc for player 1 or 2 into the given column. The disc falls to the lowest available cell. - Return -1 if the move is invalid. - Return 0 if the move is valid and no player wins. - Return 1 or 2 if that player wins on this move. - ("isDraw",): Return True if the board is completely full and no player has won; otherwise return False. - ("reset",): Clear the board and return None. - ("undo",): Remove the most recent successful move and return True. If there is no successful move to undo, return False. A move is invalid if: - the column is out of range, - the column is already full, - the player is not 1 or 2, - or the game has already ended in a win or draw and has not been reset or undone. Your solution should avoid rescanning the entire board after each move. Only lines passing through the newly placed disc can create a new win.

Constraints

1 <= m, n <= 200
1 <= k <= max(m, n)
0 <= len(operations) <= 10^5
Players are identified by integers 1 and 2

Examples

Input: (6, 7, 4, [("move", 0, 1), ("move", 1, 2), ("move", 0, 1), ("move", 1, 2), ("move", 0, 1), ("move", 1, 2), ("move", 0, 1), ("isDraw",)])

Expected Output: [0, 0, 0, 0, 0, 0, 1, False]

Explanation: Player 1 stacks four discs in column 0 and wins vertically on the seventh operation. The board is not full, so isDraw returns False.

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

Expected Output: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, True, 0]

Explanation: Player 1 forms a diagonal from bottom-left to top-right on move 10. A later move is invalid because the game is already over. Undo removes the winning move, and the final move becomes legal again.

Input: (2, 2, 2, [("move", -1, 1), ("move", 2, 1), ("move", 0, 1), ("move", 0, 2), ("move", 0, 1), ("reset",), ("move", 1, 2), ("isDraw",)])

Expected Output: [-1, -1, 0, 0, -1, None, 0, False]

Explanation: Columns -1 and 2 are out of range. After two valid moves, column 0 becomes full, so another move there is invalid. Reset clears the board, and the new move succeeds.

Input: (2, 2, 3, [("move", 0, 1), ("move", 0, 2), ("move", 1, 1), ("move", 1, 2), ("isDraw",), ("undo",), ("isDraw",)])

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

Explanation: With k = 3 on a 2 x 2 board, no one can win. After four moves the board is full, so it is a draw. Undo removes the last move, so it is no longer a draw.

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

Expected Output: [0, 0, 0, 1, -1]

Explanation: On a single-row board, player 1 makes four in a row horizontally. Any later move is invalid because the game has already ended.

Hints

Keep an array of the next free row for each column so a move does not need to search downward.
After placing a disc, only four directions through that cell matter: horizontal, vertical, diagonal down-right, and diagonal down-left.

Quick Overview