Interview Q: Given the m station and n house, print the nearest k stations for each house

Question

There are m stations and n houses, (x, y) the coordinates of each station and house, the nearest station for each house is issued.

Later the question was generalized to search for k nearest stations from each house.

My trick: for each house, build a bunch of distances (from bottom to top) to the stations, and then pop k. Do the same for all homes. O (n * (m + klogm));

Alternatively, for each house, create an order statistics tree at the stations, then find the node with the rank and go through the entire tree below the node. Do the same for all homes. O (n * (mlogm + logm + k))

Are there any better alternatives to this? Any DS graph based solution that is better than this?

Answer 1

It sounds like a great place to use a kd tree , quadtree or other space splitting tree. The problem of "finding k objects closest to some test point" is called the problem of k-nearest neighbors, and these two data structures solve it extremely efficiently. They are also quite simple to implement.

In particular: build a kd tree or a quadrant from the stations. Then, for each house, query the k-nearest neighbors in that house in the data structure to find the nearest stations.

Hope this helps!