Quick Overview

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.

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

  1. Only lines through the latest placed token need checking.

Loading coding console...