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.

Implement Connect Four game | Airbnb Coding Question

Implement Connect Four game

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

##### Question Design and implement the Connect Four game board, player moves, and winner-detection logic. Discuss time/space complexity and possible follow-ups such as AI opponent or scalable multiplayer service.

Quick Answer: This question evaluates implementation skills for game state management, move handling, and efficient winner-detection algorithms, testing competence in data structures, algorithmic complexity analysis, and correctness under edge cases.

Implement the core logic of a standard Connect Four game. The board has 6 rows and 7 columns. Players alternate turns, with Red ('R') moving first and Yellow ('Y') moving second. Each move is a column index, and the piece falls to the lowest available cell in that column. Process the moves in order and stop immediately if a player wins. A player wins if their newly placed piece creates 4 consecutive pieces horizontally, vertically, or diagonally. Return: - 'R' if Red wins - 'Y' if Yellow wins - 'Draw' if the board becomes full with no winner - 'Pending' if all moves are processed and no winner exists but the board is not full - 'Invalid' if a move uses a column outside 0 to 6, or tries to place a piece into a full column before the game has ended

Constraints

The board size is fixed at 6 rows by 7 columns.
0 <= len(moves) <= 100
A valid column index is an integer from 0 to 6.

Examples

Input: ([],)

Expected Output: 'Pending'

Explanation: No moves have been played, so nobody has won and the board is not full.

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

Expected Output: 'R'

Explanation: Red forms a horizontal line on the bottom row across columns 0, 1, 2, and 3.

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

Expected Output: 'Y'

Explanation: Yellow stacks 4 pieces vertically in column 1.

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

Expected Output: 'R'

Explanation: Red creates a diagonal from bottom-left to top-right.

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

Expected Output: 'Invalid'

Explanation: A Connect Four column holds only 6 pieces. The 7th move in the same column is invalid.

Solution

def solution(moves):
    ROWS, COLS = 6, 7
    board = [[None] * COLS for _ in range(ROWS)]
    next_row = [ROWS - 1] * COLS
    players = ("R", "Y")
    directions = ((1, 0), (0, 1), (1, 1), (1, -1))

    def count_in_direction(row, col, dr, dc, player):
        count = 0
        r, c = row + dr, col + dc
        while 0 <= r < ROWS and 0 <= c < COLS and board[r][c] == player:
            count += 1
            r += dr
            c += dc
        return count

    for turn, col in enumerate(moves):
        if not isinstance(col, int) or col < 0 or col >= COLS:
            return "Invalid"

        row = next_row[col]
        if row < 0:
            return "Invalid"

        player = players[turn % 2]
        board[row][col] = player
        next_row[col] -= 1

        for dr, dc in directions:
            line_length = 1
            line_length += count_in_direction(row, col, dr, dc, player)
            line_length += count_in_direction(row, col, -dr, -dc, player)
            if line_length >= 4:
                return player

    if all(r < 0 for r in next_row):
        return "Draw"

    return "Pending"

Time complexity: O(m), where m is the number of moves processed. Space complexity: O(1), because the board size is fixed at 6x7.

Hints

Keep track of the next open row in each column so you can place a piece in O(1) time.
After placing a piece, only check lines that pass through that new piece: horizontal, vertical, and the two diagonals.

Quick Overview

This question evaluates implementation skills for game state management, move handling, and efficient winner-detection algorithms, testing competence in data structures, algorithmic complexity analysis, and correctness under edge cases.