Implement Connect Four Winner Detection
Company: Virtu
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a Connect Four-style game engine.
The board has 6 rows and 7 columns. Two players alternate turns. On each turn, the current player chooses a column. Because of gravity, the player's token falls to the lowest empty cell in that column. A move is invalid if the chosen column is already full.
After each valid move, determine whether the current player has won. A player wins if they have four of their own tokens consecutively in any of the following directions:
- Horizontal
- Vertical
- Diagonal from bottom-left to top-right
- Diagonal from top-left to bottom-right
Design and implement the core logic for placing a token and checking whether the latest move creates a win.
Follow-up questions:
1. How would you support more than two players?
2. How would you optimize the solution if the board were very large?
Quick Answer: This question evaluates the ability to design and implement game-state logic for a Connect Four-style board, covering board data structures, coordinate and boundary handling, gravity-based token placement, and efficient pattern detection for consecutive tokens in the Coding & Algorithms domain.
Drop tokens into a 6x7 Connect Four board and return the 1-based move number that first wins, 0 for no winner, or -1 for invalid move.
Constraints
- Players alternate starting with player 1
Examples
Input: ([0, 0, 1, 1, 2, 2, 3],)
Expected Output: 7
Explanation: Player 1 wins horizontally on move 7.
Input: ([0, 1, 0, 1, 0, 1, 0],)
Expected Output: 7
Explanation: Player 1 wins vertically.
Hints
- Only lines through the latest placed token need checking.