Implement Connect Four with win detection
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
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.
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.
Input: (2, 2, 2, [("move", -1, 1), ("move", 2, 1), ("move", 0, 1), ("move", 0, 2), ("move", 0, 1), ("reset",), ("move", 1, 2), ("isDraw",)])
Expected Output: [-1, -1, 0, 0, -1, None, 0, False]
Explanation: Columns -1 and 2 are out of range. After two valid moves, column 0 becomes full, so another move there is invalid. Reset clears the board, and the new move succeeds.
Input: (2, 2, 3, [("move", 0, 1), ("move", 0, 2), ("move", 1, 1), ("move", 1, 2), ("isDraw",), ("undo",), ("isDraw",)])
Expected Output: [0, 0, 0, 0, True, True, False]
Explanation: With k = 3 on a 2 x 2 board, no one can win. After four moves the board is full, so it is a draw. Undo removes the last move, so it is no longer a draw.
Input: (1, 4, 4, [("move", 0, 1), ("move", 1, 1), ("move", 2, 1), ("move", 3, 1), ("move", 0, 2)])
Expected Output: [0, 0, 0, 1, -1]
Explanation: On a single-row board, player 1 makes four in a row horizontally. Any later move is invalid because the game has already ended.
Solution
def solution(m, n, k, operations):
class ConnectFour:
def __init__(self, rows, cols, target):
self.m = rows
self.n = cols
self.k = target
self.reset()
def reset(self):
self.board = [[0] * self.n for _ in range(self.m)]
self.next_row = [self.m - 1] * self.n
self.filled = 0
self.winner = 0
self.game_over = False
self.history = []
def _count_one_side(self, row, col, dr, dc, player):
count = 0
r, c = row + dr, col + dc
steps = 0
while (
steps < self.k - 1
and 0 <= r < self.m
and 0 <= c < self.n
and self.board[r][c] == player
):
count += 1
r += dr
c += dc
steps += 1
return count
def _is_winning_move(self, row, col, player):
if self.k == 1:
return True
directions = [(0, 1), (1, 0), (1, 1), (1, -1)]
for dr, dc in directions:
total = 1
total += self._count_one_side(row, col, dr, dc, player)
total += self._count_one_side(row, col, -dr, -dc, player)
if total >= self.k:
return True
return False
def move(self, column, player):
if player not in (1, 2):
return -1
if self.game_over:
return -1
if not (0 <= column < self.n):
return -1
if self.next_row[column] < 0:
return -1
row = self.next_row[column]
self.board[row][column] = player
self.next_row[column] -= 1
self.filled += 1
self.history.append((row, column, player))
if self._is_winning_move(row, column, player):
self.winner = player
self.game_over = True
return player
if self.filled == self.m * self.n:
self.game_over = True
return 0
def isDraw(self):
return self.filled == self.m * self.n and self.winner == 0
def undo(self):
if not self.history:
return False
row, column, _player = self.history.pop()
self.board[row][column] = 0
self.next_row[column] += 1
self.filled -= 1
self.winner = 0
self.game_over = False
return True
game = ConnectFour(m, n, k)
results = []
for op in operations:
kind = op[0]
if kind == "move":
results.append(game.move(op[1], op[2]))
elif kind == "isDraw":
results.append(game.isDraw())
elif kind == "reset":
game.reset()
results.append(None)
elif kind == "undo":
results.append(game.undo())
else:
raise ValueError(f"Unknown operation: {kind}")
return resultsTime complexity: move: O(k) (O(1) for the standard game where k = 4), isDraw: O(1), undo: O(1), reset: O(mn). Space complexity: O(mn).
Hints
- Keep an array of the next free row for each column so a move does not need to search downward.
- After placing a disc, only four directions through that cell matter: horizontal, vertical, diagonal down-right, and diagonal down-left.