← Jane Street Interview Insights

Jane Street·Machine Learning Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say
May 2026

Summary

Jane Street ML engineer round, basically a coding problem dressed up as a game design question. More algorithmic than I expected for an ML role, but I guess that tracks for Jane Street.

Questions Asked (1)

Q1

Design and implement a Connect-N game on an infinite board where pieces drop into columns under gravity. Implement an insert function and a check for N-in-a-row across all four directions after each move.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs
Author's notes

The infinite board part is what tripped me up first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the rules: infinite board, gravity, Connect-N, and the insert function. Then design a data structure that efficiently tracks the board state and checks for N-in-a-row after each move, focusing on the four directions from the last placed piece. Discuss trade-offs between time and space, and consider optimizations like incremental checks and sparse representation.

Pro tip: Emphasize that you only need to check lines through the newly placed piece, not the entire board, and use a hash map to represent the board sparsely for infinite width. This shows you understand the problem's constraints and can optimize for real-time performance.

1. Clarify requirements and constraints

Confirm the rules: infinite board, gravity, N-in-a-row wins, and that insert returns the position. Discuss assumptions about input validity and performance expectations.

2. Choose data structures

Represent the board as a hash map mapping column indices to lists of pieces (or heights), since the board is infinite. Track the last move's coordinates for efficient win checking.

3. Implement insert

For a given column, find the next available row (e.g., by checking the column's height), place the piece, update the data structure, and return the position.

4. Check for N-in-a-row

From the last placed piece, check in all four directions (horizontal, vertical, two diagonals) by counting consecutive same-colored pieces in both directions. If any count reaches N, declare a win.

5. Analyze complexity and optimize

Discuss time complexity: O(1) amortized for insert and O(N) for win check (since only lines through the last piece are checked). Mention potential optimizations like maintaining counts or using bitboards for bounded boards.

Key Points to Mention

  • Sparse representation using hash map for infinite board
  • Gravity: pieces drop to the lowest available row in a column
  • Only need to check lines through the last placed piece for win condition
  • Four directions: horizontal, vertical, and two diagonals
  • Time complexity: O(1) insert, O(N) check per move
  • Trade-offs: memory vs. speed, and handling of infinite board

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.