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 2D plane. You have to execute the query, given a fresh point, which of these n points is closest to it. This is termed as gasstation problem or postman problem, as in asking the question which is the closest gasstation/postoffice from some place.
Of course, O(n) can be done {Compare bestsofar value for each point}
But since our set of n points is constant, we would want some preprocessing so that the query time is reduced.
:) Interesting problem. Interesting solution.
Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)
Subscribe to:
Post Comments (Atom)
Fraction Brainteaser
Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this art...

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tos...

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...
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 nonCS student.
ReplyDeletehttp://www.spoj.pl/problems/RUNAWAY/