Give a set of points in a 2D plane. I need to pick two points such that, if I a drew a line connecting these points, it would divide the points into two equal halves. Was totally stumped by this question. Hadn't prepared for any geometrical questions. Any pointers to how to solve this efficiently. Edit: after being stumped about 5 min, trying to remember how to calculate the slope, the brute force approach I came up with - pick a pair, calculate the line equation y = mx + b - iterate through other points and substitute in the calculated line equation and solve for b. - based on the value of b, for each point , increment a two counters. - if the counters have same values, then we know we have divided it into equal halves. I was rejected. fyi.
Are you able to assume no 3 colinear? In that case you can pick any point you want, then test every other point to see which one divides them in half. Actually might need to have the fixed point be on the convex hull. If they can be colinear then it can't actually be solved when everything is on one line. Since it's only 2d checking which side a point lies on is very easy. EDIT: just take max X or Y coordinate point which will be guaranteed to be on the convex hull, then find median slope for an O(n) solution.
The interviewer said, assume a valid point set where there is a solution
For each point, quick-select the point with median angle. Stop when you get a unique median.
Sounds like this is the optimal solution to find the median in (average) O(N) time.
Fake Engineer is correct. You have to assume that no three-point-triplet can fall on the single line. Try every combination of two-point lines — the fixed point being the one at the left corner, and sorted by their slope — until you can find the line desired which is most likely in the middle
Don't get the divide points into two equal halves part. Isn't any line you draw can be divided in half anyway??? Are you asking that a 3rd point existing in the middle?
If you have 8 points. And you picked 2 points. 3 points should be on either side of the line
Are you using all 8 points to create the line?
Assume you have a set of N points with coordinate (x,y) and non of the pairs are colinear (makes the same cutting line): 1. pick a point 2. for any other point (out of N-1), you can make a line (with different position angle on the plane, i.e. angle relative to x-axis). So the goal is to find the point such that the angle is in the middle (median). 3. compute all the angles takes O(N). finding the median takes N log N (sorting the angle array) --- If you need to return all possible pairs, there should be some better way to do it...
Damn, interesting. There is no way I couldn't think of this, for sure
Use a modified convex Hull algorthm
Do you have a Math background? By any chance?
Nope, no math background. Just basic, 10th grad math studf, which I barely remember.
A bunch of folks are suggesting, to calculate median angle. Where does one get this idea from and what would you rate the difficulty of this question?
If you grab any point on the convex hull, that puts a linear order on the rest of the points because as you rotate a ray through that point, you will hit every other point in some order. The question is really easy if you have done any contest math. Idk where it fits on the LC scale since the algorithm is easy.
To OP: Two points define a line in 2D plane (m and b in your equation). If you are given one point, only the slope matters. Points on each side will have either bigger or small slope. So the median angle is the solution. I would rate this as LC easy to medium. It depends how far you can to the optimal solution for "finding median in unsorted array".
Yo just do regression and be like here u go man gl Hf I am a MLE
That doesn't work because you need to draw the line through two points.
I am not a MLE and was interviewing for a general software engineering role.