Low-level design · Games and state machines

Snake game on a grid

Reported in several places
SDE-2 (P40); Senior Software Engineer
Strategy
Observer
Deque
2 sources

Two or more independent public pages, at least one a candidate write-up.

The prompt

Design a snake game on a rectangular grid where the snake moves one cell at a time by adding a new head and removing its tail. One report links the round to the LeetCode snake game problem, says clarifying questions changed the scope so that leaving the board wraps to the opposite side, and mentions follow-ups on the data structure for the body, on several direction inputs arriving at once and how to synchronise them, and on unit tests. Food, growth and scoring are this answer's assumptions.

Restated in our own words, not a quote from Atlassian or any page. The answer below is written for this site.

Try it first.The answer is covered until you pick. Talk it through against a 60 minute clock, or just read it.

Clarify first

Pin the scope down before you name a single class.

Questions to ask first:

One snake or several? Assume one snake, single player.
What ends the game: hitting a wall, hitting itself, both? One report says the snake should reappear on the opposite side instead of dying. Assume a switchable rule: solid walls end the game, wrap-around does not, and hitting itself always does.
Who drives time: a real timer or an outside loop? Assume an outside loop calls tick(), so the game itself has no timers.
What if the player presses two keys inside one tick, or presses the opposite direction? Assume inputs are queued, capped at two, and a reversal is ignored.
Is there food, and how is it placed? The reports do not say. Assume one piece at a time on a free cell, growth by one and a score per meal, behind an interface so tests can script it.

Out of scope: rendering, speed levels, multiple snakes, networking and persistence of high scores.

Entities and relationships

Who owns what, and who talks to whom.

SnakeGame owns the rules: grid size, direction, score, status (running, over, won) and the tick() step. It has one Deque, one wall policy and one food source.
Deque is a doubly linked list holding the body from head to tail. Adding a head and removing the tail are both O(1).
Occupied set is a hash set of cell keys kept in step with the Deque, so the self-collision test is O(1).
WallPolicy is an interface with resolve(cell). SolidWalls returns null outside the grid, WrapAround maps the cell to the other side.
FoodSource is an interface with place(freeCells). FirstFreeFood and ScriptedFood are the deterministic versions; a random one has the same shape.
Listeners are callbacks that receive ate, over and won events, which is how a UI or a score board hears about the game.

The design

The class map, the main flow and the patterns that earn their place.

Snake game class mapThe game class owns the rules. Walls and food are strategies, the body is a deque, listeners hear events.

The UI turns key presses into direction requests.
The game takes at most one queued direction at the start of each tick.
The wall policy returns the next cell, or null when a solid wall is hit.
The head is added to the deque and the tail removed, unless the snake is growing.
After a meal the food source picks a new cell from the free cells.
Listeners receive ate, over or won events.

Open on the whiteboardAll 2 diagrams on one tidy board, with a step-by-step walkthrough.

Body data structure. A move is "add a head, drop the tail", so the body is a deque: a doubly linked list with pointers to both ends makes both operations O(1). A plain array makes unshift linear. Alongside it I keep a set of occupied cell keys, so asking "is the next cell part of the snake" is O(1) instead of a scan of the body.

One tick, in order:

If the game is not running, return. Otherwise take at most one pending direction from the input queue.
Compute the next cell from the head and the direction, then ask the WallPolicy to resolve it. Null means the snake hit a wall.
Decide whether the move eats: does the next cell equal the food cell?
Check the body. The cell the tail is about to leave is legal to enter, unless the snake is growing, because then the tail stays.
Remove the tail unless growing, add the new head, and update the set.
If it ate, bump the score, ask the food source for a new cell among the free cells, and emit ate. No free cell means the board is full and the player has won.

Patterns that earn their place. Strategy for walls and food, because both are rule variants a requirements change will touch (wrap-around, random versus scripted food) and tests need to script food. Observer for events, so scoring and UI stay out of the rules.

Simultaneous input. Key presses arrive outside the tick. They go into a small queue and each tick consumes one. A new direction is rejected if it equals or reverses the last queued direction, so two quick presses such as down then left both take effect, on consecutive ticks, instead of the second silently turning the snake into itself. In a threaded program the UI thread would only enqueue into a thread-safe queue and a single game-loop thread would own all state, so no lock is needed around the grid.

Trade-off: computing free cells on each meal is O(width * height). That is fine for small boards; a large board would keep a free set updated on every move.

The code

Runnable JavaScript, with the checks it passes.

atlassian-snake-game-lld.js

const DIRECTIONS = {
  UP: { x: 0, y: -1 },
  DOWN: { x: 0, y: 1 },
  LEFT: { x: -1, y: 0 },
  RIGHT: { x: 1, y: 0 },
};
const OPPOSITE = { UP: "DOWN", DOWN: "UP", LEFT: "RIGHT", RIGHT: "LEFT" };

function keyOf(cell) {
  return cell.x + "," + cell.y;
}

