CareerCup

This is supposed to be the "Celebrity problem". But in that problem, the celebrity does not know anybody else. Here only if given that the head of the village does not know anybody else, the problem can be solved in O(n). I guess the interviewer got confused himself and missed a vital point of the question.

Either the interviewer mentioned the point that the head of the village doesn't know anybody else, or you forgot to write that over here.
Once we have this additional piece of information with us, then we can proceed along the following path.

Suppose, knows ( p1, p2 ) returns true, it means that p1 knows and so p1 can't be the head of the village as the head of the village knows no one else. So when we will call this function the next time, we call knows ( p2, p3 ).
If suppose the function had come out to be false, then p1 would have been a possible candidate for the head of the village. Also, it would have implied that p2 cant be the head, as p1 doesn't know him. In this case, we would have called knows ( p1 , p3 ).

The terminating condition, when we have evaluated all the people, knows ( p(n-1) , p(n) ) - if it returns true, then p(n) would be the lone candidate for the head post of the village otherwise p(n-1).

Now, take care that with whomsoever we are left in the end, is only a candidate, and not the real head. Because maybe that he would have known p1 or p2 or any earlier person. So we have to go through everyone once again to confirm if he was the head of the village or not.

Time Complexity : 2O(n) -> O(n)

vector<people> vec;

for (int i=1; i<n; i++)
{
if ( know (person[0], person[i]) is true)
add i to vec.
}

if (vec.size() == n - 1)
person[0] is head, end.

for ( int i=1; i<n; i++)
{
for (int j=0; j<vec.size(); j++ )
{
if ( know(person[i], vec[j] ) == false )
vec.erase(j);

if ( vec.size() == 0)
{
stop, vec[0] is head.
}
}
}

space O(n), time O(n) too.

Explain time cost:
assume average everyone know k person, like k=n/2.
so first loop, vec[] size will be k=n/2, and first person and second person both know will be n/4; three person common know will be n/8, and so on n/16, n/32.

so first loop, time use is n,
and second n/2.
third n/4.... so total is n + n/2 + n/4 + n/8..... = 2*n;
if k != n/2, let it k = n *q(q < 1 it's obvious.
so first loop tile is n,
second n*q,
third n*q*q.
so total = n + n*q + n*q*q + ... = n + n / (1 - q ) = n * ( 1 + 1 / (1-q)).

Small clarification? Does P know Q implies Q know P.

If P1 knows P2, this does not mean P2 knows P1.

maybe use something like a bool array all initially set to 1 then use a two pointer iteration. Start by pointing at [0] and [1], then move ptr2 until it doesn't recognize the person, this means both people ptr1 and ptr2 CANNOT be the leader so set the array elements to '0' and increment ptr1 and set ptr2 = ptr1+1

Therefore by the end of the iteration, ptr1 will be pointing at the leader.
worst case it makes O(n^2) comparison but average should be O(n) running is a rather linear fashion

Question: Does head of the village know few people/everyone/no persons? If the head of the village doesn't know anyone, this can be solved in O(n) for sure.

Using directed Graph....node which have most of the converging node is head of village and who have directed edge implies known condition ...this can be done in O(n)

As every one know who the village head is ,
head=p[0];
for(i=1; people p[i] in village;i++)
{
if(know(head,p[i]) == false)
{
i++;
head=p[i];
}
else
{
head=p[i];
}
}
System.out.println(head);

Complexity is O(n).. This algo will work..

Use a hashmap (<Person,Long>) person vs the number of people who know that person ..... Iterate to all persons while you keep updating the count