Microsoft Interview Question Software Engineer in Tests
Is there ONLY ONE line joining all points? Or are there (n-1) lines from every point to remaining (n-1) points?
I am not sure if this can be done in O(n).
The naive algorithm would be to compute midpoints for each combination in O(n^2), and see if they are integers.
O(n) is possible.
Another hint: You don't even have to compute any midpoints.
(Previous hint was: Dutch flag problem)
on second thoughts, if we have more than 4 coordinates we can be sure that atleast one pair exists which will have integer midpoint.
In case we have exactly 4 or less, we have to verify in linear time that we do not have the combination - (o,o),(o,e),(e,e,), (e,o) coordinates, (o = odd, e = even).
btw, I don't see what this has to do with the Dutch Flag problem. Perhaps my thinking is clouded :P
If the problem description is changed, so that we also have to identify the lines which has an integer mid point... How would one proceed then ?
Also @anonymous who posted the constant time algorithm, can you give a short description (or link ) of why is it that if we have more than 4 points, the mid point of atleast one line will be an integer ?
Would O(n^2) solution be acceptable, where midpoint for every combination of 2 points is found?
- Anonymous January 06, 2010