CareerCup

KD Trees used in Nearest Neighbor classification algorithm.

HashMap resturants= [r1,(x1,y1) : r2,(x2,y2) ....... rn,(xn,yn)] key=resturantID,value=Location
HashMap cusomters= [c1,(x1,y1) : c2,(x2,y2) ....... cn,(xn,yn)] key=customerID,value=Location
HashMap finalAnswer = [customerID, ArrayList<Location> nearestlocation]
nearestlocation.add(DistantLocation), DistantLocation.x=9999999, DistantLocation.y=99999999 //some high number
int distancef = 9999999;

forEach ( customer in customers )
forEach ( resturant in resturants)
if(abs(customer.x-resturant.x)+abs(customer.y-resturant.y)<distancef) {
//x,y on each xn,yn --- customer.x = customer.getLocation().x and so on, nearestlocation.add(nearestlocation.get(nearestlocation.size()),nearestlocation.size()+1);
nearestlocation.add(resturant.getLocation(),0);
distancef=abs(customer.x-resturant.x)+abs(customer.y-resturant.y);
}
else nearestlocation.add(resturant.getLocation(),nearestlocation.size()+1);

// now nearestlocation contains sorted List of Locations object....pick first K locations and return that much List

Create a grid i.e divide the complete area into squares and note the restaurants in the square. for any customer in a given square, find out the nearest restaurants by looking up the nearest restaurants in that square and the adjacent squares. can implement grid as 2d array with each element pointing to a linked list containing restaurants. implement a k-element linked list for closest restaurants to customers. can create smaller grids for areas with lot of restaurants with the 2d array pointer pointing to another smaller 2d array which in turn points to restaurants

another idea similar to previous one is to create a grid but keep info for restaurants closest to each corner. similar implementation- 2d array of pointers and linked list. but in this case have to only lookup to restaurants closest to the 4 corners of the square the customer is i. if there aren't enough restaurants in these two boxes, check out the squares in a spiral starting with adjacent squares. same case for previous algo.