Coding · Design a structure
Design Snake Game
- Reported in several places
- Medium
- SDE-2 (P40)
- 2 sources
Two or more independent public pages, at least one a candidate write-up.
Solve it in the playground, with tests
Simulate the classic snake game on a board with a given width and height. The snake starts as one cell at the top-left corner, and a list of food cells, as [row, column], appears one at a time in the given order. Each move is U, D, L or R, and after a move you return the score, which is the number of foods eaten, or -1 once the game is over because the head left the board or hit the snake's own body. On a 3 wide, 2 high board with food [[1,2],[0,1]], the moves R, D, R, U, L, U return 0, 0, 1, 1, 2, -1. Each move should cost constant time.
Restated in our own words, not a quote from Atlassian or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: does the snake grow by one cell for each food? Does only the next food appear on the board, in list order? What happens when the head moves into the cell the tail is leaving this tick? What should further moves return after the game is over? Can the move list be very long, so that per-move cost matters? Is the food ever placed on the snake?
I would assume growth by one per food, one food visible at a time, the tail moving away before the collision check unless the snake is eating, the game staying over (-1) after the first loss, and food never placed on the body.
Brute force
Say the obvious answer and why it is too slow.
Keep the snake as a plain array of cells. Each move appends the new head, and if no food was eaten removes the tail from the front. To test for a collision, scan the whole array for the new head.
That scan is O(length) per move, and removing from the front of an array can also cost O(length) in the worst case, so q moves with a snake of length n cost O(q · n). With a long snake and a hundred thousand moves that is about 10^10 operations. The scan is the part to eliminate, since all we ask is whether one cell is occupied.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n) per move
- Time
- O(1) per move
- Space
- O(n + f)
This is a design and simulation problem whose answer is a deque plus a set. The deque holds the snake in order from tail to head, so growing at the head and shrinking at the tail are both O(1). The set holds the same cells, so "is this cell occupied?" is O(1) on average. The two always describe the same cells, and that invariant is the whole design.
One move works like this. Compute the new head. If it is outside the board, the game is over. Otherwise check whether it equals the next food. If it does, the snake grows: keep the tail, add one to the score, and advance to the next food. If it does not, the tail leaves: remove it from the deque and the set. Only now test whether the new head is in the set, and if so the game is over. Otherwise add the head to both structures.
The order matters. Removing the tail before the collision test is what makes it legal to step into the cell the tail just left, because that cell is empty by the time the head arrives.
In my code a single Map plays both roles: it links every body cell to the next cell towards the head, and I keep a head cell and a tail cell. The Map keys are the set, and following the links from the tail gives the deque order. I encode a cell as row * width + column. Out loud: "tail leaves first unless we eat, then check the set."
Walk it through
A dry run on the example, step by step.
| move | new head | food? | body, tail to head | result |
|---|---|---|---|---|
| start | (0,0) | next is (1,2) | (0,0) | - |
| R | (0,1) | no | (0,1) | 0 |
| D | (1,1) | no | (1,1) | 0 |
| R | (1,2) | yes, grow | (1,1) (1,2) | 1 |
| U | (0,2) | no | (1,2) (0,2) | 1 |
| L | (0,1) | yes, grow | (1,2) (0,2) (0,1) | 2 |
| U | (-1,1) | wall | game over | -1 |
On the 3 wide, 2 high board with food [[1,2],[0,1]], the snake starts at (0,0). R moves to (0,1): not food, the tail leaves, score 0. D moves to (1,1): score 0. R moves to (1,2), which is the first food, so the tail stays and the score is 1; the snake now covers (1,1) and (1,2).
U moves to (0,2) and the tail leaves: score 1. L moves to (0,1), the second food: the snake grows and the score is 2. The last U would go to row -1, which is off the board, so the function returns -1. The trace shows the body from tail to head after each move.
The code
Runnable JavaScript, checked against test cases.
class SnakeGame {
constructor(width, height, food) {
Object.assign(this, { width, height, food, foodIndex: 0, score: 0, over: false, head: 0, tail: 0 });
this.towardHead = new Map([[0, -1]]);
}
move(direction) {
if (this.over) return -1;
const [dr, dc] = { U: [-1, 0], D: [1, 0], L: [0, -1], R: [0, 1] }[direction];
const row = Math.floor(this.head / this.width) + dr;
const col = (this.head % this.width) + dc;
if (row < 0 || row >= this.height || col < 0 || col >= this.width) return this.end();
const cell = row * this.width + col;
const next = this.food[this.foodIndex];
if (next && next[0] === row && next[1] === col) {
this.foodIndex++;
this.score++;
} else {
const vacated = this.tail;
this.tail = this.towardHead.get(vacated);
this.towardHead.delete(vacated);
}
if (this.towardHead.has(cell)) return this.end();
if (this.towardHead.size === 0) this.tail = cell;
else this.towardHead.set(this.head, cell);
this.towardHead.set(cell, -1);
this.head = cell;
return this.score;
}
end() {
this.over = true;
return -1;
}
}
function run(ops, args) {
let game = null;
return ops.map((op, i) => {
if (op === "SnakeGame") {
game = new SnakeGame(args[i][0], args[i][1], args[i][2]);
return null;
}
return game.move(args[i][0]);
});
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
- Wall hit: row or column outside the board returns -1 and marks the game over.
- Chasing the tail: a snake filling a 2 by 2 board can step into the cell its tail is vacating, because the tail is removed first when no food is eaten.
- Food under the snake: assumed never to happen. If it did, the eating branch keeps the tail, so the step would count as a collision.
- Length 1: the tail and head are the same cell; removing the tail empties the structure and the new head becomes both ends.
- After game over: a flag makes every later move return -1 without touching the state.
- No food left: the next food is undefined, so no move eats and the snake keeps its length.
Follow-ups to expect
Where the interviewer pushes next.
- How would you place food at random on a free cell without ever choosing a cell under the snake?
- What changes if the board wraps around at the edges?
- How would you add a second snake, or let the player change speed?
- How would you keep memory bounded for millions of moves on a huge board?
Where candidates slip
The mistakes this problem punishes.
Where candidates go wrong:
- Checking collision before removing the tail, so a snake that follows its own tail dies by mistake.
- Removing the tail on a move that eats food, so the snake never grows.
- Scanning an array for collisions, which turns each move into O(length).
- Forgetting to advance the food pointer after eating.
- Mixing up [row, column] with [x, y], or encoding cells as row * height + column.
- Not making game over permanent, so a later move returns a score again.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.