Amazon Interview Question
SDE-3sCountry: United States
Interview Type: In-Person
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.
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) ).
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.
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).
- ufukseng March 06, 2016Complexity 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.