← Jane Street Interview Insights

Jane Street·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026

Summary

Jane Street SWE interview with a pretty involved coding problem about a modified connect-k game on an infinite grid. The twist is that dropping a piece pushes the whole column up, which makes win detection way trickier than it sounds.

Questions Asked (1)

Q1

Two players take turns dropping pieces into columns of an infinite integer grid. Each new piece lands at the bottom of its column and pushes all existing pieces in that column up by one row. Given a required run length k and a sequence of moves, find the first move after which any player has k consecutive pieces in a single row or column, and return which player(s) won. Diagonal lines don't count.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

The column-push mechanic is what got me.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints and assumptions, then propose an efficient algorithm using hash maps to track column heights and row occupancies. Explain how to detect k consecutive pieces in rows and columns after each move, and discuss trade-offs between time and space complexity.

Pro tip: Mention that you would first confirm whether the grid is truly infinite and if k is fixed, as this affects data structure choices. Also, note that early termination can save time by checking only affected rows and columns.

1. Clarify the problem

Ask clarifying questions about the grid size, k, and move sequence format. Confirm that pieces stack from the bottom and that only horizontal and vertical runs count.

2. Design data structures

Use a hash map to track the height of each column (next empty row) and another to track the pieces in each row. Since the grid is infinite, only store occupied cells.

3. Process moves and detect wins

For each move, place the piece, update column height and row occupancy. Check for k consecutive pieces in the affected row and column, and if found, record the winner and move index.

4. Analyze complexity and trade-offs

Discuss time complexity: O(1) per move for updates and O(k) for checking runs, leading to O(n*k) total. Space complexity: O(n) for storing occupied cells. Mention alternative approaches like union-find or segment trees if k is large.

5. Handle edge cases

Consider cases where k=1, multiple winners in the same move, or no winner. Ensure the algorithm correctly identifies the first move where any player wins.

Key Points to Mention

  • Use of hash maps to represent sparse infinite grid efficiently.
  • Column height tracking to determine landing row.
  • Row occupancy tracking to check horizontal runs.
  • Checking only the affected row and column after each move.
  • Time and space complexity analysis.
  • Handling multiple winners and early termination.

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