Interview Questions: N closest points – 1

Recently I failed an interview with a company everybody knows. No, it wasn’t Google. No, not Microsoft either. (OK, maybe not everybody… ALMOST everybody). Anyway, I’m not saying.

The aim was to see how large US companies hire developers. It’s not a secret that the process differs a lot from what we have in Ukraine and therefore, their process is intimidating for us. So, I wanted to experience it.

Today I want to write about one interview task and several ways to solve it. Imagine you have N points on the plane, and they’re distributed according to a principle unknown to you. You have a base point, call it A, and your task is to find K points closest to A. How would you go about it? Think about the algorithms and data structures you would use.

The bruteforce way of doing it is as follows:

1) you create a “capped” array of closest points, size K, with their distances (can use a wrapper object containing both point and distance for it). In the beginning, all its element are nulls;
2) you go through all N points. For each point P you calculate the distance D between P and A (suppose you already have the method for this – you need not go into details of that implementation);
3) you run through the result array. If array has an empty slot (null item), you just put P in its place. If not but there’s an element with distance greater than D, you replace it with current point P and its distance from A.

This way, when all N points are processed, you are going to have a K-sized array of points with minimal distance from A.

The running time for this is O(N*K), because for each point among N you run through K points that are our current solution. It’s not bad when K is small. But if K is close to N, then our time is quadratic, which is not too good.

In the next post, I will continue writing about other ways to solve this problem.

Advertisements

About Maryna Cherniavska

I have productively spent 10+ years in IT industry, designing, developing, building and deploying desktop and web applications, designing database structures and otherwise proving that females have a place among software developers. And this is a good place.
This entry was posted in Uncategorized and tagged , . Bookmark the permalink.

One Response to Interview Questions: N closest points – 1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s