Design Snake Game

Design Snake Game is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.

Problem statement

You are given the task of designing a Snake Game played on a 2D grid with dimensions width x height. The snake starts at position (0, 0) and can move in four directions: 'U' (up), 'D' (down), 'L' (left), and 'R' (right). The game is initialized with a list of food positions food, where food[i] = [ri, ci] represents the row and column of the ith food item. Food appears on the board in the order given by food.

Each time the snake moves, it must move one cell in the specified direction. If the snake's head moves to a cell containing food, the snake eats the food and its length increases by one. Otherwise, the snake moves forward by removing its tail. The game ends if the snake moves out of bounds or runs into itself.

Implement the following methods:

- SnakeGame(int width, int height, int[][] food): Initializes the game with the given grid size and food positions. - int move(String direction): Moves the snake in the specified direction. Returns the game's score (number of food items eaten) after the move, or returns -1 if the game is over due to collision or moving out of bounds.

Constraints: - 1 <= width, height <= 10^4 - 1 <= food.length <= 50 - food[i].length == 2 - 0 <= ri < height - 0 <= ci < width - direction is one of 'U', 'D', 'L', 'R'

Return the score after each move, or -1 if the game has ended.

Topics and companies

Topics: Array, Hash Table, Design, Queue, Simulation.

Reported in interviews at Amazon, Microsoft.

How to practise Design Snake Game on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(M), where M is the number of moves. Each move is processed in O(1) time due to O(1) deque and unordered_set operations. time and O(N + F), where N is the maximum possible snake length (up to width*height), and F is the number of food items. The snake's body and occupied set grow as the snake grows. space.

Open Design Snake Game in the code editor, or read the Design Snake Game editorial for a worked solution with its approach and complexity analysis.

Where Design Snake Game sits in the DSA pattern sheet

Problems related to Design Snake Game

Other problems that use the same Design (General/Specific) and Design Patterns techniques:

Preparing this workspace.