This is not a practical question, I just want to discuss and study the structure of the data structure here, I heard him ask Google during an on-site interview. Please tell me how to improve my design, thanks!
In the beginning, I wanted to use deque to store x, y coordinate pairs for parts of the body of snakes.
deque<pair<x, y>> snakeBodyParts;
Because it is very easy to push forward when the snake moves - create a new pair of coordinates as a new base for the head at the same position of the head and in the current direction, and then throw it back to remove the tail. Thus, moving, there is, checking the head hit the wall all operations are O (1) and easy to implement with deque. But checking that the new position of the head is superimposed on the body of the snakes will require a loop in all the complexity of the body - O (L), L is the number of parts of the body.
To improve it, I thought about putting all the coordinates in unordered_set (C ++) or hashset (Java), while preserving my old deque, it can give me O (1) to check if the head body will hit now . But I don’t know if this is a good idea, because it almost doubles the amount and amount of memory, when I add / remove in deque, I need to do this with my hash.
unordered_set<pair<int, int>, pair_hash> bodyPartsSet;
I also thought about creating my own structure that looks like a linked list, except that it points to the previous node:
SnakeBodyNode {
int x;
int y;
SnakeBodyNode * prev;
}
Then I also need two pointers pointing to the head and tail, as well as a directional variable.
SnakeBodyNode * head;
SnakeBodyNode * tail;
char dir;
However, I do not see any advantage of this, I still need a hash to get O (1) to check if the head hits the body ..
Is there a flaw in my deque + hash design, or does anyone have a better idea to share?