CareerCup

Well, Graph will work but I feel like making extra structure for nodes will be a little complex.

How about using QuickSort Algo. choose a random person let say Pivot.
ask all others whether they know him or not. people who know him will come to left of him and people don't know him will come to right side.

after asking everyone if Pivot is the rightmost then he is the celebrity ortherwise follow the same steps for right side people of Pivot(Pivot will be excluded from the set because right side people don't know him so he can't be celebrity).

Running time will be same as solving it with Graph.

Step 1. Perform pair-wise comparison.
Total # comparison = N/2.
In every comparison
if isKnown(a , b) = true then
b could be a celebrity.
else
a could be celebrity.

Step 2. After step 1, there will be N/2 candidates for celebrity. Again Compare pair-wise among these N/2. Total # of comparison is = N/4. resulting in N/4 candidates.

Step 3. Similar to previous steps. Total compariosn is N/8 and results in N/8 candidate

4. Continue until one winner/celebrity comes up.

complexity : T(n) = N/2 + N/4 + N/8 + ...+1 = O(N)

Does it make sense?

sorry "Interviewer said we can use Graph I dont know how?" this was not for this question !

Understand the basic premise:
If A knows B ==> A can't be celebrity, since celebrity knows no one
If A Does not Knows B==> B can't be celebrity, coz Everyone knows the celebrity.

Hence if you ask this ques to every one successively, at each call to isKnown() you eliminate one person. You need to ask everyone once to get a final person who may or may not be celebrity. Lets say this person is X

Now if it is not guaranteed that thr is atleast one celebrity you need to ask every one again 1)Do you know X?
and ask X
2) Mr. X Do you know a[i]?
The answer of ques 1) should always be yes and ques 2) should always be NO.
If this succeeds then we get our celebrity in 3n comparisons.

Graph solution is:
Make all person as nodes. Now connect each from A->B s.t: A knows B. The celebrity will be one with indegree = n-1 and out degree =0

a knows b also means b knows a ??
if so, this problem can be solved in o(n).

isKnown(a,b), if it returns true that means... a is not celebrity (as a knows b) and if it returns false that means b is not celebrity ... it implies that after each call we can eliminate on candidate to be celebrity as there are n ppl, n-1 comparison will be needed....

int findcelebrity(int[] A){
	int i=0,j=0;
	int n = A.length;
	
	for(i=0; i<n;){
		for(j=i+1;j<n;j++){
			if(! isknown(a[j],a[i]){
				break;
			}
		}
		if(j==n){
			break;
		}
		else{
			i = j;
		}
	}
	return i;
}

class person
{
public int id;
public int[] knownPersonId;
public person(int id, int[] knownPersonId)
{
this.id = id;
this.knownPersonId = knownPersonId;
}
}
class FindCelebrity
{
public person findCelebrity(List<person> candidatesforCelebrity)
{
List<person> p = GetCelebrityCandidatePeople(candidatesforCelebrity);
if (p.Count == 1) return p[0];
else
return findCelebrity(p);
}

public List<person> GetCelebrityCandidatePeople(List<person> candidatesforCelebrity)
{
List<person> newcandidates = new List<person>();
for (int i = 0; i < candidatesforCelebrity.Count; i++)
{
for (int j = 0; j < candidatesforCelebrity.Count; j++)
{
if (IsKnow(candidatesforCelebrity[i], candidatesforCelebrity[j]))
{
//candidatesforCelebrity.Add(people[j]);
newcandidates.Add(candidatesforCelebrity[j]);

}
}
return newcandidates;
}

return newcandidates;
}

public Boolean IsKnow(person a, person b)
{
Boolean know= false;

for (int i = 0; i < a.knownPersonId.Length; i++)
{
if (a.knownPersonId[i] == b.id)
{
know = true;
return know;
//break;
}
}

if (!know)
{
return know;
}
return know;
}

public static void main()
{
List<person> persons= new List<person>();
persons.Add( new person(1, new int[] { 2,3,4 }));
persons.Add( new person(2, new int[] { 1,3,4 }));
persons.Add( new person(3, new int[] { 1,4 }));
persons.Add( new person(4, new int[] {}));
persons.Add( new person(5, new int[] { 2, 4 }));

FindCelebrity c = new FindCelebrity();
person p = c.findCelebrity(persons);

Console.Read();
}

}

set unknown = createSet(All the people)
set notCelebrity;

while(size(unknown)>1)
{
randomly choose two people from unknown (first,second);
if(knows(first,second))
{
  remove first from unknown and put into notCelebrity;
}
else
{
  if(knows(second,first))
  {
    remove second from unknown and put into not Celebrity;
  }
  else
  {
    // first doesn't know second and second doesn't know first
    remove first and second from unknown and put them into notCelebrity 
  }
}

}

By using adjacency list in directed graph, we can solve it

take a vertex say from 10 vertices and see the adjacent vertex(let it be 3 vertices)

now take only these 3 adjacent vertex and look for the vertex which doesnt have the adjacent vertex

this vertex is the celebrity
...

is there any other solution?