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.