Design Snake Game

Design Snake Game

What is this problem about?

The Design Snake Game interview question asks you to simulate the mechanics of the classic mobile game. You are given a screen size and a list of food positions. You need to implement a move function that takes a direction (Up, Down, Left, Right) and returns the current score. The snake grows when it eats food, and the game ends if the snake hits a wall or itself.

Why is this asked in interviews?

Companies like Google, Amazon, and Uber use this problem to test your ability to manage dynamic state and choose efficient data structures. It evaluates how you handle coordinate systems, collision detection, and sequential updates. This coding problem is an excellent test of your proficiency with the queue interview pattern for managing the snake's body and hash table design pattern for $O(1)$ self-collision checks.

Algorithmic pattern used

This problem relies on a Queue and a Hash Set.

1. A Queue (specifically a Deque) stores the coordinates of the snake's body. The front is the head, and the back is the tail.
2. A Hash Set stores the same coordinates to allow for $O(1)$ checks to see if the snake has hit itself.
3. When the snake moves:
   • Calculate the new head position.
   • Check for wall collisions.
   • Remove the tail from the set temporarily.
   • Check for self-collisions (if the new head is in the set).
   • If there is food at the new head, keep the tail (snake grows) and move to the next food item.
   • If no food, remove the tail from the queue.
   • Add the new head to both the queue and the set.

Example explanation

Screen: $3 imes 3$, Food: [[1, 2], [0, 1]].

1. move("R"): Head moves from (0,0) to (0,1). No food. Tail (0,0) is removed. Snake: [(0,1)].
2. move("D"): Head moves from (0,1) to (1,1). No food. Tail (0,1) is removed. Snake: [(1,1)].
3. move("R"): Head moves from (1,1) to (1,2). Food! Score becomes 1. Tail (1,1) stays. Snake: [(1,2), (1,1)].

Common mistakes candidates make

• Collision Check Order: Forgetting to remove the tail before checking if the head hits the body. The snake's head can safely move into the position the tail just vacated.
• Inefficient Search: Using a list to check for self-collisions, which makes the move operation $O(N)$ instead of $O(1)$.
• Food Management: Not keeping track of which food item is "next" in the sequence.

Interview preparation tip

Always clarify the boundary conditions. For example, if the snake is length 2 and moves "Up" then "Down", it hits itself. Using a Deque is essential here because you need to efficiently add to the front (head) and remove from the back (tail).