## Microsoft Interview Question for Software Engineer in Tests

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

Would O(n^2) solution be acceptable, where midpoint for every combination of 2 points is found?

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

O(n) is possible.

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

Is there ONLY ONE line joining all points? Or are there (n-1) lines from every point to remaining (n-1) points?

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

No. n random points, each co-ordinate being an integer.

I will give a hint: Dutch flag problem.

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

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.

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

O(n) is possible.

Another hint: You don't even have to compute any midpoints.

(Previous hint was: Dutch flag problem)

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

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).

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

btw, I don't see what this has to do with the Dutch Flag problem. Perhaps my thinking is clouded :P

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

Forget dutch flag.

The constant time algo you gave is excellent!

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

Brilliant Solution!

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

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 ?

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.