Menu
Source: AMAZON INTERVIEW QUESTION
Given a point P and other N points in two dimensional space, find K points out of the N points which are nearest to P.
What is the most optimal way to do this ?
This Wiki page does not provide much of help in building a algorithm.Any ideas/approaches people.
409
Approach: The idea is to calculate the Euclidean distance from the origin for every given point and sort the array according to the Euclidean distance found. Print the first k closest points from the list. Sort the points by distance using the Euclidean distance formula. Print the points obtained in any order.
The idea is to split the point set into two halves with a vertical line, find the closest pair within each half, and then find the closest pair between the two halves. The result of finding the closest pair within each half speeds up finding the closest pair between the halves.
A KD Tree does the job. It's a geometric data structure that can find nearest neighbors efficiently by cutting the search space similarly to a binary search.
The brute force method of finding the nearest of N points to a given point is O(N) -- you'd have to check each point. In contrast, if the N points are stored in a KD-tree, then finding the nearest point is on average O(log(N)) .
Solution 1 make heap of size K and collect points by minimal distance O(NLogK) complexity.
Solution 2: Take and array of size N and Sort by distance. Should be used QuickSort (Hoare modification). As answer take first K points. This is too NlogN complexity but it is possible optimize to approximate O(N). If skip sorting of unnecessary sub arrays. When you split array by 2 sub arrays you should take only array where Kth index located. complexity will be : N +N/2 +N/4 + ... = O(N).
Solution 3: search Kth element in result array and takes all point lesser then founded. Exists O(N) alghoritm, similar to search of median.
Notes: better use sqr of distance to avoid of sqrt operations, it will be greater faster if point has integer coordinates.
As interview answer better use Solution 2 or 3.
192
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
