Wednesday, April 2, 2014

Finding the celebrity group

Problem
Given the group of people in party find the group of celebrities
Suppose we have N people and there might be a group of celebrities inside.
Every person knows every celebrity and every celebrity knows only every other celebrity.
If you are given the function of `Knows(x,y)` which returns true if x knows y, false otherwise. identify the group of celebrities.
This problem is to identify a group of celebrities, and it is not identifying the only celebrity among the people, such as http://k2code.blogspot.in/2014/04/the-celebrity-problem.html.

Solution
Method 1 - Brute force
Using brute force is easy. I can construct all possible sub-sequences of N people and filter them with the condition (everyone knows every celebrity and every celebrity knows only other celebrity)..
Also I know there must be only one celebrity group or none.

Method 2 - Linear solution
```int find_a_celebrity()
{
int C = 0; // C is a potential celebrity
for( int i=0 ; i<N ; ++i )
if( !knows(i,C) ) // C is not a celebrity nor are all j<i, but i might be.
C = i;
for( int i=0 ; i<N ; ++i ) // Loop a second time to check everyone knows C.
if( !knows(i,C) ) return -1;
return C;
}

int C = find_a_celebrity();
```

If C==-1 then there are no celebrities. Otherwise the set { y | knows(C,y) } is the set of all celebrities. All together, this took at most 3 iterations through all N people, so this is discovered in time O(N).

References
http://stackoverflow.com/questions/20983260/linear-algorithm-for-finding-the-celebrity-group-not-single-celebrity