Design Snake Game
Asked at Atlassian
Problem
Design a Snake game that starts at (0,0) on a 2D grid. The snake moves in the given direction, eats food to grow, and dies if it hits a wall or itself. This tests your ability to simulate a real-time game with appropriate data structures for the snake body and collision detection.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | Medium | View all Atlassian questions → |
How to Think About It
Brute force: represent the snake as a list of positions. On each move, add the new head, check collisions, and if no food eaten, remove the tail. That's O(n) per move where n is snake length, due to checking all body segments for self-collision.
Key insight: use a deque for the snake body (O(1) add/remove at both ends) and a hash set of occupied positions for O(1) collision detection. The deque maintains the order of body segments.
The deque stores positions from head to tail. On move: calculate new head position. Check if new head is in the hash set (collision) or out of bounds (wall). If food at new head: add head, don't remove tail (grow). If no food: add head, remove tail.
The hash set must be updated in sync with the deque. When adding a new head, add to the set. When removing the tail (no food), remove from the set. This gives O(1) collision detection.
Edge cases: snake fills the entire grid (win condition), single-cell snake, food spawned on snake (re-spawn), move into opposite direction (forbid - can't reverse), initial position has food.
Visual walkthrough for 4x4 grid, food at [(1,2), (0,1)]:
Initial: deque=[(0,0)], set={(0,0)}, score=0.
move("R"): new head=(0,1). Not in set. No food. Remove tail (0,0). deque=[(0,1)]. set={(0,1)}.
move("D"): new head=(1,1). Not in set. No food. deque=[(1,1)]. set={(1,1)}.
move("R"): new head=(1,2). Food! Score=1. deque=[(1,2),(1,1)]. set={(1,2),(1,1)}.
move("R"): new head=(1,3). No food. deque=[(1,3),(1,2)]. set={(1,3),(1,2)}.
move("U"): new head=(0,3). No food. deque=[(0,3),(1,3)]. set={(0,3),(1,3)}.
Optimal Approach
Data structures:
snake: deque of (row, col) positions, head at front, tail at backoccupied: set of positions for O(1) collision checkfood_queue: queue of food positions (or list with index)score: current scorewidth,height: grid dimensions
move(direction):
- Calculate new head position based on direction.
- Check wall collision: if new position is out of bounds, return -1.
- Check self collision: if new position is in
occupied, return -1. - Add new head to deque and occupied set.
- Check if food at new position:
- If yes: increment score. Don't remove tail (grow).
- If no: remove tail from deque and occupied set.
- Return score.
Time: O(1) per move (hash set operations). Space: O(width * height) for the snake body in worst case.
What Trips People Up in Real Interviews
Using a list instead of a deque for the snake body. List pop from the front is O(n). A deque gives O(1) for both appendleft and pop.
Not using a hash set for collision detection. Checking the deque for self-collision is O(n). A hash set gives O(1) membership checks.
Forgetting that eating food means the snake grows (don't remove tail). When the new head lands on food, add the head but skip removing the tail. This increases the snake length by 1.
Not handling the case where the snake's tail is at the food position. Before removing the tail, check if it would be removed. If the new head equals the current tail, the tail would have moved, so it's not actually a collision.
Allowing the snake to reverse direction. Moving in the opposite direction (e.g., moving left when currently moving right) should be invalid for a snake longer than 1 segment. The problem may or may not require this check.
Solution Code
from collections import deque
class SnakeGame:
def __init__(self, width, height, food):
self.width = width
self.height = height
self.food = deque(food)
self.score = 0
self.snake = deque([(0, 0)])
self.occupied = {(0, 0)}
self.directions = {"U": (-1, 0), "D": (1, 0), "L": (0, -1), "R": (0, 1)}
def move(self, direction):
dr, dc = self.directions[direction]
head_r, head_c = self.snake[0]
new_r, new_c = head_r + dr, head_c + dc
if new_r < 0 or new_r >= self.height or new_c < 0 or new_c >= self.width:
return -1
if (new_r, new_c) in self.occupied:
tail_r, tail_c = self.snake[-1]
if (new_r, new_c) == (tail_r, tail_c):
self.occupied.discard((tail_r, tail_c))
self.snake.pop()
else:
return -1
self.snake.appendleft((new_r, new_c))
self.occupied.add((new_r, new_c))
if self.food and (new_r, new_c) == self.food[0]:
self.food.popleft()
self.score += 1
else:
tail_r, tail_c = self.snake.pop()
self.occupied.discard((tail_r, tail_c))
return self.scoreFrequently Asked Questions
What is the Design Snake Game problem?
Design a Snake game that starts at (0,0) on a 2D grid. The snake moves in the given direction, eats food to grow, and dies if it hits a wall or itself. This tests your ability to simulate a real-time game with appropriate data structures for the snake body and collision detection.
How do you solve Design Snake Game?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Design Snake Game?
Design Snake Game is asked at Atlassian. It is a medium difficulty problem.
What are common mistakes on Design Snake Game?
- Using a list instead of a deque for the snake body. List pop from the front is `O(n)`. A deque gives `O(1)` for both appendleft and pop.
- Not using a hash set for collision detection. Checking the deque for self-collision is `O(n)`. A hash set gives `O(1)` membership checks.
- Forgetting that eating food means the snake grows (don't remove tail). When the new head lands on food, add the head but skip removing the tail. This increases the snake length by 1.
- Not handling the case where the snake's tail is at the food position. Before removing the tail, check if it would be removed. If the new head equals the current tail, the tail would have moved, so it's not actually a collision.
- Allowing the snake to reverse direction. Moving in the opposite direction (e.g., moving left when currently moving right) should be invalid for a snake longer than 1 segment. The problem may or may not require this check.