0

I am having trouble with a coding question that I found practicing for a interview:

A scatter graph of points on a page, draw two horizontal lines (these lines are parallel) across the page such that the perpendicular y distance to a line from all points is minimized. Count the total distance from each point to the line that is closest (Only count the distance from each point to the closest line, ignore the longer distance, when the distance is the same, pick either one). Describe an algorithm for finding these two lines.

My approach:

I have considered brute forcing this by checking all possibilities in intervals of 1 starting from the highest y axis ending with the lowest y axis of the points, but this is perhaps not the most optimal way. I have also considered splitting the points into two groups based on y axis, however there are some edge cases that will fail.

Does anyone know a more efficient way to do this?

Improve this question
9
  • 2
    see Why do interview questions make poor Software Engineering.SE questions
    – gnat
    Commented Nov 27, 2018 at 5:57
  • 1
    "all possibilities in intervals of 1"? Why 1? Aren't the coordinates supposed to be double values?
    – Doc Brown
    Commented Nov 27, 2018 at 6:32
  • @DocBrown The sought lines are horizontal. This is a 1D problem.
    – Nick Alexeev
    Commented Nov 27, 2018 at 6:48
  • 1
    @NickAlexeev: obviously, but that does not make it a discrete integer problem.
    – Doc Brown
    Commented Nov 27, 2018 at 6:49
  • @DocBrown It is a discrete problem because there is an integer number of points to consider. This can be seen as a clustering problem; each point either belongs to cluster A or B → I can enumerate all permissible clusterings, giving rise to Kain's O(n log n) solution. The non-discrete version would be if I had point densities rather than discrete points, but that would be extremely hard unless the density has an analytical form that's once differentiable.
    – amon
    Commented Nov 27, 2018 at 14:39

1 Answer 1

Reset to default
1

Yes there is a much more efficient way to do this. Off the cuff I can write an O(N log(N)) algorithm. As this is a test question, the point is not solving it it is the process of solving.

The problem you seem to have is a perspective issue. Try reducing the size of the problem down.

  • How would you solve this for two points?
  • How would you solve this for three points? four points? five points?
  • Given that you've already solved this problem for K points, can you solve it for K+1 points?
  • Does that K+1 point need to have certain properties?
  • Would receiving the points in a particular order make it easier to solve?
  • Would considering the points one, two, three at a time make it easier to solve?
  • How does each line behave as a point is added?
  • Can you take advantage of that behaviour?

At this point you'll probably have worked out if and how to sort the points, how they are picked, and how many points you'll consider at once. You will know how to update the solution for the next point, and you'll know that your answer is correct after having considered all points.

Improve this answer
2
  • The idea of solving problems this by induction is not bad in general. However, I doubt it will work well for this specific problem (but maybe I am just to blind to see it).
    – Doc Brown
    Commented Nov 27, 2018 at 6:52
  • There is a way to construct this by induction take some time and think it through. Perhaps find a copy of Computational Geometry - Algorithms and Applications
    – Kain0_0
    Commented Nov 27, 2018 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.