Jane Street·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Apr 2026

Summary

Jane Street SWE interview with a Connect Four variant problem that had a twist I hadn't seen before. The design scope was pretty wide and they wanted complexity analysis, edge case handling, and actual code, all in one shot.

Questions Asked (1)

Design and implement a Connect Four variant where dropping a disc into a column pushes existing discs upward instead of stacking downward, with ejection when the column overflows. Support configurable board size, win detection in all directions, and full undo/redo functionality. Analyze time and space complexity and handle edge cases like invalid columns, ejected discs, turn alternation, and draw detection.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

The push-up mechanic threw me at first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a clean data model (e.g., a list of columns with discs stored bottom-to-top) and outline the core operations: drop, win check, undo/redo. Discuss trade-offs (time vs. space, simplicity vs. efficiency) and analyze complexity for each operation, covering edge cases and testing strategy.

Pro tip: Emphasize immutability and state snapshots for undo/redo to simplify correctness, and mention that you'd write unit tests for edge cases like full columns and simultaneous wins. This shows you prioritize maintainability and robustness, which Jane Street values.

1. Clarify Requirements and Constraints

Ask about board dimensions, win condition (e.g., 4 in a row), whether ejected discs can be reinserted, and undo/redo depth. Confirm that the variant pushes discs upward and ejects from the top.

2. Design Data Structures and Operations

Propose representing the board as a list of columns (each a list of discs bottom-to-top) or a 2D array with a height pointer per column. Define drop, win detection, undo, and redo operations.

3. Implement Core Logic and Edge Cases

Detail the drop algorithm: insert at bottom, shift discs up, eject if overflow. Implement win detection by checking all directions from the last move. Handle invalid columns, turn alternation, and draw detection.

4. Analyze Complexity and Trade-offs

Compute time and space complexity for each operation (e.g., drop O(column height), win check O(1) with incremental checks). Discuss trade-offs between different undo/redo strategies (command pattern vs. snapshots).

5. Test and Validate

Outline a testing plan covering edge cases: full column, ejection, win on last move, undo/redo sequences, and draw. Mention unit tests and property-based testing for confidence.

Key Points to Mention

Data structure choice: list of columns vs. 2D array with height pointers, and implications for shifting and ejection.
Win detection: check only around the last move in all 8 directions (horizontal, vertical, two diagonals) for O(1) time.
Undo/redo: use command pattern (store moves) or state snapshots; discuss memory vs. speed trade-offs.
Edge cases: invalid column index, column full (ejection), turn alternation, draw when board full and no winner.
Complexity analysis: drop O(H) due to shifting, win check O(1) incremental, undo/redo O(1) with command pattern.
Testing strategy: unit tests for each operation, property-based tests for invariants (e.g., disc count consistency).

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