Design a Snake Game (Queue and Set)

To solve this efficiently, I propose a hybrid approach combining a Deque and a Hash Set. First, we initialize a Deque to represent the snake's body segments, ordered from head to tail. This allows us to access the head in O(1) and remove the tail in O(1), which is crucial when the snake moves without eating. However, checking if the new head position collides with any existing body part requires scanning the entire Deque, resulting in O(N) complexity. To achieve the required O(1) performance, we simultaneously maintain a Hash Set containing all current body coordinates. When the snake moves, we first check if the new head coordinate exists in the set; if it does, a collision occurs instantly. If not, we remove the tail coordinate from both the Deque and the Set, then add the new head coordinate to both. This ensures our lookup remains constant time regardless of snake length. For Stripe's high-throughput environment, this structure prevents latency spikes during gameplay. We also handle boundary checks separately. This solution balances memory usage with computational efficiency, demonstrating robust data structure selection.