PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates proficiency in data structures, algorithm design, state management, and API design for game mechanics, focusing on board representation, move operations, win detection, and undo/redo functionality.

  • Medium
  • Jane Street
  • Coding & Algorithms
  • Software Engineer

Implement Connect Four with bottom push-up

Company: Jane Street

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

Implement a Connect Four variant where when a player inserts a disc into a column, the disc moves to the bottom cell of that column and pushes all existing discs in that column up by one. If the column is already full, the disc that is pushed above the top row is ejected and removed from the board. Design the board representation and APIs to: ( 1) initialize with R rows and C columns (default 6x 7), ( 2) drop a disc for a given player into a column, ( 3) detect a win (four in a row horizontally, vertically, or diagonally) after each move, and ( 4) support undo and redo of moves. Specify time and space complexities, data structures used, and how you handle edge cases such as ejected discs, invalid columns, alternating turns, and draw detection. Provide code for the core operations.

Quick Answer: This question evaluates proficiency in data structures, algorithm design, state management, and API design for game mechanics, focusing on board representation, move operations, win detection, and undo/redo functionality.

Part 1: Initialize a Bottom Push-Up Connect Four Board

Create the initial state for a Connect Four variant where discs are inserted at the bottom of a column and push existing discs upward. Use row index 0 as the bottom/insertion row, and row index R-1 as the top/ejection row. For this standalone problem, return a textual snapshot of the initialized board and bookkeeping. Passing rows=0 and cols=0 requests the default 6 x 7 board. If dimensions are invalid, return ['INVALID_DIMENSIONS']. Also report whether a connect-four line is geometrically possible on the board.

Constraints

  • 0 <= rows, cols <= 200
  • rows=0 and cols=0 means use the default 6 x 7 board
  • After default handling, rows and cols must both be positive
  • Internal row orientation must treat row 0 as the bottom insertion row

Examples

Input: (0, 0)

Expected Output: ['rows=6', 'cols=7', 'orientation=bottom_index_0_top_index_R-1', 'heights=0,0,0,0,0,0,0', 'filled=0', 'can_connect_four=true', '.......', '.......', '.......', '.......', '.......', '.......']

Explanation: The default 6 x 7 empty board is created.

Input: (3, 3)

Expected Output: ['rows=3', 'cols=3', 'orientation=bottom_index_0_top_index_R-1', 'heights=0,0,0', 'filled=0', 'can_connect_four=false', '...', '...', '...']

Explanation: A 3 x 3 board cannot contain four cells in any direction.

Input: (1, 4)

Expected Output: ['rows=1', 'cols=4', 'orientation=bottom_index_0_top_index_R-1', 'heights=0,0,0,0', 'filled=0', 'can_connect_four=true', '....']

Explanation: A horizontal connect-four is possible even with one row.

Input: (-1, 7)

Expected Output: ['INVALID_DIMENSIONS']

Explanation: Negative dimensions are rejected.

Hints

  1. Pick one row-index convention and use it consistently. Row 0 as the bottom makes bottom insertion easy to reason about.
  2. Store a height per column and a global filled count so later operations can answer fullness questions without scanning the whole grid.

Part 2: Drop a Disc with Bottom Push-Up Semantics

Simulate disc drops in the bottom push-up Connect Four variant. A valid drop inserts the player's disc into the bottom cell of the chosen column and shifts existing discs in that column upward by one row. If the column is full, the old top disc is ejected permanently. Player X always moves first, and valid moves must alternate X, O, X, O. Rejected moves must not mutate the board or advance the turn.

Constraints

  • 1 <= rows, cols <= 200
  • 0 <= len(moves) <= 1000
  • Players are represented by 'X' and 'O'
  • A rejected move performs no mutation and does not advance the turn
  • This part does not perform win detection; it only simulates drops

Examples

Input: (4, 3, ['X 1', 'O 1', 'X 1'])

Expected Output: ['OK:ejected=.', 'OK:ejected=.', 'OK:ejected=.', 'TURN:O', 'HEIGHTS:0,3,0', 'FILLED:3', '...', '.X.', '.O.', '.X.']

Explanation: All three discs are inserted at the bottom of column 1, pushing previous discs upward.

Input: (2, 1, ['X 0', 'O 0', 'X 0'])

Expected Output: ['OK:ejected=.', 'OK:ejected=.', 'OK:ejected=X', 'TURN:O', 'HEIGHTS:2', 'FILLED:2', 'O', 'X']

Explanation: The third drop is into a full column and ejects the old top X.

Input: (3, 3, ['X 3', 'X 0'])

Expected Output: ['INVALID_COLUMN', 'OK:ejected=.', 'TURN:O', 'HEIGHTS:1,0,0', 'FILLED:1', '...', '...', 'X..']

Explanation: Column 3 is out of range for a 3-column board, so the turn remains X.

Input: (3, 3, ['O 0', 'X 0'])

Expected Output: ['WRONG_TURN', 'OK:ejected=.', 'TURN:O', 'HEIGHTS:1,0,0', 'FILLED:1', '...', '...', 'X..']

Explanation: O cannot move first; the following X move is still accepted.

Input: (1, 1, [])

Expected Output: ['TURN:X', 'HEIGHTS:0', 'FILLED:0', '.']

