Katkat
Back

Implement Connect Four with win detection

AirbnbSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This question evaluates a candidate's ability to design efficient data structures and algorithms for real-time game state management, including win detection, API design, time/space complexity analysis, and handling edge cases such as full or out-of-range columns.

Implement a Connect Four game engine. Support a general m×n board (default 6× 7) and a win condition of k in a row (default 4). Provide an API: ConnectFour(m, n, k), move(column, player)->status where status returns 0 (no win), 1 or 2 (player wins), -1 (invalid move), and a separate method isDraw(). Discs fall to the lowest available cell in the chosen column. After each move, detect wins horizontally, vertically, and both diagonals. Design data structures to achieve O(

  1. or near O(
  2. time per move for win checking, and analyze time/space complexity. Extend the design to support reset() and optional undo() efficiently, and discuss how you would test edge cases (full columns, out-of-range columns, early wins).