Nearest Point problem
This was the question asked to Anirudh in his google interview. He could not do it (who cares! He got the job :D)
I could give a vague but correct answer :)
You have n points on a 2-D plane. You have to execute the query, given a fresh point, which of these n points is closest to it. This is termed as gas-station problem or postman problem, as in asking the question which is the closest gas-station/post-office from some place.
Of course, O(n) can be done {Compare best-so-far value for each point}
But since our set of n points is constant, we would want some pre-processing so that the query time is reduced.
:) Interesting problem. Interesting solution.
I could give a vague but correct answer :)
You have n points on a 2-D plane. You have to execute the query, given a fresh point, which of these n points is closest to it. This is termed as gas-station problem or postman problem, as in asking the question which is the closest gas-station/post-office from some place.
Of course, O(n) can be done {Compare best-so-far value for each point}
But since our set of n points is constant, we would want some pre-processing so that the query time is reduced.
:) Interesting problem. Interesting solution.
The solution can be found on this wikipedia link:
ReplyDeletehttp://en.wikipedia.org/wiki/Nearest_neighbor_search
Thanks. There was a problem I was struggling with, being a non-CS student.
ReplyDeletehttp://www.spoj.pl/problems/RUNAWAY/