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