@Piyush. The simplest algorithm is to sort the array entries by the
number. Then the three friends of each person will be the closest
three of the set comprising the closest three on the left and the
closest three on the right. This algorithm has running time O(n log
n).
Usually, we regard "being a friend" as a transitive relationship: if A
is a friend of B, then B also is a friend of A. However, the
definition of friend in this problem is non-transitive. Consider {A:1,
B:5, C:6, D:7, E:8} Then B, C, and D are friends of A, but A is not a
friend of any of them.
Dave
On May 16, 4:31 pm, Piyush Sinha <[email protected]> wrote:
> Say you have an array containing information regarding n people. Each person
> is
> described using a string (their name) and a number (their position
> along a number
> line). Each person has three friends, which are the three people whose number
> is
> nearest their own. Describe an algorithm to identify each person's
> three friends.
> --
> *Piyush Sinha*
> *IIIT, Allahabad*
> *+91-8792136657*
> *+91-7483122727*
> *https://www.facebook.com/profile.php?id=100000655377926*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
