Microsoft OA Question

Revision en1, by Lamentis, 2022-08-20 11:46:39

Q) Given a 2D array of size n that represents the x and y coordinates([x,y]), find the number of collinear triplets.If collinear triplets>1e9, then return -1.

N<=1000

----------------------------------------------- This question came in yesterday's Microsoft OA. I was not able to come up with an efficient solution and ultimately wrote an O(n^3) solution using the idea that the area of triangle formed by three collinear points is 0.

Please suggest an efficient solution.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Lamentis 2022-08-20 11:46:39 506 Initial revision (published)