Design and implement Connect Four engine
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
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.
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.
Input: (6, 7, 4, [('drop', 0, 1), ('drop', 1, 2), ('drop', 1, 1), ('drop', 2, 2), ('drop', 2, 1), ('drop', 3, 2), ('drop', 6, 1), ('drop', 3, 2), ('drop', 5, 1), ('drop', 5, 2), ('drop', 2, 1), ('drop', 3, 2), ('drop', 3, 1), ('status',)])
Expected Output: [5, 5, 4, 5, 4, 5, 5, 4, 5, 4, 3, 3, 2, ('win', 1)]
Explanation: Player 1 builds a bottom-left to top-right diagonal using supporting discs underneath. The last move at row 2, column 3 completes the diagonal connect-4.
Input: (2, 2, 3, [('drop', 0, 1), ('drop', 1, 2), ('drop', 0, 1), ('drop', 1, 2), ('status',)])
Expected Output: [1, 1, 0, 0, 'draw']
Explanation: On a 2x2 board with k=3, no player can ever connect 3. Once the board fills up, the game is a draw.
Input: (3, 3, 1, [('drop', 2, 1), ('status',)])
Expected Output: [2, ('win', 1)]
Explanation: When k=1, the first valid disc immediately satisfies the win condition.
Solution
def solution(rows, cols, k, operations):
board = [[0] * cols for _ in range(rows)]
next_row = [rows - 1] * cols
current_turn = 1
status = 'inProgress'
moves = 0
results = []
def reset_state():
return [[0] * cols for _ in range(rows)], [rows - 1] * cols, 1, 'inProgress', 0
def check_win(r, c, player):
directions = ((0, 1), (1, 0), (1, 1), (1, -1))
for dr, dc in directions:
count = 1
step = 1
while step < k:
nr = r + dr * step
nc = c + dc * step
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == player:
count += 1
step += 1
else:
break
step = 1
while step < k:
nr = r - dr * step
nc = c - dc * step
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == player:
count += 1
step += 1
else:
break
if count >= k:
return True
return False
for op in operations:
kind = op[0]
if kind == 'drop':
_, col, player = op
if status != 'inProgress':
results.append('error:game_over')
continue
if not (0 <= col < cols):
results.append('error:out_of_range')
continue
if player != current_turn:
results.append('error:wrong_turn')
continue
row = next_row[col]
if row < 0:
results.append('error:column_full')
continue
board[row][col] = player
next_row[col] -= 1
moves += 1
if check_win(row, col, player):
status = ('win', player)
elif moves == rows * cols:
status = 'draw'
else:
current_turn = 2 if player == 1 else 1
results.append(row)
elif kind == 'status':
results.append(status)
elif kind == 'reset':
board, next_row, current_turn, status, moves = reset_state()
results.append('OK')
else:
results.append('error:invalid_operation')
return resultsTime complexity: O(1) per valid drop before win checking, O(k) win checking per valid drop, O(1) per status, and O(rows * cols) per reset. Space complexity: O(rows * cols).
Hints
- Use a 2D board plus an array `next_row[col]` so each drop is O(1) before win checking.
- 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.