Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Nov 25, 2009

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.

2 comments:

  1. Thanks. There was a problem I was struggling with, being a non-CS student.
    http://www.spoj.pl/problems/RUNAWAY/

    ReplyDelete