Microsoft Interview Question
Software Engineer / DevelopersTeam: MS Office Platform
Country: India
Interview Type: In-Person
3-d also follows same logic. Whereas for 2-D we will have x-y slope, for 3-D we can have x-y slope and y-z slope. O(k*n^2) complexity for kth dimension. Is there are better algo?
Say points are like this in 2-D, and pick x1 to find the slope with respect to other points. Now i see that x2 and x3 are colinear with x1, but there exists one more set y1 y2 y3 y4 which has more colinear points. So shouldn't we maintain a count map with respect to all points and return the maximum ?
x1 x2 x3
y1 y2 y3 y4
Points will be collinear if there slop will be same. Take origin and calculate slop of all points with respect to origin. Now problem reduces to find maximum frequent words. that can be done in simple O(n) with using couting variable.
Similarly for 3d this can be extend, here we need to take 2 angle to define a line.
Two points are colinear if they
- Sugarcane_farmer May 20, 20141) pass through same point.
2) Have same slope.
pick one point and calculate slope of each point w.r.t this point. Store all these in an array. Sort this array. find duplicates. (there will be different sets). each set will be of collinear points. (Since we have calculated this wrt one point the first condition is prechecked)
Second part is tough man