## Directi Interview Question for SDE1s

Country: India
Interview Type: Written Test

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

KD Trees used in Nearest Neighbor classification algorithm.

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

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);
distancef=abs(customer.x-resturant.x)+abs(customer.y-resturant.y);
}

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

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

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

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

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.

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.

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.