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

What role is this question designed for?

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

Design and implement Connect Four engine

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design and implement a Connect Four game engine. Use a default 6x7 board and two players. Provide an API with: drop(col, player) returning the row placed or an error; getStatus() returning inProgress, win with winning player, or draw; and reset(). Enforce gravity so a disc occupies the lowest empty cell in the selected column. After each valid move, check for a win of four in a row horizontally, vertically, and on both diagonals, based only on the last move. Handle invalid inputs (out-of-range column, full column, wrong player turn). Optimize win detection to avoid scanning the entire board (aim for O(k) around the last move). Generalize to an MxN board with a configurable connect length k. Discuss data structures (e.g., 2D array vs. bitboards), time/space complexity, and include unit tests covering edge cases.

Quick Answer: This question evaluates a candidate's competency in algorithmic problem solving, data structure selection, API design, complexity analysis, and testing through implementation of a Connect Four game engine.

Implement a generalized Connect Four engine. Your function receives `rows`, `cols`, `k`, and a list of operations. Each operation is one of: `('drop', col, player)`, `('status',)`, or `('reset',)`. Players are `1` and `2`, and player `1` always starts on a fresh board and after every reset. Use 0-based indexing for columns and returned rows, with row `0` at the top and row `rows - 1` at the bottom. A valid drop must obey gravity, so the disc lands in the lowest empty cell of the chosen column, and the operation returns that row index. Invalid drops must return one of: `'error:out_of_range'`, `'error:column_full'`, `'error:wrong_turn'`, or `'error:game_over'`. Invalid operations must not change the board or turn. `('status',)` returns `'inProgress'`, `'draw'`, or `('win', player)`. `('reset',)` clears the board and returns `'OK'`. After each valid drop, detect a win by checking only lines that pass through the last placed disc, rather than scanning the whole board. A 2D grid plus a per-column next-empty-row array is sufficient; bitboards are an optional low-level optimization. The classic game is `rows=6`, `cols=7`, `k=4`.

Constraints

1 <= rows, cols <= 200
1 <= k <= max(rows, cols)
1 <= len(operations) <= 100000
Operations are well-formed tuples using only 'drop', 'status', and 'reset'
Players are 1 and 2, and player 1 starts after creation and after every reset

Examples

Input: (6, 7, 4, [('drop', 0, 1), ('drop', 0, 2), ('drop', 1, 1), ('drop', 1, 2), ('drop', 2, 1), ('drop', 2, 2), ('status',), ('drop', 3, 1), ('status',), ('drop', 4, 2)])

Expected Output: [5, 4, 5, 4, 5, 4, 'inProgress', 5, ('win', 1), 'error:game_over']

Explanation: Player 1 completes a horizontal connect-4 on the bottom row after dropping in column 3. After that, the game is over, so further drops are rejected.

Input: (4, 4, 3, [('drop', -1, 1), ('drop', 0, 2), ('drop', 0, 1), ('drop', 0, 2), ('drop', 0, 1), ('drop', 0, 2), ('drop', 0, 1), ('status',), ('reset',), ('status',)])

Expected Output: ['error:out_of_range', 'error:wrong_turn', 3, 2, 1, 0, 'error:column_full', 'inProgress', 'OK', 'inProgress']

Explanation: The first move uses an invalid column, the second uses the wrong player, and the final drop into column 0 fails because the column is full. Reset clears the board and restores the initial state.

Input: (6, 7, 4, [('drop', 0, 1), ('drop', 1, 2), ('drop', 1, 1), ('drop', 2, 2), ('drop', 2, 1), ('drop', 3, 2), ('drop', 6, 1), ('drop', 3, 2), ('drop', 5, 1), ('drop', 5, 2), ('drop', 2, 1), ('drop', 3, 2), ('drop', 3, 1), ('status',)])

Expected Output: [5, 5, 4, 5, 4, 5, 5, 4, 5, 4, 3, 3, 2, ('win', 1)]

Explanation: Player 1 builds a bottom-left to top-right diagonal using supporting discs underneath. The last move at row 2, column 3 completes the diagonal connect-4.

Input: (2, 2, 3, [('drop', 0, 1), ('drop', 1, 2), ('drop', 0, 1), ('drop', 1, 2), ('status',)])

Expected Output: [1, 1, 0, 0, 'draw']

Explanation: On a 2x2 board with k=3, no player can ever connect 3. Once the board fills up, the game is a draw.

Input: (3, 3, 1, [('drop', 2, 1), ('status',)])

Expected Output: [2, ('win', 1)]

Explanation: When k=1, the first valid disc immediately satisfies the win condition.

Hints

Use a 2D board plus an array `next_row[col]` so each drop is O(1) before win checking.
To detect a win in O(k), count matching discs in both directions for each of the 4 line types: horizontal, vertical, main diagonal, and anti-diagonal.

Quick Overview

This question evaluates a candidate's competency in algorithmic problem solving, data structure selection, API design, complexity analysis, and testing through implementation of a Connect Four game engine.