Stepan
BAN USER
Comments (4)
Reputation 5
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
-1
of 1 vote
1) Sort the points by one coordinate first and store in array or list: o(n * log n)
2) Traverse through resulting array eliminating all points which are apart more than distance X in chosen coordinate from their neighbours and performing full distance check on others: O(n)
Therefore resulting complexity is O(n * logn + n) = O(n * logn)
----
Could this be a solution?
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Reading 'Given a n-ary tree' and then seeing 'O(log n)' does not make sense. I presume it must have been 'O(log m)' where m is number of nodes in the tree.
- Stepan December 24, 2008Prashi, could you clarify, please.