class Deque {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  addFirst(value) {
    const node = { value, prev: null, next: this.head };
    if (this.head) this.head.prev = node;
    else this.tail = node;
    this.head = node;
    this.size += 1;
  }
  removeLast() {
    const node = this.tail;
    this.tail = node.prev;
    if (this.tail) this.tail.next = null;
    else this.head = null;
    this.size -= 1;
    return node.value;
  }
  toArray() {
    const out = [];
    for (let node = this.head; node; node = node.next) out.push(node.value);
    return out;
  }
}

class SolidWalls {
  resolve(cell, width, height) {
    const inside = cell.x >= 0 && cell.y >= 0 && cell.x < width && cell.y < height;
    return inside ? cell : null;
  }
}

class WrapAround {
  resolve(cell, width, height) {
    return { x: (cell.x + width) % width, y: (cell.y + height) % height };
  }
}

class FirstFreeFood {
  place(free) {
    return free.length > 0 ? free[0] : null;
  }
}

class ScriptedFood {
  constructor(cells) {
    this.cells = cells.slice();
  }
  place(free) {
    while (this.cells.length > 0) {
      const cell = this.cells.shift();
      if (free.some((candidate) => keyOf(candidate) === keyOf(cell))) return cell;
    }
    return free.length > 0 ? free[0] : null;
  }
}

class SnakeGame {
  constructor({ width, height, start, direction, walls, food }) {
    if (!Number.isInteger(width) || !Number.isInteger(height) || width < 1 || height < 1) {
      throw new Error("the board needs a positive width and height");
    }
    if (!DIRECTIONS[direction]) throw new Error("unknown direction " + direction);
    if (!new SolidWalls().resolve(start, width, height)) throw new Error("the start cell is outside the board");
    this.width = width;
    this.height = height;
    this.direction = direction;
    this.walls = walls;
    this.foodSource = food;
    this.body = new Deque();
    this.body.addFirst(start);
    this.occupied = new Set([keyOf(start)]);
    this.pending = [];
    this.listeners = [];
    this.status = "running";
    this.score = 0;
    this.food = this.foodSource.place(this.freeCells());
    if (this.food === null) this.status = "won";
  }
  subscribe(listener) {
    this.listeners.push(listener);
  }
  emit(event) {
    this.listeners.forEach((listener) => listener(event));
  }
  freeCells() {
    const free = [];
    for (let y = 0; y < this.height; y += 1) {
      for (let x = 0; x < this.width; x += 1) if (!this.occupied.has(x + "," + y)) free.push({ x, y });
    }
    return free;
  }
  queueDirection(name) {
    const last = this.pending.length > 0 ? this.pending[this.pending.length - 1] : this.direction;
    if (!DIRECTIONS[name] || name === last || name === OPPOSITE[last] || this.pending.length >= 2) return false;
    this.pending.push(name);
    return true;
  }
  finish(status, reason) {
    this.status = status;
    this.emit({ type: status, reason });
    return status;
  }
  tick() {
    if (this.status !== "running") return this.status;
    if (this.pending.length > 0) this.direction = this.pending.shift();
    const head = this.body.head.value;
    const step = DIRECTIONS[this.direction];
    const next = this.walls.resolve({ x: head.x + step.x, y: head.y + step.y }, this.width, this.height);
    if (!next) return this.finish("over", "wall");
    const grows = this.food !== null && keyOf(next) === keyOf(this.food);
    const hitsBody = this.occupied.has(keyOf(next)) && (grows || keyOf(next) !== keyOf(this.body.tail.value));
    if (hitsBody) return this.finish("over", "self");
    if (!grows) this.occupied.delete(keyOf(this.body.removeLast()));
    this.body.addFirst(next);
    this.occupied.add(keyOf(next));
    if (!grows) return this.status;
    this.score += 1;
    this.food = this.foodSource.place(this.freeCells());
    this.emit({ type: "ate", score: this.score });
    return this.food === null ? this.finish("won", "board full") : this.status;
  }
}

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.

Extend it

The change requests an interviewer throws next.

How would you add speed levels that depend on score without touching the rules class?
What changes if two snakes share the grid and heads can collide with each other?
How would you record every tick so a finished game can be replayed from a seed?
How would you add a second kind of food that shrinks the snake or gives bonus points?
Key presses come from another thread. Where does synchronisation go, and why not lock the whole game?

Where candidates slip

The mistakes this problem punishes.

Mistakes this problem punishes:

Storing the body in an array and doing unshift and a full scan for collisions, then having no answer when asked about the cost.
Rejecting a move into the cell the tail is leaving, which wrongly kills a snake that is chasing its own tail, or failing to keep the tail when the snake grows.
Letting a reversal through, so a snake of length two dies when the player presses the opposite key.
Dropping all but the last key press in a tick, or applying several turns in one tick.
Placing food on top of the snake, or looping forever looking for a free cell when the board is full.
Hard-coding the timer and random food, which makes the game untestable.

Have a go before you read.

Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.

Always show the answer straight away

Now make it stick

Sketch the class map on the whiteboard Run a mock interview

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.

Now make it stick

Where this was reported

More on games and state machines