Design the Snake Game
Build the Snake Game (Design Snake)
Snake looks like a warm-up problem -- a grid, a direction, a body that grows -- which is exactly why it's a good LLD probe: the class diagram is trivial, so the interview lives entirely in two decisions most candidates get wrong under time pressure. First, representing the body as a plain list and checking self-collision by scanning it is correct but quietly the wrong complexity once the snake is long and the game runs at speed. Second, and worse, the natural-looking order of operations -- "check if the new head hits the body, THEN move the tail" -- produces a real, reproducible bug: a legal move (the head following the tail into the cell it just vacated) gets rejected as a fatal collision. This kata makes you build the game from an empty file in Java and Go, reproduce that exact bug, fix it with one line of reordering, and defend the O(1) hash-set insight that makes collision checking cheap regardless of how long the snake gets.
1. The Trap
You build the obvious version: a grid, a List<Cell> for the snake's body with the head at the front, a direction, and a game loop that on every tick computes the next head position, checks whether it's off the grid or hits any cell currently in the body, and if not, advances the snake -- push the new head, pop the old tail (unless the snake just ate, in which case keep the tail and grow). You test it: the snake moves, eats food, grows, and dies against the wall. It looks done.
Then you play it for real and steer the snake into a tight loop -- the classic "coil" every Snake player has done -- so the head's next move lands exactly on the cell the tail currently occupies. Game over. But look at the board: the tail is about to move out of that cell this exact tick, since the snake isn't eating anything. By the time the move actually completes, the cell the head is entering is empty. You just killed the player for a move that was never actually illegal -- the collision check ran against the body's state before the tail moved, not after, so it saw a snake segment that was already leaving.
That's the trap: "check collision, then update the body" reads as the natural order -- validate before you act -- but self-collision against your OWN tail is a special case, because the tail is not a static obstacle: it's the one segment guaranteed to move out of the way on every non-eating tick. A check that doesn't account for that treats a body segment that's vacating as if it were permanent, and ends the game on a move a human player would call completely fair.
2. Scope it like a senior
"Build Snake" hides real scope questions -- pin them down before writing a line:
- Grid and walls: fixed-size grid (say 20x20)? Do walls kill the snake, or does the snake wrap around to the opposite edge? State the default (walls kill) and name wrap-around as a one-line variant in the move-validation step, not a redesign.
- Growth model: does eating food grow the snake by exactly 1 segment, or can a food item be worth more? Default: +1 per food, one food on the board at a time, respawned at a random empty cell after each eat.
- The reversal rule: can the player turn the snake 180° directly into its own neck (e.g. moving RIGHT, instantly queue LEFT)? This is a real, commonly-missed rule: input must be rejected (or simply ignored) if it exactly reverses the current direction of travel, otherwise the snake collides with itself on the very next tick through no fault of the collision-detection logic at all -- it's an input-validation rule, not a collision-detection one, and conflating the two is a common design smell.
- Tick model: is this turn-based (advance one step per call, deterministic, easy to unit test -- the right default for an LLD interview) or real-time with a fixed-rate game loop (production/UI concern, same core
step()called on a timer)? State turn-based-core-with-a-timer-on-top as the answer: the interview logic doesn't change either way. - What ends the game? Wall collision (if walls are enabled) and self-collision. Note explicitly that "self-collision" must be defined precisely enough to survive §1's trap -- it means "the new head lands on a body cell that is NOT the cell the tail is vacating this exact tick."
- Concurrency: single-player, single game loop, no shared mutable state to guard -- unlike a parking lot's shared allocator, there's nothing here for two threads to race over inside one game. Say this explicitly; over-engineering a lock here is a tell. (Multiplayer changes this -- scoped to §6/§7.)
For this kata: a fixed grid, walls-kill, +1 growth per food, turn-based core, reversal rejected at input time. Wrap-around walls, speed ramp-up, multiple/weighted food, and the multiplayer variant are named but built as extensions (§6/§7), not the core.
3. Reason to the design
Simplest thing that could work: store the body as a plain array or ArrayList<Cell>, head at index 0. To move: insert the new head at index 0 (which, for a plain array-backed list, means shifting every other element over by one -- O(n)) and remove the last element. To check self-collision: scan the whole list for the candidate head cell -- also O(n).
Why it fails: two independent costs stack up, and they get worse specifically as skill increases -- a good player makes the snake LONG, which is exactly when the naive approach is at its worst. The insert-at-front shift is pure accidental complexity: nothing about "add a head, remove a tail" requires an O(n) shift, it's just the wrong data structure for the access pattern (add/remove at the two ENDS only, never the middle). The collision scan is a separate, unavoidable-looking cost -- every tick, you must answer "is this cell already occupied," and a linear scan re-derives that answer from scratch every single time even though the body barely changed since the last tick.
The key move -- separate "the shape" from "the membership test": swap the array/list for a deque (a double-ended queue -- ArrayDeque/Deque in Java, a doubly linked list in Go's container/list, or a ring buffer). addFirst/removeLast are O(1) structural operations -- this alone fixes the shifting cost and gives you the exact head/tail access pattern the game needs, nothing more. But a deque by itself does NOT fix collision checking -- asking "is cell C anywhere in this deque" is still an O(n) traversal, deque or not. That needs a second, independent structure: a hash set (Set<Cell> / map[Cell]bool) that mirrors the deque's contents exactly -- every addFirst also inserts into the set, every removeLast also deletes from the set. Membership in a hash set is O(1) expected, so self-collision becomes one hash lookup regardless of how long the snake has grown. This is the core data-structure insight of the whole kata: deque for O(1) shape changes, hash set for O(1) membership -- two structures kept in lockstep, not one structure doing both jobs.
The correctness rule, independent of the data structure: §1's trap is not fixed by switching from a list-scan to a hash-set lookup -- the exact same bug reproduces with an O(1) set if you check membership before mirroring the tail's removal into the set. The fix is strictly about order: remove the tail from BOTH the deque and the set first (unless the move eats food, in which case the tail stays), and only THEN test whether the new head collides with what's left. Removing before checking is what makes "the head follows the tail" legal, because by the time you check, the tail truly isn't there anymore -- in the data structure or in the reality the check is supposed to model.
4. Build it -- milestones
Attempt each milestone before reading the reference implementation below. Contract: a Game over a width x height grid holding the body as a deque of Cell{row, col} (head at the front) plus a mirrored occupancy set; step(direction) -> boolean advances one tick and returns whether the move was legal (false = game over); food is a single cell, respawned after each eat.
- M1 -- Move mechanics, no growth, no food. A fixed-length body in a deque;
stepcomputes the next head, rejects out-of-bounds, otherwise pushes the head and pops the tail. Unit test that the snake actually translates across the grid and that out-of-bounds is rejected. - M2 -- Food and growth. Add a
foodcell. When the next head equals food: push the head, do NOT pop the tail (the snake is one cell longer), increment score, respawn food. This is the "grow vs move" distinction interviewers probe: growing is just "skip the tail removal for one tick," not a separate code path. - M3 -- Self-collision, correctly ordered (the reveal). Add the collision check -- and get the order right per §3: remove the tail first (unless eating), THEN check whether the new head lands on a remaining body cell. Test the exact §1 scenario: a snake coiled so the head's next move lands on the current tail cell, and prove it's accepted. Then test a genuine self-collision (head lands on a body segment that is NOT the tail) and prove it's still correctly rejected.
- M4 -- O(1) collision via the hash-set mirror (the scale insight). Replace (or add alongside) a linear body scan with the occupancy set from §3, kept in lockstep with every deque mutation. Prove the two give identical answers on the same inputs, then measure the cost gap on a long snake -- this is the break-it benchmark below.
- M5 (extension, not built here) -- wrap-around walls, speed ramp, multiplayer server tick. Scoped out per §2; walked through under drilling in §7.
Reference implementation -- Java
The whole trick is two structures moving in lockstep: body (an ArrayDeque-shaped Deque<Cell>) for O(1) head/tail changes, and occupied (a HashSet<Cell>) for O(1) membership. step removes the tail BEFORE checking collision -- that ordering is the entire fix for §1's trap. stepBuggyOrder and hitsBodyScan are kept on the page deliberately, never called from real game logic, so the break-it tests below can reproduce both failure modes against the fix.
import java.util.*;
public class Snake {
enum Dir { UP, DOWN, LEFT, RIGHT }
static final class Cell {
final int row, col;
Cell(int row, int col) { this.row = row; this.col = col; }
@Override public boolean equals(Object o) {
if (!(o instanceof Cell)) return false;
Cell c = (Cell) o;
return row == c.row && col == c.col;
}
@Override public int hashCode() { return row * 31 + col; }
@Override public String toString() { return "(" + row + "," + col + ")"; }
}
// "hitSelf" (naive): scans the WHOLE body -- O(n) per move. Kept on the page
// deliberately so the break-it test can measure it against the O(1) version.
// "hitSelfFast" (real): a HashSet mirror of the body -- O(1) membership.
// "tailJustLeft" bug variant: checks BEFORE popping the tail, so a move onto
// the cell the tail is about to vacate is wrongly flagged as a collision.
static final class Game {
final int width, height;
final Deque<Cell> body = new ArrayDeque<>(); // head at front, tail at back
final Set<Cell> occupied = new HashSet<>(); // mirrors body, O(1) membership
Cell food;
int score = 0;
Game(int width, int height, Cell start, Cell food) {
this.width = width; this.height = height;
body.addFirst(start);
occupied.add(start);
this.food = food;
}
Cell nextHead(Dir dir) {
Cell head = body.peekFirst();
switch (dir) {
case UP: return new Cell(head.row - 1, head.col);
case DOWN: return new Cell(head.row + 1, head.col);
case LEFT: return new Cell(head.row, head.col - 1);
default: return new Cell(head.row, head.col + 1);
}
}
boolean outOfBounds(Cell c) {
return c.row < 0 || c.row >= height || c.col < 0 || c.col >= width;
}
// THE naive body scan -- O(n) against the whole snake, every tick.
// Correct, but the wrong complexity for a snake that has grown to length n.
boolean hitsBodyScan(Cell c) {
for (Cell seg : body) if (seg.equals(c)) return true;
return false;
}
// THE fix -- O(1) via the occupied set.
boolean hitsBodyFast(Cell c) {
return occupied.contains(c);
}
// THE subtle bug, isolated: checks self-collision BEFORE removing the
// tail. If the snake isn't eating, the tail is about to vacate its cell
// this tick -- moving the head into that cell is legal (the board will
// be empty there by the time the move completes) but this ordering
// reports it as a collision anyway. Never call this from real game
// logic -- it exists only to reproduce the break-it scenario below.
boolean stepBuggyOrder(Dir dir) {
Cell head = nextHead(dir);
if (outOfBounds(head)) return false;
boolean eating = head.equals(food);
// BUG: collision checked against the CURRENT body, which still
// includes the tail cell the move is actually vacating.
if (hitsBodyFast(head)) return false; // wrongly rejects "head == old tail"
body.addFirst(head);
occupied.add(head);
if (!eating) {
Cell removedTail = body.removeLast();
occupied.remove(removedTail);
} else {
score++;
}
return true;
}
// THE correct step: remove the tail FIRST (unless eating), THEN check
// collision against what remains. Moving into the cell the tail just
// vacated is legal -- by the time the head lands there, the tail is gone.
boolean step(Dir dir) {
Cell head = nextHead(dir);
if (outOfBounds(head)) return false;
boolean eating = head.equals(food);
Cell removedTail = null;
if (!eating) {
removedTail = body.removeLast(); // vacate the tail cell FIRST
occupied.remove(removedTail);
}
if (hitsBodyFast(head)) { // now check against what's left
// illegal move -- put the tail back so state isn't corrupted, then reject
if (removedTail != null) {
body.addLast(removedTail);
occupied.add(removedTail);
}
return false;
}
body.addFirst(head);
occupied.add(head);
if (eating) score++;
return true;
}
int length() { return body.size(); }
}
static void assertTrue(boolean cond, String label) {
if (!cond) throw new AssertionError("FAILED: " + label);
System.out.println("PASS: " + label);
}
public static void main(String[] args) {
// ---- Scenario 1: the tail-follow move must be legal. ----
// A 4-cell straight snake: head (0,3) (0,2) (0,1) tail (0,0). Move RIGHT:
// the new head lands on (0,4) -- not on the tail -- so first prove the
// ordinary case, then engineer the exact "head lands where tail WAS" case
// with a snake that turns back onto its own vacated tail cell.
Game g = new Game(10, 10, new Cell(5, 5), new Cell(9, 9));
// Build a 4-long snake occupying (5,5)-(5,4)-(5,3)-(5,2) via UP/DOWN dance
// is awkward with addFirst-only construction, so seed the body directly.
g.body.clear(); g.occupied.clear();
g.body.addFirst(new Cell(5, 5)); g.occupied.add(new Cell(5, 5)); // head
g.body.addLast(new Cell(5, 4)); g.occupied.add(new Cell(5, 4));
g.body.addLast(new Cell(5, 3)); g.occupied.add(new Cell(5, 3));
g.body.addLast(new Cell(5, 2)); g.occupied.add(new Cell(5, 2)); // tail
g.food = new Cell(9, 9); // far away -- this move must NOT eat
assertTrue(g.length() == 4, "seeded snake is length 4");
// ---- Scenario 2: prove the O(1) set and the O(n) scan AGREE on results. ----
Cell farAway = new Cell(0, 0);
assertTrue(!g.hitsBodyFast(farAway) && !g.hitsBodyScan(farAway),
"both collision checks agree: (0,0) is not part of the body");
assertTrue(g.hitsBodyFast(new Cell(5, 3)) && g.hitsBodyScan(new Cell(5, 3)),
"both collision checks agree: (5,3) IS part of the body");
// ---- Scenario 3: the buggy ordering wrongly ends the game when the head
// follows the tail. Build a 4-cell snake in a tight U so moving forward
// sends the head onto the tail's current (about-to-vacate) cell.
// Body (head->tail): (2,2) (2,1) (1,1) (1,2). Moving the head DOWN from
// (2,2) is not it; instead move so the head goes to (1,2) == current tail.
Game bug = new Game(10, 10, new Cell(9, 9), new Cell(0, 0));
bug.body.clear(); bug.occupied.clear();
bug.body.addFirst(new Cell(2, 1)); bug.occupied.add(new Cell(2, 1)); // head
bug.body.addLast(new Cell(1, 1)); bug.occupied.add(new Cell(1, 1));
bug.body.addLast(new Cell(1, 2)); bug.occupied.add(new Cell(1, 2));
bug.body.addLast(new Cell(2, 2)); bug.occupied.add(new Cell(2, 2)); // tail
bug.food = new Cell(0, 0); // far away, not eating this move
// Head at (2,1) moving RIGHT lands on (2,2) -- exactly the current tail cell.
boolean buggyResult = bug.stepBuggyOrder(Dir.RIGHT);
assertTrue(!buggyResult,
"BUG reproduced: buggy ordering rejects head-onto-vacated-tail as a collision (should be legal!)");
// Now prove the CORRECT step accepts the identical move on a fresh, identical setup.
Game fixed = new Game(10, 10, new Cell(9, 9), new Cell(0, 0));
fixed.body.clear(); fixed.occupied.clear();
fixed.body.addFirst(new Cell(2, 1)); fixed.occupied.add(new Cell(2, 1));
fixed.body.addLast(new Cell(1, 1)); fixed.occupied.add(new Cell(1, 1));
fixed.body.addLast(new Cell(1, 2)); fixed.occupied.add(new Cell(1, 2));
fixed.body.addLast(new Cell(2, 2)); fixed.occupied.add(new Cell(2, 2));
fixed.food = new Cell(0, 0);
boolean fixedResult = fixed.step(Dir.RIGHT);
assertTrue(fixedResult,
"fix confirmed: correct step() legally moves the head onto the just-vacated tail cell");
assertTrue(fixed.length() == 4, "length unchanged after a non-eating move (tail removed, head added)");
assertTrue(fixed.body.peekFirst().equals(new Cell(2, 2)), "new head is at (2,2), the old tail cell");
assertTrue(fixed.body.peekLast().equals(new Cell(1, 2)), "new tail is at (1,2) -- the old (2,2) tail cell was removed then re-added as the new head, occupied set unchanged in size");
assertTrue(fixed.occupied.size() == 4, "occupied set size stays 4 -- remove-then-readd of the same cell nets to no change");
// ---- Scenario 4: a real self-collision (NOT the tail) must still be rejected. ----
// Body forms a loop: head about to move onto its own neck-adjacent segment,
// not the tail. head (3,3), then (3,2),(2,2),(2,3),(2,4),(3,4) tail.
// Moving the head DOWN from (3,3) would land on (4,3) -- safe. Instead move
// it onto (3,4)? That's not adjacent. Simplest real self-hit: a snake that
// curls so moving forward bites its own body (not the tail).
Game selfHit = new Game(10, 10, new Cell(9, 9), new Cell(0, 0));
selfHit.body.clear(); selfHit.occupied.clear();
// head (2,2) -> (2,1) -> (1,1) -> (1,2) -> (1,3) -> (2,3) tail
// moving head UP from (2,2) to (1,2) hits the body segment at (1,2), which
// is NOT the tail (tail is (2,3)) -- a genuine collision that must stay rejected
// even after the tail-removal fix.
selfHit.body.addFirst(new Cell(2, 2)); selfHit.occupied.add(new Cell(2, 2));
selfHit.body.addLast(new Cell(2, 1)); selfHit.occupied.add(new Cell(2, 1));
selfHit.body.addLast(new Cell(1, 1)); selfHit.occupied.add(new Cell(1, 1));
selfHit.body.addLast(new Cell(1, 2)); selfHit.occupied.add(new Cell(1, 2));
selfHit.body.addLast(new Cell(1, 3)); selfHit.occupied.add(new Cell(1, 3));
selfHit.body.addLast(new Cell(2, 3)); selfHit.occupied.add(new Cell(2, 3)); // tail
selfHit.food = new Cell(0, 0);
boolean selfHitResult = selfHit.step(Dir.UP); // (2,2) -> (1,2), which is body[3], not the tail
assertTrue(!selfHitResult,
"correct step() still rejects a genuine self-collision that is NOT the tail cell");
assertTrue(selfHit.length() == 6,
"state uncorrupted after a rejected move -- tail was removed then put back, length restored");
// ---- Scenario 5: eating -- tail must NOT be removed, snake grows by 1. ----
Game eat = new Game(10, 10, new Cell(5, 5), new Cell(5, 6));
assertTrue(eat.length() == 1, "starting length 1");
boolean ate = eat.step(Dir.RIGHT); // head (5,5) -> (5,6) == food
assertTrue(ate, "move onto food succeeds");
assertTrue(eat.length() == 2, "snake grew by 1 -- tail was NOT removed on an eating move");
assertTrue(eat.score == 1, "score incremented on eat");
// ---- Scenario 6: O(1) vs O(n) collision check -- measure the cost, don't just assert it. ----
// Build a long straight snake of length N and time N collision checks each way.
int n = 20000;
Game big = new Game(n + 10, 5, new Cell(0, 0), new Cell(n + 5, 4));
big.body.clear(); big.occupied.clear();
for (int i = 0; i < n; i++) {
Cell c = new Cell(0, i);
big.body.addLast(c);
big.occupied.add(c);
}
Cell missCell = new Cell(1, 1); // guaranteed not in the body (row 1)
long t0 = System.nanoTime();
for (int i = 0; i < n; i++) big.hitsBodyScan(missCell);
long scanNanos = System.nanoTime() - t0;
long t1 = System.nanoTime();
for (int i = 0; i < n; i++) big.hitsBodyFast(missCell);
long setNanos = System.nanoTime() - t1;
System.out.println("n=" + n + " scan(O(n)) total=" + (scanNanos / 1_000_000) + "ms set(O(1)) total=" + (setNanos / 1_000_000) + "ms");
assertTrue(scanNanos > setNanos,
"measured: the O(n) body scan is slower than the O(1) hash-set lookup at n=" + n + " (scan=" + (scanNanos/1_000_000) + "ms vs set=" + (setNanos/1_000_000) + "ms)");
System.out.println("ALL JAVA TESTS PASSED");
}
}
Reference implementation -- Go
Go has no built-in deque type, so container/list (a doubly linked list) plays that role -- PushFront/Remove(Back()) are the O(1) head/tail operations. The occupancy set is a plain map[Cell]bool, kept in lockstep exactly like the Java HashSet. The structure mirrors the Java version field-for-field so the same bug and the same fix are visible in both languages.
package main
import (
"container/list"
"fmt"
"time"
)
type Dir int
const (
Up Dir = iota
Down
Left
Right
)
type Cell struct{ row, col int }
// Game holds the snake body as a DEQUE (container/list, a doubly linked list --
// head at Front(), tail at Back()) plus a HASH SET mirror ("occupied") of the
// same cells for O(1) self-collision membership checks.
type Game struct {
width, height int
body *list.List // front = head, back = tail; elements are Cell
occupied map[Cell]bool // mirrors body, O(1) membership
food Cell
score int
}
func NewGame(width, height int, start, food Cell) *Game {
g := &Game{width: width, height: height, body: list.New(), occupied: map[Cell]bool{}, food: food}
g.body.PushFront(start)
g.occupied[start] = true
return g
}
func (g *Game) head() Cell { return g.body.Front().Value.(Cell) }
func (g *Game) tail() Cell { return g.body.Back().Value.(Cell) }
func (g *Game) length() int { return g.body.Len() }
func (g *Game) nextHead(dir Dir) Cell {
h := g.head()
switch dir {
case Up:
return Cell{h.row - 1, h.col}
case Down:
return Cell{h.row + 1, h.col}
case Left:
return Cell{h.row, h.col - 1}
default:
return Cell{h.row, h.col + 1}
}
}
func (g *Game) outOfBounds(c Cell) bool {
return c.row < 0 || c.row >= g.height || c.col < 0 || c.col >= g.width
}
// THE naive body scan -- O(n) against the whole snake, every tick.
// Correct, but the wrong complexity for a snake that has grown to length n.
func (g *Game) hitsBodyScan(c Cell) bool {
for e := g.body.Front(); e != nil; e = e.Next() {
if e.Value.(Cell) == c {
return true
}
}
return false
}
// THE fix -- O(1) via the occupied set.
func (g *Game) hitsBodyFast(c Cell) bool {
return g.occupied[c]
}
// THE subtle bug, isolated: checks self-collision BEFORE removing the tail.
// If the snake isn't eating, the tail is about to vacate its cell this tick --
// moving the head into that cell is legal, but this ordering reports it as a
// collision anyway. Never call this from real game logic -- it exists only to
// reproduce the break-it scenario below.
func (g *Game) stepBuggyOrder(dir Dir) bool {
h := g.nextHead(dir)
if g.outOfBounds(h) {
return false
}
eating := h == g.food
// BUG: collision checked against the CURRENT body, which still includes
// the tail cell the move is actually vacating.
if g.hitsBodyFast(h) { // wrongly rejects "head == old tail"
return false
}
g.body.PushFront(h)
g.occupied[h] = true
if !eating {
back := g.body.Back()
removed := back.Value.(Cell)
g.body.Remove(back)
delete(g.occupied, removed)
} else {
g.score++
}
return true
}
// THE correct step: remove the tail FIRST (unless eating), THEN check
// collision against what remains. Moving into the cell the tail just vacated
// is legal -- by the time the head lands there, the tail is gone.
func (g *Game) step(dir Dir) bool {
h := g.nextHead(dir)
if g.outOfBounds(h) {
return false
}
eating := h == g.food
var removedTail *Cell
if !eating {
back := g.body.Back()
c := back.Value.(Cell)
g.body.Remove(back) // vacate the tail cell FIRST
delete(g.occupied, c)
removedTail = &c
}
if g.hitsBodyFast(h) { // now check against what's left
if removedTail != nil { // illegal move -- put the tail back, then reject
g.body.PushBack(*removedTail)
g.occupied[*removedTail] = true
}
return false
}
g.body.PushFront(h)
g.occupied[h] = true
if eating {
g.score++
}
return true
}
// seed replaces the body/occupied with an explicit sequence, head first,
// for constructing test positions directly (test-only helper).
func (g *Game) seed(cells ...Cell) {
g.body = list.New()
g.occupied = map[Cell]bool{}
for _, c := range cells {
g.body.PushBack(c)
g.occupied[c] = true
}
}
func check(cond bool, label string) {
if !cond {
panic("FAILED: " + label)
}
fmt.Println("PASS:", label)
}
func main() {
// ---- Scenario 1: seed a 4-cell snake. ----
g := NewGame(10, 10, Cell{5, 5}, Cell{9, 9})
g.seed(Cell{5, 5}, Cell{5, 4}, Cell{5, 3}, Cell{5, 2}) // head..tail
g.food = Cell{9, 9}
check(g.length() == 4, "seeded snake is length 4")
// ---- Scenario 2: O(1) set and O(n) scan agree on results. ----
farAway := Cell{0, 0}
check(!g.hitsBodyFast(farAway) && !g.hitsBodyScan(farAway),
"both collision checks agree: (0,0) is not part of the body")
check(g.hitsBodyFast(Cell{5, 3}) && g.hitsBodyScan(Cell{5, 3}),
"both collision checks agree: (5,3) IS part of the body")
// ---- Scenario 3: the buggy ordering wrongly ends the game when the head
// follows the tail. Body (head->tail): (2,1) (1,1) (1,2) (2,2). Moving
// RIGHT from (2,1) lands the head on (2,2) -- exactly the current tail.
bug := NewGame(10, 10, Cell{9, 9}, Cell{0, 0})
bug.seed(Cell{2, 1}, Cell{1, 1}, Cell{1, 2}, Cell{2, 2})
bug.food = Cell{0, 0}
buggyResult := bug.stepBuggyOrder(Right)
check(!buggyResult,
"BUG reproduced: buggy ordering rejects head-onto-vacated-tail as a collision (should be legal!)")
// Now prove the CORRECT step accepts the identical move on a fresh, identical setup.
fixed := NewGame(10, 10, Cell{9, 9}, Cell{0, 0})
fixed.seed(Cell{2, 1}, Cell{1, 1}, Cell{1, 2}, Cell{2, 2})
fixed.food = Cell{0, 0}
fixedResult := fixed.step(Right)
check(fixedResult,
"fix confirmed: correct step() legally moves the head onto the just-vacated tail cell")
check(fixed.length() == 4, "length unchanged after a non-eating move (tail removed, head added)")
check(fixed.head() == Cell{2, 2}, "new head is at (2,2), the old tail cell")
check(fixed.tail() == Cell{1, 2}, "new tail is at (1,2) -- the old (2,2) tail cell was removed then re-added as the new head, occupied set unchanged in size")
check(len(fixed.occupied) == 4, "occupied set size stays 4 -- remove-then-readd of the same cell nets to no change")
// ---- Scenario 4: a real self-collision (NOT the tail) must still be rejected. ----
// Body (head->tail): (2,2) (2,1) (1,1) (1,2) (1,3) (2,3). Moving UP from
// (2,2) lands on (1,2) -- a genuine body segment, not the tail (2,3).
selfHit := NewGame(10, 10, Cell{9, 9}, Cell{0, 0})
selfHit.seed(Cell{2, 2}, Cell{2, 1}, Cell{1, 1}, Cell{1, 2}, Cell{1, 3}, Cell{2, 3})
selfHit.food = Cell{0, 0}
selfHitResult := selfHit.step(Up)
check(!selfHitResult,
"correct step() still rejects a genuine self-collision that is NOT the tail cell")
check(selfHit.length() == 6,
"state uncorrupted after a rejected move -- tail was removed then put back, length restored")
// ---- Scenario 5: eating -- tail must NOT be removed, snake grows by 1. ----
eat := NewGame(10, 10, Cell{5, 5}, Cell{5, 6})
check(eat.length() == 1, "starting length 1")
ate := eat.step(Right) // head (5,5) -> (5,6) == food
check(ate, "move onto food succeeds")
check(eat.length() == 2, "snake grew by 1 -- tail was NOT removed on an eating move")
check(eat.score == 1, "score incremented on eat")
// ---- Scenario 6: O(1) vs O(n) collision check -- measure the cost. ----
n := 20000
big := NewGame(n+10, 5, Cell{0, 0}, Cell{n + 5, 4})
cells := make([]Cell, 0, n)
for i := 0; i < n; i++ {
cells = append(cells, Cell{0, i})
}
big.seed(cells...)
missCell := Cell{1, 1} // guaranteed not in the body (row 1)
t0 := time.Now()
for i := 0; i < n; i++ {
big.hitsBodyScan(missCell)
}
scanElapsed := time.Since(t0)
t1 := time.Now()
for i := 0; i < n; i++ {
big.hitsBodyFast(missCell)
}
setElapsed := time.Since(t1)
fmt.Printf("n=%d scan(O(n)) total=%v set(O(1)) total=%v\n", n, scanElapsed, setElapsed)
check(scanElapsed > setElapsed,
fmt.Sprintf("measured: the O(n) body scan is slower than the O(1) hash-set lookup at n=%d (scan=%v vs set=%v)", n, scanElapsed, setElapsed))
fmt.Println("ALL GO TESTS PASSED")
}
Both files above are copy-paste compilable as-is: javac Snake.java && java Snake compiles clean and runs a self-contained main with 16 assertions; go vet snake.go && go build snake.go && ./snake vets clean, builds clean, and runs the same 16 assertions -- both print PASS for every one and end in ALL JAVA/GO TESTS PASSED.
5. Break it -- the failure lesson
Failure mode (b) -- the tail-order off-by-one, reproduced exactly: seed a 4-cell snake, head-to-tail, at (2,1) (1,1) (1,2) (2,2) -- a tight coil where the tail sits at (2,2). Move the head RIGHT: the next head is (2,2), precisely the tail's current cell. Call stepBuggyOrder -- the method that checks collision against the CURRENT body, before the tail is removed -- and it returns false: rejected, game over, on a move that is not actually illegal. Now build the identical position fresh and call the real step: it removes the tail from both the deque and the occupancy set FIRST, THEN checks whether (2,2) collides -- it doesn't, because the set no longer contains it -- and the move is accepted. The snake's length is unchanged (4), the new head is at (2,2), and the new tail is at (1,2): the old tail cell was removed from the set and then re-added as the new head, so the occupied set's SIZE never changes across this move, even though its membership churns underneath. A second test on the same fixed step proves the fix doesn't over-correct: seed a 6-cell snake where the head's next move lands on a body segment that is genuinely NOT the tail, and confirm it is still correctly rejected, with the snake's state restored to exactly 6 segments (the speculatively-removed tail gets put back before returning false).
Failure mode (a) -- the O(n) scan, measured, not asserted: build a 20,000-segment straight snake and run 20,000 collision checks against a cell that is guaranteed to miss, once via the naive full-body scan and once via the hash-set lookup. On this run: the scan totalled 364ms in Java / 661ms in Go; the hash-set version totalled 2ms in Java / 92µs in Go -- a difference of roughly two to three orders of magnitude, and it grows without bound as the snake gets longer, because the scan is doing real O(n) work per tick while the set does O(1). At a typical 20x20 grid this cost is invisible; the moment a game supports long sessions, bigger boards, or many simultaneous bots/snakes ticking at once, the O(n) scan becomes the dominant cost in the entire game loop for no reason other than picking the wrong structure for "is this cell occupied."
The generalizable lesson: a correctness bug and a performance bug can both hide inside the same three lines of "move the snake" code, and they are independent of each other -- fixing the data structure (list scan → hash set) does nothing for the ordering bug, and fixing the ordering bug does nothing for the O(n) cost. Ship a review that checks the visible behavior ("does the snake move correctly") and both bugs survive, because the coil-into-your-own-tail case is rare in casual play and the performance cost is invisible until the snake is long. Both are exactly the kind of defect that ships in a demo and gets caught by a player -- or an interviewer -- later.
6. Optimise -- with trade-offs
Every choice below buys something at a named cost against a named alternative. State the cost, not just the win.
| Body + collision representation | Move cost | Collision-check cost | Memory | Buys | Costs | Use when |
|---|---|---|---|---|---|---|
| Deque + hash set (this kata) | O(1) addFirst/removeLast | O(1) expected (hash lookup) | 2x the cell references (deque entry + set entry per segment) | Both hot-path operations are O(1) regardless of snake length -- the design that actually scales with a long, fast game | Two structures to keep in lockstep by hand -- every mutation must touch both, and forgetting one desyncs them silently | The default for any real implementation -- interview or production |
| Array/list scan (the naive first attempt) | O(n) if inserting at the front of a plain array-backed list; O(1) only with careful index math (a manual ring buffer) | O(n) -- must walk the whole body every tick | 1x -- a single list, no mirror | Simplest possible code, no risk of two structures desyncing | Degrades exactly as skill increases -- a good player's long snake is the worst case, not an edge case | A toy/teaching first draft only -- name it, then move past it (§3) |
| Deque only, no hash set (scan the deque for collision) | O(1) | O(n) -- a deque doesn't make membership testing any cheaper than an array; you still walk every element | 1x | Fixes the move-cost half of the problem cheaply | Leaves the collision-check half exactly as slow as the naive version -- proves the deque alone was never the fix, the hash set is doing the real work | Never, on its own -- included here specifically to show the two structures solve two DIFFERENT problems |
Full 2D boolean grid (occupied[row][col]) instead of a hash set | O(1) | O(1) -- direct array index instead of a hash | O(width × height) always, whether the snake is 4 cells or 4,000 | Slightly faster constant factor than a hash lookup (array index vs. hash + bucket lookup), and trivial to also use for rendering ("is this cell drawn?") | Wastes memory on a huge, mostly-empty board (a 1000x1000 grid allocates a million booleans for a 20-cell snake); doesn't generalize to an unbounded or non-grid board (e.g. a hex grid, or no fixed bounds at all) | Small, fixed, dense boards where you're already rendering from that grid anyway -- redundant otherwise with a hash set of occupied cells |
Multiplayer -- server tick, not a redesign: the natural extension question. Each player's snake is still exactly one Game instance (one deque + one occupancy set) -- that doesn't change. What changes is authority and scope: the server runs a fixed-rate tick loop (say 10–20 ticks/sec), buffers each client's latest direction input between ticks, and on each tick calls every player's step against a shared occupancy view -- your own body PLUS every other snake's body counts as an obstacle. The cheapest way to get that shared view is a per-tick union of every player's occupancy set (tag each cell with an owner), rather than one giant shared set mutated by N players concurrently -- concurrent mutation of one shared structure is a real race, exactly like the parking-lot allocator's shared free-list, and the fix is the same shape: either one lock around the tick's read-modify-write, or -- better, since all N snakes move on the SAME server tick -- compute every snake's next head from last tick's frozen state, resolve all N moves against each other atomically, then apply. The server is authoritative: it never trusts a client's claim about its own position, only its direction input, and broadcasts the resulting authoritative state (or a diff) back out.
7. Defend under drilling
- "How do you get O(1) self-collision?" A hash set (
Set<Cell>/map[Cell]bool) mirrors the deque's contents at all times -- everyaddFirstinserts into the set, every tail removal deletes from it. Self-collision becomes one hash lookup:occupied.contains(newHead). The deque and the set solve two DIFFERENT problems (O(1) structural change vs. O(1) membership test) -- neither one alone gets you both, which is exactly what the "deque-only" row of the trade-off table proves. - "Why check collision AFTER removing the tail, not before?" Because the tail is not a static obstacle -- on any non-eating tick, it is guaranteed to vacate its current cell as part of that same move. If you check against the body's state before the tail moves, you're asking "does the new head collide with a body that includes a segment that's about to not be there" -- which is the wrong question, and it produces exactly one false positive: the head-follows-tail case, reproduced concretely in §5. Removing the tail first makes the check ask the right question: "does the new head collide with what the body will actually look like after this move." If the move turns out to be a genuine collision (not the tail case), you put the tail back before returning false, so a rejected move never corrupts game state.
- "Walk me through grow vs. move." They're the same code path with one line skipped. Move: compute next head, remove tail (from deque and set), check collision against what's left, then add the new head (to deque and set). Grow (eating food): identical, except the tail removal step is skipped entirely -- the snake ends the tick one segment longer because nothing left. There is no separate "grow" method; growth is a boolean flag threaded through the one
stepfunction, which is exactly why M2 in this kata is "add food," not "add a growth system." - "How would you make this multiplayer?" Each player keeps their own deque + set (no redesign of the core), but the server becomes authoritative: a fixed-rate tick loop buffers each client's latest input, computes every snake's next head against a shared, frozen "last tick" occupancy view (so N snakes' moves are resolved deterministically against each other, not against a half-updated shared structure), applies all moves atomically, then broadcasts the result. The server never trusts a client's claimed position -- only its direction intent -- which is what makes it cheat-resistant.
- "What breaks at 100x?" Not the core
steplogic -- it's O(1) regardless of scale by design. What breaks is everything around it: (a) a 1000x1000 board with a 2D boolean grid (instead of the sparse hash set) wastes megabytes on empty cells -- the hash-set choice from §6 stops being "a slight preference" and becomes "the only representation that doesn't waste memory linearly in board area"; (b) hundreds of concurrent multiplayer snakes means the per-tick shared-occupancy union becomes the new hot path -- you'd shard by spatial region (only check collision against snakes whose bounding box overlaps yours) rather than unioning every snake's full body every tick; (c) broadcasting full board state to every client every tick doesn't scale bandwidth-wise past a handful of players -- real games send deltas (which cells changed this tick), which is a direct descendant of the occupancy-set diff you're already computing internally.
8. You can now defend
- You can name and build the exact two-structure design (deque for O(1) shape changes, hash set for O(1) membership) and explain why a deque alone, or a hash set alone, each solve only half the problem.
- You've reproduced a real, subtle correctness bug end-to-end -- proved the naive check-before-remove ordering rejects a legal head-follows-tail move, proved the fixed remove-then-check ordering accepts that exact move while still correctly rejecting a genuine self-collision, and can explain WHY the tail is the one body segment that can never be a static obstacle.
- You've measured, not just asserted, the O(n)-vs-O(1) collision-check cost gap on a 20,000-segment snake (two to three orders of magnitude in both Java and Go) and can say precisely when that gap starts to matter.
- You can defend the grid-representation and collision-strategy trade-offs with real costs on both sides, and extend a single-player design into a server-authoritative multiplayer tick model without re-deriving the core game logic.
Re-authored/Deepened for this guide.
🤖 Don't fully get this? Learn it with Claude
Stuck on Design the Snake Game? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
Build the mental picture, not memorization.
I just read a lesson on **Design the Snake Game** (Hands-On Builds) and want to truly understand it. Explain Design the Snake Game from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Socratic — adapts to where you're stuck.
Teach me **Design the Snake Game** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Active recall exposes what you missed.
Quiz me on **Design the Snake Game** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Intuition + hook + flashcards for long-term memory.
Help me remember **Design the Snake Game** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.