educative.io

Educative

How do you use a doubly linked list to help find all the neighboring grids?

One way to find neighboring grids, according to the text, is to use a doubly linked list. The text says you can iterate forward or backward among the neighboring leaf nodes. Can I see some examples?

What if you need to split a leaf into 4 leaves? How does this compare with the other method of going up the quad tree?

1 Like

I have same question. This design problem lacks many details. @Design_Gurus

Another point I’m confused about is how to do you decide which places go to which grid?

And when searching for a grid, you search all nodes of the tree? This seems like a brute force solution.

1 Like

Let’s say the user falls into a grid X because his location is at the border of this grid. Now the places he wants should be in the 1 mile radio. Since the user is at the border of the grid, the places we return to the user MUST not be from its own grid only. We must query neighboring grids too, correct?

How do we do it? @Design_Gurus lease explain it.

@TJ_Singh, yes we do need to search the neighboring grids. This all depends upon the searching radius and the grid size. Uber design is based on Yelp design, please see Yelp design for most of the discussion around your questions:

What could be a reasonable grid size? Grid size could be equal to the distance we would like to query since we also want to reduce the number of grids. If the grid size is equal to the distance we want to query, then we only need to search within the grid which contains the given location and neighboring eight grids.

Please see Yelp design for answer to both of your questions.

@Thape_Samthree, assuming you know how to iterate a doubly linked list, let’s discuss how will we build the doubly linked list and how to break a node into four nodes.

We can easily find the next leaf node of a given leaf node through parent pointer, here is some relevent text from Yelp design:

We can keep a pointer in each node to access its parent, and since each parent node has pointers to all of its children, we can easily find siblings of a node.

We can keep searching the next leaf node by going up. Since each node has pointers to its next and previous leaf node, so while breaking it into four nodes, we can easily connect first and the fourth node with the previous and next leaf node respectively.

1 Like

let us say we have million of leaf nodes. and there may be lot of neraby places.If you see a leaf nodes,prev and next, how long will you go,?If you stop by radius threshold, it is possible that the current node does not fall in radius but the next to that falls?How will u handle this case?Also it is possible if u stop by 500 places, then the next nodes may have more relevant nodes,how will u handles such cases?What is the criteria to terminate looking for places?