Monday, 16 July 2012

Search for Celebrity

Consider a party of n people. Consider a matrix A (nXn) with each entry being either 0 or 1. 
A(ij) = 1 if the ith person knows jth person in party
A(ij) = 0 if the ith person doesn't know jth person in party
Also note that A(ij) is not always equal to A(ji)


A celebrity is the one who doesn't know anybody but everybody knows him. 
Can you find the celebrity in O(n).

Disclaimer: This was again asked in GSach Interview which I was unable to answer. I guess you can try using directed graphs for solving this but not sure.

7 comments:

  1. one thing we must notice that there can not be more than one celebrity, if we have then they know each other(as celebrity is known by all other) and they don't know each other(as celebrity doesn't know anyone)... so contradiction...
    now we can proceed this way... we have 1-2-3-...-n people in a party... start comparing 1 & 2 (compare A(12) and A(21) ), we have either none of them as celebrity (if A(12)=A(21)=0 or 1) or one of them can be celebrity (1 can be celeb if A(21)=1, A(12)=0, ow 2 can be celeb)... suppose 1 can be celeb.. then compare 1 & 3 and find next who can be celeb.... thus at last either we will find no one as celeb. or one person k can be celeb... now check whether k is celeb. or not by checking all A(ik)and A(kj)for all i&j (as we have missed some checking in prev. process and we just found out if anyone can be celeb. or not)... thus we have our celebrity in O(n) time (actually we need 2*(n-1)+2*(n-1) checking only)...

    ReplyDelete
  2. How about A(12)= A(21)=1 and both 1&2 not being celebrity but knowing each other

    ReplyDelete
  3. then proceed to next person 3&4... as we are only finding celebrity, then we don't have to bother about 1&2 ....

    ReplyDelete
  4. @rik : can u be more precise. from your description, it doesn't seems to be O(n)

    ReplyDelete
  5. Algorithm(n people):
    pair the people in n/2 groups
    possiblePeople = empty
    if both of them no each other, drop them
    else the one who doesn't know the other --> add him to possible people
    return Algorithm(possiblePeople)

    mainMethod:
    person = Algorithm(n people)
    celebrityCheck(person) // he might not be a celebrity

    Since everybody knows a celebrity and celebrity doesn't know anyone, the size of the recursion will be reduced by atleast half. therefore, T(n) = T(n/2) + O(n) --> T(n) = O(n)

    ReplyDelete
  6. Algo :
    Let the people be i1,i2..in.
    Run a progressive check
    compare i1 with i2 :
    if(A(i1,i2)==1 && A(i2,i1)==0)
    {keep i1,i2}
    else
    {drop i2}
    ....
    if i2 is dropped now check i1 and i3.And so on .
    At any point if we encounter a celebrity then he/she is not gonna get dropped + any other person encountered after him will get dropped .
    So the last person remaining in the array is the celebrity .
    Since the worst case is when celebrity is at index N,the worst case has N-1 comparisons .So O(n)time is reqd.
    ---------
    Demo:
    let the persons be
    i1,i2 ,i3,C,i5
    -i1 knows i2,i2 doesnt know i1,i2 and i3 dont know each oder.
    -other relationships can be laid as reqd.
    check i1,i2(condtion satisfied so we dnt drop any)
    check i2,i3(condition not satisfied,drop i3)
    check i2 C(condn satisfied dont drop any)
    check C i4(condn not satisfied drop i4)
    Array:i1,i2,C<---celebrity

    ReplyDelete
  7. if there is no celebrity i will run a check whether evrybody knows him and he know sno body,it will tkae O(n) time only.
    In the demo i have mistyped i5 as i4 .

    ReplyDelete