## Amazon Interview Question for Software Engineer / Developers

Country: India

Comment hidden because of low score. Click to expand.
0
of 0 vote

What is the meaning of k closest here ?
If its minimizing sum of pairwise distance then i think there is no polynomial time solution for this problem.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This looks like a clustering problem except that we need to find just one cluster of k closest elements rather than finding clusters for all elements (i.e., k-means clustering which is NP-hard). We can have an O(n^2 lgn) solution where for each point we compute its distance from other points. For each point, we have a list of n distances. We can sort each list in O(nlgn) and find k-1 smallest element and compare the sum of distances of these points with the already calculated minimum sum of distances and replace if needed.
Total time complexity = n * (O(n) + O(nlgn)) = O(n^2 lgn).
We can use the order statistics method to find k-1 smallest elements in each list, which makes the algorithm O(n^2).

Comment hidden because of low score. Click to expand.
0

This won't work. You are considering distance from a point to other k-1 points only for minimization rather you should minimize sum of pairwise distance.
e.g. When we find closest triplet of points then it means we have to find a triangle from set of points which has minimum perimeter i.e. we minimize AB+BC+CA not AB+BC.

Comment hidden because of low score. Click to expand.
0

That's a great point Cerberuz, and might make the problem more challenging. There could be two interpretations possible from the problem statement.

1. Find k closest points such that sum of distance among all the points is minimized.
2. Find a circle with smallest diameter that can contain k points (k closest points in as small space as possible).

I think the problem statement hints towards the second interpretation, so we need to find k elements such that the max distance between any two points is minimized (smallest diameter). However, even if we consider the second case, things are not easy. Minimizing the sum of distances of k-1 points from the center (kth point) does not ensure minimizing the diameter of the circle (which my earlier post assumed). The diameter represents the maximum distance between any two points in the sub-cluster. Let us see how can we minimize the diameter :
(i) Initially maintain an NxN matrix and compute distances of all points from each other O(n^2).
(ii) Take a point p1 and find k-1 closest elements to p1.O(n)
(iii) Maintain a heap of distances of all k points with each other. Build heap - O(k^2) time, O(k^2) space. Also find Sk for k points which is the sum of distances from the rest of k-1 points.
(iv) Get the next point (k+1) and find its maximum distance from any of the k points. If this maximum is greater than the max Heap, ignore this point and move to the next one. Else remove that point of the max Heap distance (each distance has two points associated with it) whose Sk is larger. Now remove all k distances of that point from the heap, and insert new k distances in the heap. O(klgk + klgk) = O(klgk).
(v) Repeat point (iv) for the rest of the points.
Total time complexity = O(n^2) + O(k^2 + nklgk) = O(n^2).

Comment hidden because of low score. Click to expand.
0
of 0 vote

Guys you can refer to Voronoi Diagrams diagrams for this problem!! its a very nice problem and the solution is not that easy!! :-(

Comment hidden because of low score. Click to expand.
-1
of 1 vote

-sort the points based on the distance between them and (0,0). Now start with two pointers: one = 0, and two = k; Compute the total distance between one and two , if its < min then store it in min. increment one and two , the new distance is D = previous_distance - distanceBetween(point[one-1], point[one]) + distanceBetween(point[two], point[two-1]); if distance < min store it in min and so on till two goes over the point.length.

Each time we store a new value in min we also store in 2 variables the values of "one" and "two" . At the end we return all the points betweeen one and two.

Comment hidden because of low score. Click to expand.
0

this won't work because two points with same distance from origin can be located one in first quadrant and one in third quadrant. This algo seems to imply that they will be closest to each other.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.