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

Senior

May 2026

Summary

Jane Street ML Engineer interview with a coding problem that looks like a toy game but has real algorithmic teeth. The unbounded board constraint is what makes it interesting and also where I think most people slip up if they're not careful about complexity.

Questions Asked (1)

Implement a variant of Connect Four on an unbounded board (columns indexed by any integer, infinite vertical capacity). Support an insert(col, player) operation that drops a piece and returns true if the move creates N consecutive pieces in a row or column for that player. Each insert must run in O(N) time, not scan the whole board.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

The 'unbounded in both directions' part is the real constraint.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the rules (N, win condition, board bounds) and then design a data structure that tracks, for each cell, the lengths of consecutive runs in all relevant directions. For each insert, update only the affected runs in O(N) time by checking neighboring cells and combining their run lengths.

Pro tip: Mention that you would precompute or maintain run lengths for all four directions (horizontal, vertical, and both diagonals) and that the vertical direction is trivial because pieces stack, so you only need to check the new piece's row and column neighbors. Also, discuss how to handle the unbounded board efficiently using a hash map keyed by (row, col).

1. Clarify requirements and constraints

Ask about N (fixed or variable), whether the board is truly infinite in all directions or just columns, and if multiple players can win simultaneously. Confirm that insert must be O(N) and not O(board size).

2. Choose data structures

Use a hash map to represent the sparse board, mapping (row, col) to player. Additionally, maintain for each cell the lengths of consecutive runs in the four directions (horizontal, vertical, diagonal /, diagonal \).

3. Design the insert operation

For a given column, find the lowest empty row (by checking the hash map or maintaining a column height map). Place the piece, then for each direction, compute the run length by combining the run lengths of the two neighboring cells in that direction (if they belong to the same player) plus 1. Update the run length for the new cell and for the endpoints of the combined runs.

4. Check for win condition

After updating run lengths, if any run length >= N, return true. Otherwise, return false. Ensure that updates are O(1) per direction, so total O(N) is satisfied (since N is constant, O(1) is O(N)).

5. Analyze complexity and edge cases

Explain that each insert touches O(1) cells (the new cell and its neighbors) and updates O(1) run lengths per direction, so O(N) time is trivially satisfied. Discuss edge cases: multiple pieces in a column, winning with more than N pieces, and memory usage for unbounded board.

Key Points to Mention

Use a hash map to represent the sparse board and avoid allocating an infinite grid.
Maintain run lengths for each cell in four directions to enable O(1) updates per direction.
For vertical direction, the run length is simply the height of the column, which can be tracked separately.
When updating run lengths, only the new cell and the endpoints of the merged runs need to be updated.
The win condition is checked by comparing the updated run length to N.
Time complexity per insert is O(1) (or O(N) if N is considered variable), and space complexity is O(number of pieces).

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