Understanding and Solving “Design Snake Game”: Interview Question

Today, we’re going to dive deep into the game that many of us played during the early era of mobile phones — the Snake Game!

Problem Statement 🐍

Design a Snake game that is played on a device with screen size height x width.

The snake is initially positioned at the top left corner (0, 0) with a length of 1 unit.

You are given an array food where food[i] = (ri, ci) is the row and column position of a piece of food that the snake can eat. When a snake eats a piece of food, its length and the game's score both increase by 1.

Each piece of food appears one by one on the screen, meaning the second piece of food will not appear until the snake eats the first piece of food.

When a piece of food appears on the screen, it is guaranteed that it will not appear on a block occupied by the snake.

The game is over if the snake goes out of bounds (hits a wall) or if its head occupies a space that its body occupies aftermoving (i.e. a snake of length 4 cannot run into itself).

Implement the SnakeGame class:

• SnakeGame(int width, int height, int[][] food) Initializes the object with a screen of size height x widthand the positions of the food.
• int move(String direction) Returns the score of the game after applying one direction move by the snake. If the game is over, return -1.

Intuition 💡

1. We will be using a Queue (Deque) data structure to keep track of the snake’s body. The reason being the snake moves in a way that the head advances and the tail retracts, which naturally resembles the operations of a queue.
2. We also need a Set to keep track of all the positions of the snake’s body for quick access when checking if the snake hits itself.
3. To know if the snake has eaten an apple, we will keep track of the current apple’s position and compare it with the snake’s head after each move.

Design 🎨

1. Initialize: Set the starting position of the snake and the first apple. The snake starts with a size of 1.
2. Move: Depending on the direction, we will determine the new head’s position. Check if the…