LLD: Snake and Food Game with O(1) Movement

Requirements: Design the classic Snake game: the snake moves on a grid, grows when it eats food, and the game ends if the snake collides with itself or the wall. Movement (advancing the snake by one step) must be O(1), not O(length of snake).

Design: Represent the snake's body as a Deque (double-ended queue) of grid cells, giving O(1) push-front (new head) and pop-back (remove tail) for a normal move. Use a HashSet mirroring the deque's contents for O(1) self-collision checks (checking if the new head position already occupies the body) instead of an O(n) linear scan through the deque. On eating food: push the new head as usual but skip popping the tail (this grows the snake by one cell) and add the new head to the HashSet without removing the old tail from it. Track food positions in a queue/list of upcoming spawn coordinates (or a HashSet of active food cells) so multiple food items can be checked in O(1) too. This combination (Deque + HashSet, kept in sync on every move) is the standard trick achieving O(1) amortized time per move regardless of snake length.