Snake Game
The Nokia classic as an engine: a deque for the body, a set for “did I bite myself?”.
the brief
What you are building
Remember Snake on the old Nokia phones? You will build its game engine — no graphics, just the rules.
The board is a grid. The snake starts in the top-left corner, one cell long. Food appears one piece at a time.
Each call moves the snake one cell. Eat food and you grow. Hit a wall or your own body, and the game is over.
must have
Requirements
- The board has
heightrows andwidthcolumns. The snake starts at row 0, column 0, with length 1. The score starts at 0. foodlists the pieces in order. Only the next piece is on the board; after it is eaten, the following one appears.movetakesU,D,LorRand moves the head one cell.- If the new head is off the board, the game is over.
- If the new head is on the current food, the snake grows: the tail stays where it is, and the score goes up by 1. Otherwise the tail moves forward first (it leaves its cell).
- Then, if the new head is on the snake's body, the game is over. (So moving into the cell the tail just left is fine.)
movereturns the score, or-1if this move ends the game. Every move after that also returns-1.
the contract
The Java API: class SnakeGame
This is close to LeetCode 353 (Design Snake Game, Premium); the move order above is the exact rule our judge uses.
public SnakeGame(int width, int height, int[][] food)food[i] = {row, col}.public int move(String direction)- Returns the score after the move, or
-1once the game is over.
- 1 ≤ width, height ≤ 10,000 (so
row * width + colfits in anint) - 0 ≤ food.length ≤ 5,000
- up to 10,000 moves
example session
Calls in, answers out
A board 4 wide and 3 high. Food at (0,2), then (1,2), then (1,1).
| call | returns | why |
|---|---|---|
new SnakeGame(4, 3, new int[][] {{0, 2}, {1, 2}, {1, 1}}) | — | |
move("R") | 0 | head at (0,1); no food here, so the tail follows |
move("R") | 1 | eats at (0,2); length 2 |
move("D") | 2 | eats at (1,2); length 3 |
move("L") | 3 | eats at (1,1); length 4 |
move("U") | 3 | into (0,1), the cell the tail just left: allowed |
move("D") | -1 | back into (1,1), which is still body: it bit itself |
move("L") | -1 | the game is already over |
time plan
Your 90 minutes
- 10 minclarify — Where does the snake start? Can it move into its tail's cell? What happens after game over? Write the move order down.
- 10 mindesign — The body changes at both ends: a deque. Is this cell body? must be fast: a set. Decide how to store a cell.
- 35 mincore code —
movein four steps: new head, wall check, eat-or-move-tail, body check. Run the example. - 25 minedge cases — 1×1 board, every wall, turning back on a length-2 and a length-3 snake, food under the tail, moves after game over.
- 10 minpolish — Name the steps. Be ready to add obstacles, or several snakes.
Practise under real pressure: a 90-minute clock with the phases above. It keeps running if you reload the page.
your turn
Build it here
Write the whole class in the editor. Run replays the example session; Submit adds the hidden tests (edge cases and large random sessions). Stuck for 20 minutes? Open one hint at a time.
Build SnakeGame in the browser
Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
The reference, the data-structure reasoning and the rubric are hidden so you can build it first. Even a half-working attempt teaches you more than reading a perfect answer.
Opening all three hints also shows it.
reference
One clean way to build it
A deque and a set that always hold the same cells. The order of the four steps in move is the whole game.
class SnakeGame { private final int width, height; private final int[][] food; private final ArrayDeque<Integer> body = new ArrayDeque<>(); // head at the front, tail at the back private final Set<Integer> cells = new HashSet<>(); // the same cells, for O(1) "am I biting myself?" private int eaten = 0; // also the index of the next piece of food private boolean over = false; public SnakeGame(int width, int height, int[][] food) { this.width = width; this.height = height; this.food = food; body.addFirst(0); // the snake starts at row 0, column 0 cells.add(0); } /** One number per cell: row * width + col. Cheaper than an int[] and works in a HashSet. */ private int cell(int row, int col) { return row * width + col; } public int move(String direction) { if (over) return -1; int head = body.peekFirst(); int row = head / width, col = head % width; switch (direction) { case "U": row--; break; case "D": row++; break; case "L": col--; break; case "R": col++; break; default: throw new IllegalArgumentException("unknown direction: " + direction); } if (row < 0 || row >= height || col < 0 || col >= width) return gameOver(); // hit a wall int next = cell(row, col); boolean eats = eaten < food.length && food[eaten][0] == row && food[eaten][1] == col; if (eats) eaten++; // grow: the tail stays where it is else cells.remove(body.pollLast()); // the tail moves first, so the head may take its cell if (cells.contains(next)) return gameOver(); // bit itself body.addFirst(next); cells.add(next); return eaten; } private int gameOver() { over = true; return -1; }}the choices
Which data structures, and why
ArrayDeque<Integer>The body in order, head at the front. Adding a head and dropping a tail are both O(1).
O(1) per move. A List with remove(0) would shift every cell: O(length).
HashSet<Integer>The same cells, for "did I bite myself?". The deque alone would need a scan of the whole body.
O(1) average per check, instead of O(length).
int cell = row * width + colOne number per cell: works as a set key with no equals/hashCode to write.
No extra objects; row = cell / width, col = cell % width.
self-check
Mark yourself like the interviewer would
Tick only what your code really does. Nothing is saved or sent — this is just for you.
your honest self-score: 0 / 100
traps
Common mistakes
- Checking "did I bite myself?" before removing the tail. Then the snake dies when it simply follows its own tail.
- Mixing up rows and columns, or
widthandheight. Say it out loud: row goes with height, column goes with width. - Scanning a
Listof body cells on every move. It works on a 4×3 board and times out on a long snake. - Removing the tail from the deque but forgetting the set (or the other way round). Keep both updates next to each other.
- Letting the game continue after game over.
what they ask next
Follow-ups and extensions
Add walls (obstacles) inside the board.
Pass a set of blocked cells to the constructor. The wall check becomes: off the board, or in the blocked set. Still O(1).
Food can now appear anywhere at random. How do you pick a free cell fast?
Picking random cells until one is free gets slow when the snake fills the board. Keep the free cells in an array plus a map cell → index (like LeetCode 380, Insert Delete GetRandom O(1)): random pick, add and remove are all O(1).
Two snakes on the same board.
Make a Snake class (its own deque) and keep one shared map cell → which snake.
A head that lands on any snake's cell ends that snake's game.
How would you test this without a UI?
Exactly like our judge: a script of moves and the expected list of returns. Small boards make every edge case easy to draw on paper.
revise