CareerCup

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.

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.

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

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.

Use knn algorithm