## Yahoo Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

Let P_x be an array of the points sorted by their x-coordinates and P_y an array of the points sorted by their y-coordinates. Divide the plain into two regions e.g. using the median of the x-coordinates. Assume delta is the minimum distance among points entirely in one of the regions (determined by recursion). Now consider the vertical strip centered around the median having width 2 * delta. Let S_y be the sorted subset of P_y consisting of the points in the strip. For each element in S_y calculate its distance to the next 7 points in S_y.

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

what?

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

Refer kd tree.. for 2 dimensions.. It is useful for finding nearest neighbor for a set of given points.

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

This algorithm technique is called Divide and Conquer. You can find it in the textbook of Kleinberg and Tardos

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

The above answer is correct. I have added a answer of my own with links to explanation of algorithm - including a video lecture. Enjoy!

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

there is O(n^2) approach ,

int minD,X,Y;

simply.. for (x0,y0),traverse through the array.. and calculate the distance from formula
sqrt((y2-y1)^2+(x2-x1)^2),and keep on updating the values of minD and X,Y;

i'm sure there must be better sol. than this .

. pls do correct me if i'm wrong

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

for each point in x-y plane calculate the distance sqrt(x^2 + y^2) wrt to (0,0) and store them in array. sort the distances in this array. find the index in array with (next position - current position) is minimum. The points corresponding to this min distance are closest.

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

This may not be always correct. If we take a point (-x, -y), then the distance from origin of this point is exactly same as that of (x, y) but both these points are located in opposite coordinates.

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

BSS is correct. If you have points [(1, 1), (1, 2), (-1, -1)], and you sort on the distance from (0, 0), you get [(1, 1), (-1, -1), (1, 2)], and the your algorithm will not return the correct answer.

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

Question. Were you expected to write the code on the white board for this problem or just outlining the idea was enough?

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

Code on board.

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

Here is the solution using the divide & conquer method:
rosettacode.org/wiki/Closest-pair_problem/C

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

Approach can be solving using O(n^2) approach. calculate distance between every 2 points and find the minimum distance pair.

Or in divide and conquer we can use highest coordinates/2 and divide the plane and keep doing it until we reach a set where we just have 2 points.. for every region calculate dist(min) and dist with its neighboring cells. this might be complicated to implement though.

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

Let S={(x1,y1), (x2,y2), (x3,y3)....(xn,yn)}
find the mean (X,Y) of all the points say X=x1+x2+x3....xn/n and Y=y1+y2+y3...yn/n
we have actually found the centroid of the set of points. We now need to replace this imaginary point X,Y with a real point. For that:
find the minimum distance of this imaginary point X,Y with a point in the set S. That point is what we are looking for.

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

I dont think that will work. Your solution is based on the assumption that the closest pair of points will be nearest to centroid, which may not be true.

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

Brute-force checking every pair works and easy to implement but inefficient.

Divide and conquer dynamic approach is better. Details are below:

Look for Closest_pair_of_points_problem on Wiki page for quick overview.

Look for "Lecture -9 Divide And Conquer -IV Closest Pair" in youtube - this video lecture is entirely dedicated to explaining the algorithm.

Enjoy!

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

Calculate distance every point from origin.
Store this value in a new array. Sort this array. Now for every adjacent element find the the one with min(abs(a[i]-a[i+1]))
Timing complexity of this algorithm will be nlogn

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

Rather than just throwing an approach why not explain a bit? (Of course, there are well known divide and conquer algorithms...)

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.