Jane Street·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate

Jun 2026

Summary

Jane Street SWE interview with a snake game BFS problem. Small grid, deceptively tricky state representation once you account for the snake's body changing as it moves.

Questions Asked (1)

Given a snake on an R x C grid with a known body configuration, find the minimum number of moves for the snake's head to reach an apple. The snake grows when it eats the apple, and a move into the current tail cell is legal on non-eating moves since the tail vacates simultaneously. Return -1 if unreachable.

Algorithms & Data Structures

Author's notes

My first instinct was plain BFS on just the head position, which is completely wrong once the snake is longer than one cell.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a shortest path search in a state space where each state is the snake's full body configuration (or head position plus body orientation). Use BFS to explore moves level by level, tracking visited states to avoid cycles. Handle the tail-vacating rule by checking if the next head cell is the current tail and the snake is not eating; if so, the move is legal and the tail cell becomes free.

Pro tip: Emphasize that the state space can be reduced by noting that the snake's body is a path, so you can represent it as a deque of cells; also mention that BFS is optimal because each move has uniform cost, and pruning symmetric states can improve performance.

1. Define the state representation

Represent the snake as an ordered list of cells (head first) or a deque. The state includes the entire body because the snake's shape affects future moves.

2. Identify valid moves and transitions

From each state, generate up to four moves (up, down, left, right). A move is valid if the new head cell is within bounds and not occupied by the body, except possibly the tail if the snake is not eating (tail vacates).

3. Apply BFS for shortest path

Use a queue to perform BFS from the initial state. Track visited states (e.g., as a hash set of serialized body configurations) to avoid revisiting. The first time the head reaches the apple, return the depth.

4. Handle growth and tail vacating

When the head moves to the apple, the snake grows: the tail does not move. Otherwise, the tail moves forward (the last cell is removed). Ensure the tail-vacating rule is correctly applied for non-eating moves.

5. Return -1 if unreachable

If BFS exhausts all reachable states without finding the apple, return -1.

Key Points to Mention

State space includes the entire snake body, not just the head position.
BFS guarantees the minimum number of moves because each move has unit cost.
The tail-vacating rule: moving into the current tail cell is allowed only if the snake is not eating (i.e., the tail will move away).
When the snake eats the apple, it grows, so the tail does not move and the body length increases by one.
Visited states must be tracked to avoid infinite loops; serialization of the body configuration is needed.
Time complexity is O(R*C*4^L) in the worst case, but pruning and efficient state encoding can help.

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