353. Design Snake Game
Asked at Atlassian
Difficulty
Medium
Time
O(1) per move
Space
O(width * height)
Pattern
Array
Companies
1
Problem
Design a Snake game on a grid of height rows and width columns. The snake starts at the top-left cell (0, 0) with length 1, and the score starts at 0.
You are given a list food, where each entry [ri, ci] is a cell that holds food. Food appears one piece at a time: the next piece only shows up after the snake eats the current one. Food never appears on a cell the snake already occupies.
Each call to move(direction) moves the snake one cell in that direction ('U', 'D', 'L', 'R'). The snake's head moves into the new cell. If that cell has food, the snake grows by one (the tail stays) and the score goes up by 1. Otherwise the tail cell is removed, so the length stays the same. Return the current score after the move. The game ends and you return -1 if the head goes out of bounds (hits a wall) or if the head lands on a cell the body occupies. Note: moving into the cell the tail is just leaving is allowed, because the tail moves away at the same time.
The board and the snake
Constraints
- ●
1 <= width, height <= 10^4 - ●
1 <= food.length <= 50 - ●
food[i].length == 2 - ●
0 <= ri < height - ●
0 <= ci < width - ●
direction.length == 1 - ●
direction is 'U', 'D', 'L', or 'R' - ●
At most 10^4 calls will be made to move
Examples
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]][null, 0, 0, 1, 1, 2, -1]["SnakeGame", "move", "move", "move", "move"]
[[2, 2, [[0, 1]]], ["R"], ["D"], ["L"], ["U"]][null, 1, 1, 1, -1]Asked At
1 companies| 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.
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.
Deque plus hash set
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
O(1) per move timefrom 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 runs in O(1) per move time and O(width * height) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.