## Amazon Interview Question for SDE-3s

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 4 vote

An easier and intuitive solution would be to have max heap of distances. Its size needs to be limited with k. Given point (a,b) to look for k closest cities, for each (x,y) in the coordinates list, find the distance between (a,b) and (x,y). If distance is smaller than the top element of max heap, throw the max element away and put the new distance into the max heap. At the end of scanning the list, heap will have the closest points to the point (a,b).

Complexity of the algorithm above depends on the input and the size of k.

Another way is to do what quick sort does. Find the pivot with a custom comparison that is distance of two coordinates. Keep finding pivot recursively on the range it resides until the pivot is k.

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

k-d binary tree are the suitable data structure to keep the geographical co-ordinates in k-dimensional plane. where k is 2,3.....n. for k=1 we have generic binary tree data structure.

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

You can't find closest pair easily with k-d binary tree. It is good for look-up.

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

We could have process the raw data of coordinates, then using addtional lookup tables of cities and base latitude and longitude and store this in a Maps(Map1 <latitude longitude> <List of zones>, Map2<zones><list of cities along with latitude and longitude>).
Now given a coordinate we can qickly find out the zone and from map1 and map2 find out the cities that are closest.

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

First create a HashMap of point object and distances, once the map is ready sort the map based on the distance of the map (value of the map) using comparator. But to sort this map, convert it into a list, sort the list. As this list is sorted, retrieve all the top 100 points from the list. Complexity of this is O(nlogn) as the sort takes this much time, inserting and retrieving takes linear time( O(n) ).

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

In java, create a new class to store these coordinates and implement comparable interface
class and override equals and compareTo
Class Location{
int lat;
int long;
String name;
int relativeDistance}

if(x,y) are coordinates of any point and (a.b) the coordinates of our pivot, then calculate relative distance as follows:
d1 = x-a
if(d1 > 180) d1 = 360 - d1
d2 = y -b
if(d2 > 180) d2 = 360 - d2
Calculate relative distance as Math.pow(Math.pow(d1,2)+Math.pow(d2,2), 0.5)

Use relativeDistance in the equals and compareTo method for comparison. Now insert the entries into a TreeMap, the complexity will be o(log(n!)). Iterate over first k entries to get your k closest points.

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

Use knn algorithm

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.