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.

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.

Hints

  1. Use a 2D board plus an array `next_row[col]` so each drop is O(1) before win checking.
  2. 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.

Loading coding console...