## Adobe Interview Question for Software Engineer / Developers

• 0

Country: India

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

from the given n points, find mean point i.e (x1 +x2+.. xn)/n, (y1+y2+.. yn)/n
Now whichever point is closest to the mean point is the point we are looking for.
O(N)

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

this can not be true

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

The idea is right that it should lie somewhere in between all these points. To do this we might do it like this sort the coordinates based on x coordinate and find the middle coordinate then sort the coordinates based in y coordinate and find the middle co ordinates one among these two should be the Point P. O(nlogn).

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

This solution is not right. Burden of proof is on the guy proposing the solution.

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

I doubt that the OP's solution is correct. Agreed that the proposer of the solution should offer a proof. This algorithm would be correct for a variant of this problem. Namely, if the distance metric were to be the Manhattan (street block, e.g. |x2 - x1| + |y2 - y1|) distance. I could prove that, but I'm not going to bother since that's not the question. Even then, this is only true when there's no requirement to pick any of the N points, but when you can pick any point on the grid.

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

@Eugene. In case of Manhattan, the solution would still be wrong.

In manhattan you need the median, not the mean.

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

By the way, was it expected that you beat O(n^2)? If your interviewer was asking this question just to see you write some code, maybe they just expected the straightforward O(n^2) approach.

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

True, even in the Manhattan version it would be the median and not the mean. I didn't pay very close attention when I read the proposed answer.

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

I think the above solution is right. Mean point by definition is a point whose sum of deviation from all the points is minimum and so from the given list, the point closest to the mean point is the answer.

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

No. Lookup Fermat point for the case of three points. That is not necessarily the median.

Now if you are given four points as three points A,B,C, and their fermat point D, then D is answer which is not the median.

Ridiculousness abounds on this site. People just make claims without any hint of trying to justify it.

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

Of course, a proof is still required to show that D, is not the closest point to the median :-)

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

The anonymous of Fermat point is right. The wiki has an example supporting his/her statement.

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

We can use the minimal length spanning tree concept. First to find minimal length to connect all the points on the coordinate then we can find a average point in them to to find minimum distance.

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

@Umesh: That doesn't make any sense to me. Want to explain further?

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

that's called geometric median, well-known problem in statistics, only approximate algorithms exist..

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

correction: unless we go for O(n^2) solution of course ))

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

In the above solution, The concept is right, but it doesn't always work.

Consider a GRID with both +ve and -ve points . and the above formula fails to work for such inputs.

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

ha, I think my answer is a little off, maybe a rolling mean would prove more useful. I saw the median has cases where it fails.

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

This is Geometric Median

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

My approach would be.
Given all the co-ordinates..

1) Pick minimum absolute values of X call it X1
2) Pick Maximum absolute values of X call it X2
3) Pick minimum absolute values of Y call it Y1
4) Pick Maximum absolute values of Y call it Y2

The source P should be very close to (X1 + X2)/2 , (Y1 + Y2)/2

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

This will not work, consider having many values close to X2 and only one value for X1 and one value of X near the middle... The correct value would be one close to X2 since the sum of all their distances is minimal...

e.x. : x values: 1,15,30,31,32, 29, 33.... according to your method, source p should be ~17 --> (33+1)/2, where in actuality it will be closer to the median ~31 since the sum of all the distances to that point is minimal.

I recommend the above comment where the MEDIAN values of X and Y should be considered closest to the point

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

Rdo, you are right, the above solution works for even distribution of points. without any distant point from a cluster.

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

After you have a point (median x, median y) i suggest iterating out from the middle of the sorted x (or sorted y) list. Or iterate in from both ends, and keep track of the smallest distance... and that will be the point p. Run-time complexity: sort x= O(nlogn) sort y= O(nlogn) and finally iterate through = O(n/2) therefore overall complexity O(nlogn)

Can anyone comment on the correctness of the complexity analysis?

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

I would, but I need a more complete and more clear description of the algorithm.

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

I just took the analysis from sort(vector.begin(), vector.end()) being executed twice then doing a two pointer iteration to find the minimum distance in the array. basically:

sort x values in array, set median x
sort y values in array, set median y

set ptr1 to index 0 (doesn't matter what sorting the array is since we compare each value once)
set ptr2 to index n

iterate pointers ptr1++ and ptr2-- until they meet and just keep track of the minimum distance from point(median x, median y)

the min point is the answer

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

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

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

I'm just kidding. It's just the choice of "feel" when describing an answer is not the choice of words I'd use.

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

@rdo ... I cannot understand what are trying to do with the pointers .. are you calculating the min distance??

What i think is .. we had to find the point from where the distance is minimum to every other given point .. which should be the Median.

Please elaborate if you are doing anything else ?

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

My proposal is : If we see in an array , median will be the element having smallest distance with all other elements.

So, we can take median of all Xi's and all Yi's separately , then check for the min. pair b/w (Xm , Yi) and (Xj,Ym) elements.

What say?

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

That only works if the distance metric is Manhattan distance. Here it seems it's Euclidean distance.

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

en.wikipedia.org/wiki/Centroid

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

I think it is not the Geometric Median ... the solution should be Arithmatic Median.

hxxp://math.stackexchange.com/questions/131981/how-to-calculate-geometric-median-of-some-points-in-x-y-plane

My approach for the problem would be to create a 2D boolean array, arr[x,y] where x and y are the largest values available in the input. and then mark the coordinates as TRUE where there exists a 'Point'.
Now, calculate the median of x-axis and y-axis separately. That should give the answer. (It is not necessary that the answer will be unique).

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

I forgot to explain the calculation of median.

the median is the middle number of the list.

if the input is
(2,2)
(2,4)
(3,3)
(4,2)
(4,4)

then the calculation of the median can be done by making a list of x-axis and y-axis separately and sort them..
x-axis : 2,2,3,4,4
y-axis : 2,2,3,4,4

the median will be the middle of the two lists. i.e (3,3).

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.