Design the Snake game

01The design, in the six-step framework

1. Requirements and use cases

This is LeetCode 353 and it has also been reported as a Google phone question: write Snake in a shared document and say which data structures you would use. The structures are the answer, so state them early. A deque holds the body in order; a set answers "am I hitting myself" in O(1).

• A game is created with a width, a height and a list of food positions served in order.
• A player moves the snake one cell up, down, left or right.
• Each move returns the score (food eaten), or −1 if the game ended.
• The snake grows by one when it eats; otherwise its tail moves forward.
• The game ends when the head leaves the board or runs into the body.

Out of scope: rendering, timers, speed levels. Constraints: move is O(1) regardless of snake length; memory is O(length) plus the food list, not O(width × height), since the board may be huge and sparse; the food source should be swappable for random placement.

2. Core entities and relationships

• Direction: an enum carrying its row and column change.
• Cell: an immutable (row, col) tuple.
• Snake: the deque of cells and the occupied set, kept in step; it knows how to advance and how to grow.
• FoodSource: an interface giving the next food cell; a list-backed version meets the LeetCode contract.
• SnakeGame: the board size, score and game-over flag; the only public entry point.

The game composes the snake, which has no meaning alone. The food source is aggregated and injected, because that is how tests hand in fixed food and production hands in random food.

3. Interfaces and key methods

from collections import deque
from enum import Enum
from typing import Optional, Protocol, Tuple

Cell = Tuple[int, int]

class Direction(Enum):
    UP = (-1, 0)
    DOWN = (1, 0)
    LEFT = (0, -1)
    RIGHT = (0, 1)

class FoodSource(Protocol):
    def peek(self) -> Optional[Cell]:
        """The current food cell, or None when no food is left."""
    def consume(self) -> None:
        """Advance to the next food."""

class Snake:
    def head(self) -> Cell:
        """The front of the body."""
    def hits_self(self, cell: Cell, grow: bool) -> bool:
        """Would moving the head to cell collide with the body after the tail moves."""
    def advance(self, cell: Cell, grow: bool) -> None:
        """Add a new head; drop the tail unless growing."""

class SnakeGame:
    def move(self, direction: Direction) -> int:
        """Advance one step; return the score, or -1 once the game is over."""

Invariants: occupied is exactly the set of cells in body; the body cells are distinct; the score equals the body length minus one; once over, every later move returns −1 and changes nothing.

4. Design patterns and the choices behind them

Deque plus set, kept together

The force: moving touches both ends of the body, and collision asks about membership. A deque gives O(1) push at the head and pop at the tail, and a set gives O(1) membership. A list alone would make collision O(length). Neither structure alone is enough, so Snake wraps them and offers one method that changes both, which is encapsulation protecting the invariant that the two agree. A 2-D boolean grid would also work but costs O(width × height) memory, which the sparse board rules out. See modeling boards and grids for the general choice.

The tail moves first

The subtle rule: moving into the cell the tail is about to vacate is legal, unless the snake is eating, in which case the tail stays. So the collision test depends on whether this step grows. hits_self takes that flag and answers correctly in one place. This is the bug the question is really testing, and it deserves a named test.

A narrow API and an injected food source

Returning the score or −1 is the contract the prompt gives, so move keeps it, as a matter of method design; game over is an expected outcome rather than an exception. FoodSource is a small seam, and that is the whole of what designing for unit tests needs here: a test passes a list and gets a deterministic game.

Why the score is not a separate source of truth

The score always equals the body length minus one, so a stored counter is redundant. It is kept because move reads it on every call and the name says what it means, but a test should assert the two agree. An invariant that can be checked in one line is worth checking, particularly in a phone screen where the interviewer is reading along and has no debugger to reach for.

5. Core flow and code

1. SnakeGame.move returns −1 at once if the game is over.
2. It computes the new head cell from the direction and checks the bounds.
3. It peeks at the food source; a match sets grow.
4. It asks Snake.hits_self(cell, grow); a hit ends the game.
5. Otherwise Snake.advance moves the body, and if growing the game adds a point and consumes the food.

import random

