CareerCup

Use a linear-time selection algorithm to find the median point under the order of increasing x then y. The two halves resulting are both contained in convex regions weakly separated by a vertical line. (If the interviewer gets cranky about the boundary, rotate the line a fraction counterclockwise and make some noise about the imprecision of floating point arithmetic.)

find median in O(n) time for the x-coord / y-coord only.

Isn't it similar to the question "In a rectangular cake, a smaller rectangle of any size and orientation is cut out. Draw a single cut in the rest of the piece to cut in two halves."

Thus find the centroid of the batch of points by finding averages of x and y separately and then draw a line going through the calculated centroid and (1/2, 1/2).

Its classification problem you can use Linear Perceptron algorithm, where you have to solve the eq

How about sorting the points by their slopes wrt origin and then find the median? Would it give the slope of line that would divide the points in space equally?

sorting the points on x coordinate and then y coordinate ..and then finding the middle point i.e. median ..will a line passing through that point will divide all points in equal halves???