Course4all

Design Snake Game

Expert Answer & Key Takeaways

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on State Management and API Design. ### Core Principles 1. Encapsulation: Keep data private and expose functionality through well-defined methods. 2. Trade-offs: Every design choice has a cost. Is it better to have O(1)O(1) read and O(N)O(N) write, or vice versa? 3. State Consistency: Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for O(1)O(1) caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - HashMap: Provides O(1)O(1) lookups for keys to their corresponding nodes. - DLL: Provides O(1)O(1) addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in Queue using Stacks or Dynamic Arrays. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is O(1)O(1), and "flipping" elements to another stack happens only when necessary, averaging O(1)O(1) per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., Circular Queue, Hit Counter). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., Bounded Blocking Queue). - Use Mutexes (Locks) to prevent data races. - Use Condition Variables (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. Identify the API: What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. Define the State: What variables represent the current state? (Size, Capacity, Pointers). 3. Choose the Data Structures: Select the combination that minimizes time complexity for the most frequent operations. 4. Dry Run: Trace the state changes through a sequence of operations based on your chosen structure.

Design Snake Game

Design a Snake game that is played on a device with screen size height×widthheight \times width. The snake is initially positioned at the top left corner (0,0)(0, 0) with a length of 1 unit.

Logic

  1. Move the head.
  2. Check boundaries and self-collision.
  3. If head hits food, increase length (don't remove tail).
  4. Otherwise, move forward (remove tail).
Medium

Examples

Input: SnakeGame(3, 2, [[1, 2], [0, 1]]), move("R"), move("D"), move("R"), move("U"), move("L"), move("U")
Output: 0, 0, 1, 1, 2, -1
Approach 1

Level II: Deque only (Body only scan)

Intuition

Maintain the body in a Deque. For collision check, iterate through the entire deque (O(N)O(N)). This avoids the secondary HashSet but is slower for long snakes.
⏱ O(N) per move.💾 O(N).
java
class SnakeGame {
    Deque<Integer> body = new LinkedList<>();
    int[][] food; int foodIdx, w, h, score;
    public SnakeGame(int width, int height, int[][] food) {
        this.w = width; this.h = height; this.food = food; body.add(0);
    }
    public int move(String dir) {
        int head = body.peekFirst(), r = head / w, c = head % w;
        if (dir.equals("U")) r--; else if (dir.equals("D")) r++;
        else if (dir.equals("L")) c--; else if (dir.equals("R")) c++;
        if (r < 0 || r >= h || c < 0 || c >= w) return -1;
        int next = r * w + c;
        if (foodIdx < food.length && r == food[foodIdx][0] && c == food[foodIdx][1]) {
            foodIdx++; score++;
        } else body.removeLast();
        if (body.contains(next)) return -1;
        body.addFirst(next); return score;
    }
}
Approach 2

Level III: Deque + HashSet

Intuition

Use a Deque to store the coordinates of the snake's body (head at front, tail at back). Use a HashSet of encoded coordinates (r * width + c) for O(1)O(1) self-collision check.
⏱ O(1) per move.💾 O(N + F) where N is snake length, F is food items.
java
class SnakeGame {
    Deque<Integer> body = new LinkedList<>();
    Set<Integer> set = new HashSet<>();
    int[][] food; int foodIdx, w, h, score;
    public SnakeGame(int width, int height, int[][] food) {
        this.w = width; this.h = height; this.food = food;
        body.add(0); set.add(0);
    }
    public int move(String dir) {
        int head = body.peekFirst(), r = head / w, c = head % w;
        if (dir.equals("U")) r--;
        else if (dir.equals("D")) r++;
        else if (dir.equals("L")) c--;
        else if (dir.equals("R")) c++;
        if (r < 0 || r >= h || c < 0 || c >= w) return -1;
        int next = r * w + c;
        int tail = body.peekLast();
        set.remove(tail); // Tail moves out, head can move in to old tail spot
        if (set.contains(next)) return -1;
        if (foodIdx < food.length && r == food[foodIdx][0] && c == food[foodIdx][1]) {
            set.add(tail); body.addLast(tail); foodIdx++; score++;
        }
        body.addFirst(next); set.add(next);
        return score;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionDesign Underground System
Next Question →LFU Cache