Design Snake Game — Deque-Based State Machine

Problem Statement#

Design a snake game on a width x height grid. The snake starts at position (0,0) and moves in directions U/D/L/R. Food appears at given positions sequentially. move(direction) returns the current score (food items eaten) or -1 if the game is over. The snake grows by 1 cell when it eats food.

Constraints:

• 1 <= width, height <= 10^4
• 1 <= food.length <= 50
• food[i][0] < height, food[i][1] < width
• direction is one of "U", "D", "L", "R"
• At most 10^4 calls to move

Input:  width=3, height=2, food=[[1,2],[0,1]], move("R"), move("D"), move("R")
Output: 0, 0, 1

Input:  ... move("U"), move("L")
Output: 2, -1  (self-collision)

Why This Problem Matters#

Snake game simulation tests your ability to maintain an ordered mutable collection with O(1) operations at both ends. The same data structure—a deque with an accompanying set for membership testing—appears in sliding window problems, browser history, and cache implementations. Amazon asks this problem because it exercises precise state management: the order of operations (check collision before adding head, remove tail before checking head collision) is subtle and error-prone.

In production systems, this pattern models any sequential process where items enter at one end and exit at the other while membership queries are required. Think of task queues, packet reordering buffers, and real-time game state synchronisation.

Understanding the correct order of operations in the snake simulation (tail removal before head collision check) is the key insight that separates candidates who truly understand the algorithm from those who guessed it.

The Core Insight#

Use a deque to store body positions in order, with the head at the front and tail at the back. Use a set of (row, col) tuples for O(1) self-collision checks—scanning the deque would be O(N).

The critical order of operations in move: (1) compute new head; (2) check wall collision; (3) if no food, remove tail from deque and set; (4) check if new head is in body set; (5) add new head to deque and set; (6) return score.

Remove the tail BEFORE checking head collision. If you remove tail after, a snake of length 1 moving straight would falsely detect a self-collision (new head equals old tail position, which should be vacated).

Visual Dry Run#

Solution (Optimal)#

from collections import deque
 
class SnakeGame:
    def __init__(self, width, height, food):
        self.w = width
        self.h = height
        self.food = food
        self.fi = 0
        self.snake = deque([[0, 0]])
        self.body = {(0, 0)}
        self.dirs = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
 
    def move(self, direction: str) -> int:
        dr, dc = self.dirs[direction]
        r, c = self.snake[0]
        nr, nc = r + dr, c + dc
        if nr < 0 or nr >= self.h or nc < 0 or nc >= self.w:
            return -1
        tail = self.snake[-1]
        if self.fi < len(self.food) and [nr, nc] == self.food[self.fi]:
            self.fi += 1
        else:
            self.snake.pop()
            self.body.discard((tail[0], tail[1]))
        if (nr, nc) in self.body:
            return -1
        self.snake.appendleft([nr, nc])
        self.body.add((nr, nc))
        return self.fi

class SnakeGame {
    constructor(width, height, food) {
        this.w = width;
        this.h = height;
        this.food = food;
        this.fi = 0;
        this.snake = [[0, 0]];
        this.body = new Set(["0,0"]);
        this.dirs = { U: [-1, 0], D: [1, 0], L: [0, -1], R: [0, 1] };
    }
 
    move(dir) {
        const [dr, dc] = this.dirs[dir];
        const [r, c] = this.snake[0];
        const [nr, nc] = [r + dr, c + dc];
        if (nr < 0 || nr >= this.h || nc < 0 || nc >= this.w) return -1;
        const tail = this.snake[this.snake.length - 1];
        if (this.fi < this.food.length &&
            this.food[this.fi][0] === nr && this.food[this.fi][1] === nc) {
            this.fi++;
        } else {
            this.snake.pop();
            this.body.delete(tail[0] + "," + tail[1]);
        }
        if (this.body.has(nr + "," + nc)) return -1;
        this.snake.unshift([nr, nc]);
        this.body.add(nr + "," + nc);
        return this.fi;
    }
}

Time: O(1) per move call — deque operations and set lookup are all constant time
Space: O(W * H) — body can grow up to the full grid size

Common Mistakes#

• Checking self-collision BEFORE removing the tail—this incorrectly marks the old tail position as occupied when the snake should have vacated it
• Using a list instead of a deque for the snake body—list.insert(0, ...) and list.pop(0) are O(N)
• Comparing food coordinates with == on lists vs tuples—ensure consistent types
• Not resetting the food index fi separately from the score—they are the same in this problem but could diverge in variants
• Forgetting to remove the tail from the body SET as well as the deque—the set becomes stale and will block valid moves

Interview Tips#

• Draw the deque state at each step to show you understand the head-at-front, tail-at-back invariant
• Explicitly walk through the tail-before-head-collision order of operations—this is the most common bug
• Mention that in JavaScript, Array.unshift() is O(N)—for a true O(1) solution in JavaScript, implement a doubly linked list or use a circular buffer
• The body set stores (row, col) tuples; in JavaScript, serialise to a string key since objects are compared by reference

Follow-up Questions#

• How would you render the snake game at 60fps in a browser? (Store grid as a 2D array; only update changed cells in the DOM)
• How would you add walls (obstacles) the snake must avoid? (Add obstacle positions to the body set at init)
• How would you implement multiplayer snake with two snakes sharing a grid? (Two deques and two sets; check cross-collision against both sets)
• What is the maximum possible score? (width * height - 1: the snake fills the entire grid minus its starting cell)
• How would you implement an AI snake player? (BFS/DFS to find a path to food that avoids the current body)

Key Takeaways#

• Use a deque for the snake body: O(1) appendleft (add head) and O(1) pop (remove tail)
• Use a set for O(1) body membership testing—scanning the deque for collision would be O(N)
• Critical order: remove tail FIRST, then check if new head collides with remaining body
• If food is eaten, skip tail removal—the snake grows by keeping the tail in place
• Wall collision must be checked before self-collision: both return -1 but wall check is simpler
• JavaScript Array.unshift() is O(N); prefer a doubly linked list for true O(1) head insertion
• The score equals fi (food index), which tracks how many food items have been eaten