Snake Game

Prompt

"Design the game of Snake. The board is a grid. The snake starts as a single cell in the top-left corner, moves one cell per step in a direction I give you, grows when it eats food, and dies when it hits a wall or itself. Write the class."

Clarifying questions

• How is food supplied? As an ordered list of positions given at construction; the next item appears only after the current one is eaten. Random placement is a follow-up.
• What does a step return? The current score (number of food eaten), or -1 when the game is over. After game over, further steps keep returning -1.
• Can the snake reverse into itself when it is longer than one cell? Treat a reversal as any other move; with length 2 or more it collides with its own neck and the game ends. The interviewer may instead want reversals ignored; ask.
• Is moving into the cell the tail currently occupies a collision? No. The tail vacates that cell during the same step, so the head may enter it. This is the case most solutions get wrong.
• Can food appear on the snake's body? Assume not; the input guarantees it. Say what you would do otherwise (skip that food, or re-place it).
• Real-time or step-driven? Step-driven: the caller supplies directions. A timer loop is a thin wrapper added later.

Requirements

Functional

• move(direction) advances the snake one cell and returns the score, or -1 on death.
• Growth by one cell per food eaten, with the food sequence consumed in order.
• Death on leaving the grid or on entering a cell occupied by the body (excluding the vacating tail).
• Expose the body cells and current food for rendering.

Non-functional

• move in O(1): a snake of length 10^4 must not be scanned per step.
• Game rules (what counts as death, how growth works) must be isolated so variants (wrap-around walls, obstacles) are local changes.
• Deterministic given the same inputs, so tests can be scripted.

Numbers

• A 100 x 100 board holds 10^4 cells, so the snake can reach length 10^4 and a game can run 10^6 steps. A per-step O(length) collision scan would be 10^10 operations over a long game; a hash set makes it 10^6. That is the arithmetic that justifies the second data structure.