Quick Overview

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 Connect Four with win detection

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

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( 1) 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).

Quick Answer: 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 generalized Connect Four game engine for an m x n board with a win condition of k in a row. For the standard game, use m = 6, n = 7, and k = 4. Process a list of operations against a single game instance: - ("move", column, player): Drop a disc for player 1 or 2 into the given column. The disc falls to the lowest available cell. - Return -1 if the move is invalid. - Return 0 if the move is valid and no player wins. - Return 1 or 2 if that player wins on this move. - ("isDraw",): Return True if the board is completely full and no player has won; otherwise return False. - ("reset",): Clear the board and return None. - ("undo",): Remove the most recent successful move and return True. If there is no successful move to undo, return False. A move is invalid if: - the column is out of range, - the column is already full, - the player is not 1 or 2, - or the game has already ended in a win or draw and has not been reset or undone. Your solution should avoid rescanning the entire board after each move. Only lines passing through the newly placed disc can create a new win.

Constraints

  • 1 <= m, n <= 200
  • 1 <= k <= max(m, n)
  • 0 <= len(operations) <= 10^5
  • Players are identified by integers 1 and 2

Examples

Input: (6, 7, 4, [("move", 0, 1), ("move", 1, 2), ("move", 0, 1), ("move", 1, 2), ("move", 0, 1), ("move", 1, 2), ("move", 0, 1), ("isDraw",)])

Expected Output: [0, 0, 0, 0, 0, 0, 1, False]

Explanation: Player 1 stacks four discs in column 0 and wins vertically on the seventh operation. The board is not full, so isDraw returns False.

Input: (4, 4, 4, [("move", 0, 1), ("move", 1, 2), ("move", 1, 1), ("move", 2, 2), ("move", 2, 2), ("move", 2, 1), ("move", 3, 2), ("move", 3, 2), ("move", 3, 2), ("move", 3, 1), ("move", 0, 2), ("undo",), ("move", 0, 2)])

Expected Output: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, True, 0]

Explanation: Player 1 forms a diagonal from bottom-left to top-right on move 10. A later move is invalid because the game is already over. Undo removes the winning move, and the final move becomes legal again.

Hints

  1. Keep an array of the next free row for each column so a move does not need to search downward.
  2. After placing a disc, only four directions through that cell matter: horizontal, vertical, diagonal down-right, and diagonal down-left.

Loading coding console...