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.