The coding question
Build a snake game with a nextMove(direction) function. Keep track of the board, the snake and the food. The snake only grows after it's eaten n pieces of food, and the game ends if it hits a wall or itself.
Ask a few questions first
| Ask | What we'll assume |
|---|---|
| Board size and where does the snake start? | A height by width grid. The snake starts as one cell in the top left, (0, 0). |
| Where does food come from? | A list of positions given up front. Only the first one is on the board, and the next appears once it's eaten. I'll pick that so tests are predictable. |
| What does 'grows after n pieces' mean exactly? | Every nth piece eaten makes the snake one cell longer. With n = 2, the 2nd, 4th and 6th pieces grow it. |
| What should nextMove return? | The score, meaning pieces eaten so far, or -1 once the game is over. Moves after that also return -1. |
| Can the head move into the cell the tail is leaving? | Yes, unless the snake is growing this turn, because then the tail stays put. |
| What's being judged? | Mostly how it's split up and how easy it is to change. So I'll keep the board, snake and food as separate small classes. |
A couple of examples
| Input | Output |
|---|---|
| 3×3 board, food at (0,1), (0,2), (1,2), n = 2. Moves R, R, D, L | [1, 2, 3, 3], and the snake ends as [(1,1), (1,2)] |
| 5×5 board, food at (0,1) to (0,4), n = 1. Moves R, R, R, R, D, L, U, R | [1, 2, 3, 4, 4, 4, -1, -1]. The U runs into its own body |
| 2×3 board, food at (1,2), (0,1), n = 1. Moves R, D, R, U, L, L, L | [0, 0, 1, 1, 2, 2, -1]. The last L hits the wall |
Start with brute force
Keep the snake as a list of cells. Each move, compute the new head, check walls, then check whether the new head is anywhere in the list. Insert the head at the front, and pop the tail unless growing.
Cost: checking the list and inserting at the front are both O(length of the snake) per move. That's fine for small boards but gets slow for a long snake.
A better way
Two structures fix the speed. A deque, a list that's fast at both ends, holds the body in order, so adding a head and dropping a tail are O(1). A set holds the same cells, so 'did I hit myself?' is O(1). They're a hash map and a sliding window, more or less.
The design matters more than the speed in this round. Give each thing one job, which is object-oriented design at its simplest. The Board knows its size. The Snake knows its body and how to move. Food knows what's next. The Game holds the rules, like when to grow and when it's over. Then a change like 'grow every nth piece' touches one line in one place.
Watch the order. Decide whether this move grows the snake before checking for a collision, because a growing snake doesn't free up its tail cell.
- If the game is already over, return -1.
- Work out the next head cell from the direction.
- Check if that cell has food, and if eating it makes this the nth piece, which means growing.
- If the cell is off the board, or in the body (ignoring the tail when not growing), end the game.
- Move the snake: add the head, and drop the tail unless growing.
- If food was eaten, take it off the food list and add one to the score. Return the score.
The code
from collections import deque
MOVES = {"U": (-1, 0), "D": (1, 0), "L": (0, -1), "R": (0, 1)}
class Board:
def __init__(self, height, width):
self.height = height
self.width = width
def inside(self, cell):
row, col = cell
return 0 <= row < self.height and 0 <= col < self.width
class Snake:
def __init__(self, start):
self.body = deque([start]) # head is body[0]
self.cells = {start}
def head(self):
return self.body[0]
def next_head(self, direction):
row, col = self.head()
d_row, d_col = MOVES[direction]
return (row + d_row, col + d_col)
def hits_itself(self, cell, growing):
# When not growing, the tail moves out of the way this turn.
if not growing and cell == self.body[-1]:
return False
return cell in self.cells
def move(self, cell, growing):
if not growing:
self.cells.discard(self.body.pop())
self.body.appendleft(cell)
self.cells.add(cell)
class Food:
def __init__(self, positions):
self.positions = deque(positions)
def current(self):
return self.positions[0] if self.positions else None
def eat(self):
self.positions.popleft()
class SnakeGame:
def __init__(self, height, width, food, grow_every=1):
self.board = Board(height, width)
self.snake = Snake((0, 0))
self.food = Food(food)
self.grow_every = grow_every
self.eaten = 0
self.over = False
def next_move(self, direction):
"""Returns the score (food eaten so far), or -1 once the game is over."""
if self.over:
return -1
if direction not in MOVES:
raise ValueError("unknown direction: " + direction)
cell = self.snake.next_head(direction)
eats = cell == self.food.current()
growing = eats and (self.eaten + 1) % self.grow_every == 0
if not self.board.inside(cell) or self.snake.hits_itself(cell, growing):
self.over = True
return -1
self.snake.move(cell, growing)
if eats:
self.food.eat()
self.eaten += 1
return self.eaten| Cost | Why | |
|---|---|---|
| Time per move | O(1) | Deque ends and set lookups are constant time |
| Space | O(s + f) | The snake's s cells, stored twice, plus f food positions |
Test it
Walk through one of the examples out loud, then check the cases that tend to break things:
- Moving off the board on the very first move: return -1 and stay over.
- Chasing your own tail in a loop: allowed, because the tail leaves the cell this turn.
- Moving into the tail on a turn you grow: that's a crash, because the tail stays.
- n = 1: grows on every piece, which is the classic game.
- Running out of food: the game keeps going, the score just stops rising.
- A bad direction like 'X': raise an error rather than guessing.
Common mistakes
- Checking for a self hit before deciding whether the snake grows. Then the tail rule is wrong one way or the other.
- Using only a list for the body, so every move costs O(length).
- Forgetting to remove the tail from the set when it moves, so the snake crashes into a cell it already left.
- Putting every rule inside one giant nextMove. It works, but it's what this round marks you down for.
- Not stopping after game over, so later moves keep changing the state.
Follow-up questions
How would you add random food that never lands on the snake?
Give Food a method that picks a random empty cell, asking the Snake which cells are taken. For a crowded board, keep a set of free cells so you don't retry forever.
How would you add a wrap-around mode, where walls teleport you?
Put it in the Board: add a method that maps an outside cell back inside with modulo. The Game asks the Board for the real cell instead of checking inside(). Nothing else changes.
How would you test this?
Unit test each class alone, like Snake.move with and without growing. Then test the game with fixed food and scripted moves, like the examples above.
How the time adds up
| Minutes | What you're doing |
|---|---|
| 0–5 | Ask about the board, food, growing and what nextMove returns |
| 5–10 | Sketch the classes and the simple list version |
| 10–20 | Pick a deque and a set, and settle the order of checks |
| 20–35 | Write the code |
| 35–40 | Test growing, walls, and hitting itself |
| 40–45 | Follow-up questions |
Key concepts used here
- Object-oriented designSplit a small program into classes that are easy to change.
- Hash maps and sliding windowsSwap nested loops for a single pass.
We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Atlassian.