class ListFood:
    def __init__(self, cells: list) -> None:
        self.cells = [tuple(c) for c in cells]
        self.index = 0
    def peek(self) -> Optional[Cell]:
        return self.cells[self.index] if self.index < len(self.cells) else None
    def consume(self) -> None:
        self.index += 1

class RandomFood:
    """Places food on a free cell; rejection sampling is fine while the board is mostly empty."""
    def __init__(self, width: int, height: int, snake: "Snake", rng: random.Random) -> None:
        self.width, self.height, self.snake, self.rng = width, height, snake, rng
        self.current: Optional[Cell] = None
        self.consume()
    def peek(self) -> Optional[Cell]:
        return self.current
    def consume(self) -> None:
        self.current = None
        if len(self.snake.occupied) == self.width * self.height:
            return
        while self.current is None:
            cell = (self.rng.randrange(self.height), self.rng.randrange(self.width))
            if cell not in self.snake.occupied:
                self.current = cell

class Snake:
    def __init__(self, start: Cell = (0, 0)) -> None:
        self.body: deque = deque([start])     # left end is the head
        self.occupied: set = {start}

    def head(self) -> Cell:
        return self.body[0]

    def tail(self) -> Cell:
        return self.body[-1]

    def hits_self(self, cell: Cell, grow: bool) -> bool:
        if cell not in self.occupied:
            return False
        return grow or cell != self.tail()    # the tail cell is free only if the tail moves away

    def advance(self, cell: Cell, grow: bool) -> None:
        if not grow:
            self.occupied.discard(self.body.pop())
        self.body.appendleft(cell)
        self.occupied.add(cell)

class SnakeGame:
    def __init__(self, width: int, height: int, food: FoodSource, snake: Optional[Snake] = None) -> None:
        self.width, self.height = width, height
        self.food = food
        self.snake = snake or Snake()
        self.score = 0
        self.over = False

    def _on_board(self, cell: Cell) -> bool:
        return 0 <= cell[0] < self.height and 0 <= cell[1] < self.width

    def move(self, direction: Direction) -> int:
        if self.over:
            return -1
        row, col = self.snake.head()
        cell = (row + direction.value[0], col + direction.value[1])
        if not self._on_board(cell):
            self.over = True
            return -1
        grow = self.food.peek() == cell
        if self.snake.hits_self(cell, grow):
            self.over = True
            return -1
        self.snake.advance(cell, grow)
        if grow:
            self.score += 1
            self.food.consume()
        return self.score

if __name__ == "__main__":
    game = SnakeGame(3, 2, ListFood([(1, 2), (0, 1)]))
    moves = [Direction.RIGHT, Direction.DOWN, Direction.RIGHT, Direction.UP, Direction.LEFT, Direction.UP]
    assert [game.move(d) for d in moves] == [0, 0, 1, 1, 2, -1]

That final assert is LeetCode's own sample: score 2 after six moves, with the last step leaving the board.

6. Extensions, concurrency and what interviewers probe

• "Why not a list?" Pop from the front and membership are both O(length). A deque plus set makes each step O(1), and that is the sentence the interviewer wants.
• "Reversing into yourself." A length-two snake moving straight back onto its neck collides, and hits_self handles it because the neck is not the tail. Longer snakes behave the same. Some versions ignore a reverse key; that is one extra check on the last direction, in SnakeGame.move.
• "Random food." RandomFood slots in with no change to the game. When the board is nearly full, rejection sampling degrades, so keep a list of free cells instead.
• "Wrap-around walls." Replace the bounds check with modular arithmetic inside move; the body logic is unaffected.
• Concurrency: a game loop is one thread. If input arrives on another thread, it writes the latest direction to a queue that the loop reads once per tick; the snake is never touched from two threads.
• Common mistake: removing the tail after the collision check is not considered at all, so a snake following its own tail is wrongly killed; or eating food and also popping the tail, so it never grows.

02Where this question was reported

• LeetCode Discuss · LeetCode 353 (Medium), Google-tagged (freq 19.7)
• Codemia · Codemia Medium
• GeeksforGeeks · 'Develop the game Snake' in a shared Doc and say which data structures you'd use
• Taro · Taro lists Google among askers; SnakeGame(width,height,food).move(dir) returning score/-1