CODEWITHSUNDEEP
algorithmdata-structuresgraph
shallOvercome
shallOvercome

Reputation: 396

Find nearest delivery centers to a given area code

This was asked during interviewing process for a company. Suppose there is an interface to look for nearest delivery center to your area. All you have to enter is your zipcode/pincode and it returns the nearest delivery center. What would be the data structure and algorithm to do this? Like, you have broken your phone and want to go to a service center. You go to the company website and enter your zipcode to find out the nearest repair center. How does it do that?

I suggested a graph + hashmap solution where I will return the neighbouring nodes from a given node and addresses will be stored in hashmap w.r.t zipcodes but that wasn't good enough as the interviewer kept pressing on using the geographical property saying that you are not given the distance between two centers so how do you know which is the nearest and also if asked for top 3 nearest centers. I was not able to come up with any solution then. He was also asking me again and again what data you need to solve this thing. Would be really helpful to know what could be the approach for this as it has been bugging me for days. Thanks

Upvotes: 2

Views: 520

Answers (2)

Bernhard Barker
Bernhard Barker

Reputation: 55619

Most algorithms deal with single points - just taking the centre point of a zip code area should suffice.

For a single nearest neighbour, a Voronoi diagram seem like the way to go.

It separates the space into regions such that, given any query point, we know which point is closest.

Taken from Wikipedia:

A kd-tree is also an option:

The k-d tree is a binary tree in which every node is a k-dimensional point. Every non-leaf node can be thought of as implicitly generating a splitting hyperplane that divides the space into two parts, known as half-spaces. Points to the left of this hyperplane are represented by the left subtree of that node and points right of the hyperplane are represented by the right subtree. The hyperplane direction is chosen in the following way: every node in the tree is associated with one of the k-dimensions, with the hyperplane perpendicular to that dimension's axis. So, for example, if for a particular split the "x" axis is chosen, all points in the subtree with a smaller "x" value than the node will appear in the left subtree and all points with larger "x" value will be in the right subtree. In such a case, the hyperplane would be set by the x-value of the point, and its normal would be the unit x-axis.

Finding the k nearest neighbours is significantly more difficult. There is a k nearest neighbours algorithm, but this is a classification algorithm, so I'm not sure it helps here.

One option is to create a grid of the region. Then, given a point, we know which cell it's in, and we can simply query that cell and its neighbours until we've found the desired number of neighbours.

One just has to be careful here, as the next nearest point can actually be in another cell, e.g.:

--------------
   |        B|
 A | X       |
   |         |
   |         |
--------------

Given point X, the closest point is A, but B would be returned if we simply look in the same cell. We also need to look at all neighbouring cells after we've found k points.

Upvotes: 1

Tarik
Tarik

Reputation: 11209

You need the whole road network which is a sparse matrix containing the distance between all of the nodes. You also need to have the list of nodes containing the service centers. Having this, I think the A* algorithm should do the job in determining the distance between a given location and each service center, then picking up the least three in distance. I am certain there are more efficient algorithms but I believe the interviewer should concentrate on the way you think to resolve a problem rather than asking for implementation details such as data structures. Would I have to solve such a problem in real life, I would do a literature research first. I am not sure about what strategy is best when facing such interviewer and if he would have accepted such a response. Being assertive and providing an overview of the solution before diping into the details might have been better. Do not have regrets though. Benefit from the experience and move on. You do not know what bounties God has in store for you.

Upvotes: 1

Related Questions