Explanation: Edge case: no moves on a 1 x 1 board.

Hints

  1. Branch on whether heights[column] == rows. In the full case, save the top disc before shifting.
  2. A single drop only touches one column, so the shift cost is proportional to R, not R*C.

Part 3: Detect Wins After Bottom Push-Up Drops

Simulate bottom push-up drops and report winners after each valid move. A win is four equal discs horizontally, vertically, or diagonally. Unlike standard Connect Four, checking only around the newly inserted bottom cell is not sufficient because every disc in the affected column may move upward. For this problem, use a full-board scan after each valid move.

Constraints

  • 1 <= rows, cols <= 100
  • 0 <= len(moves) <= 1000
  • Players are 'X' and 'O'
  • A rejected move performs no mutation and does not advance the turn
  • A board with both rows < 4 and cols < 4 can never contain a connect-four line

Examples

Input: (4, 5, ['X 0', 'O 4', 'X 1', 'O 4', 'X 2', 'O 4', 'X 3'])

Expected Output: ['OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:X']

Explanation: X completes a horizontal bottom-row connect four.

Input: (4, 6, ['X 1', 'O 4', 'X 1', 'O 5', 'X 2', 'O 2', 'X 3', 'O 4', 'X 3', 'O 5', 'X 0', 'O 0'])

Expected Output: ['OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:X']

Explanation: The final O drop in column 0 pushes an X upward, creating an X horizontal win that is not through the newly placed O.

Input: (4, 3, ['X 0', 'O 1', 'X 0', 'O 1', 'X 0', 'O 2', 'X 0'])

Expected Output: ['OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:X']

Explanation: X forms a vertical four in column 0.

Input: (3, 3, ['O 0', 'X 3', 'X 0'])

Expected Output: ['WRONG_TURN', 'INVALID_COLUMN', 'OK:-']

Explanation: Rejected moves do not mutate state or advance the turn.

Input: (3, 3, [])

Expected Output: []

Explanation: Edge case: no moves means no statuses.

Hints

  1. The newly inserted disc is not the only changed cell; all occupied cells in the chosen column may shift upward.
  2. A full-board scan is simple and correct for the default board size. Larger boards can optimize by rechecking lines that pass through the changed column.

Part 4: Undo and Redo Bottom Push-Up Drops

Support drop, undo, and redo operations for the bottom push-up Connect Four variant. Each successful drop must be recorded as a command containing enough information to invert it exactly, including whether the column was full and which disc, if any, was ejected. Undo reverses the most recent successful drop. Redo reapplies the most recently undone drop. A new successful drop after an undo clears the redo history.

Constraints

  • 1 <= rows, cols <= 100
  • 0 <= len(operations) <= 1000
  • Players are 'X' and 'O', with X moving first
  • Rejected drops do not mutate state, advance turn, or clear redo history
  • A new successful drop after one or more undos clears the redo stack

Examples

Input: (3, 2, ['drop X 0', 'drop O 1', 'undo', 'redo'])

Expected Output: ['OK:ejected=.', 'OK:ejected=.', 'UNDO_OK', 'REDO_OK:ejected=.', 'TURN:X', 'HEIGHTS:1,1', 'FILLED:2', '..', '..', 'XO']

Explanation: Undo removes O from column 1; redo restores the same drop.

Input: (2, 1, ['drop X 0', 'drop O 0', 'drop X 0', 'undo'])

Expected Output: ['OK:ejected=.', 'OK:ejected=.', 'OK:ejected=X', 'UNDO_OK', 'TURN:X', 'HEIGHTS:2', 'FILLED:2', 'X', 'O']

Explanation: Undo of a full-column drop restores the ejected X to the top.

Input: (3, 2, ['drop X 0', 'drop O 1', 'undo', 'drop O 0', 'redo'])

Expected Output: ['OK:ejected=.', 'OK:ejected=.', 'UNDO_OK', 'OK:ejected=.', 'REDO_EMPTY', 'TURN:X', 'HEIGHTS:2,0', 'FILLED:2', '..', 'X.', 'O.']

Explanation: The new O drop after undo clears the redo stack, so redo is empty.

Input: (3, 3, ['drop O 0', 'drop X 3', 'undo', 'drop X 0'])

Expected Output: ['WRONG_TURN', 'INVALID_COLUMN', 'UNDO_EMPTY', 'OK:ejected=.', 'TURN:O', 'HEIGHTS:1,0,0', 'FILLED:1', '...', '...', 'X..']

Explanation: Invalid operations do not affect state; undo is empty until a successful drop occurs.

Input: (1, 1, [])

Expected Output: ['TURN:X', 'HEIGHTS:0', 'FILLED:0', '.']

Explanation: Edge case: no operations.

Hints

  1. Use two stacks: one for executed commands and one for undone commands.
  2. Undo has two branches: a full-column drop restores the ejected top disc, while a non-full drop clears the vacated top occupied slot and decreases the height.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Collapsible Code Editor: Brace Matching and Toggle - Jane Street (medium)
  • Implement a Circular Buffer - Jane Street (medium)
  • Optimize trade PnL table updates - Jane Street (hard)
  • Transform sparse time-code stream to dense rows - Jane Street (easy)
  • Sort trade executions into a canonical order - Jane Street (easy)