Find the celebrity, Facebook Inteveriew question
Published: 2020-05-27 14:43:13

Question: Suppose you are at a party with "n" people and among them, there may exist one celebrity. The definition of a celebrity is that all the people at the party know him/her but he/she does not know any of them. 

You want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information about whether A knows B. You need to find out the celebrity.

Since you don't want to disturb everyone, you want to ask as few questions as possible.

We're given a function 
```javascript 
knows(a,b) // returns 1 if a knows b or 0.
```

<h2>Brute Force O(n^2)</h2>

Brute Force approach would be to ask everyone, so for a person A we ask if they know everyone else at the party and we do this for each and every guest and on based upon that, we find whos the celebrity. 

To implement this, we create two arrays, 

```javascript
know[n], doesntKnow[n]
``` 
of size n each. 

For each person A, we will perform a call,
```javascript 
   knows(A,B)
```

If it returns 1, that means A knows B, so we can do :  
```javascript
   know[A] += knows(A,B);             // if A knows B then we add 1 to knows[A]
   doesntKnow[B] += knows(A,b);       // if B doesn't know A then we add 0 to doesntKnow[B] or else we add 1
```
At the, if a guest know[X] = 0 and doestKnow[X] = n-1, we know that X is the celebrity. 

Converting it to code: 

```javascript 
let arr = [[0,0,0,1,0],
           [0,0,0,1,0],
           [0,0,0,1,0],
           [0,0,0,0,0],
           [0,0,0,1,0]];

function knows(i,j){
  return arr[i][j];
}

function celebrity(n){
  let know = new Array(n).fill(0);
  let doesntKnow = new Array(n).fill(0);

  for(let i=0;i<n;i++){
    for(let j=0;j<n;j++){
      know[j] += knows(i,j);
      doesntKnow[i] += knows(i,j);
    }
  }

  for(let i=0;i<n;i++){
    if(know[i] == n-1 && doesntKnow[i] == 0){
      return i;
    }
  }
  return -1;
}           
```

Now, let's think about optimizing this. 

All we care about is whether person A knows person B. If person A knows B then A can't be the celebrity or if B knows person A then B can't be the celebrity since B doesn't know anyone.

Based on this simple observation, let's optimize our solution. 
First : We shall eliminate those who know someone. 
Second : When we get to a point where there's only one person remaining we check if that person knows anyone else ? If not then that person is the celebrity. 

So how shall we eliminate those who know someone else? 
We shall maintain two pointers, let A : 0 and B : N. then we ask know(A,B), 
if it returns true then we move pointer A : 1, or else we move pointer B : N-1.

To understand it clearly see this gif : 
<img src="https://media.giphy.com/media/hQEdQVEZbWDXkUCgyb/200w_d.gif" />

After this we reach will reach check if the Pointer A, is really indeed a celebrity by checking 
1> Celebrity doesn't know anyone else :
```javascript
   for i = 0 -> N; 
   knows(A,i)  // should be false 
```
2> Everyone else knows the celebrity :
```javascript
   for i = 0 -> N;
   knows(i,A) // should be true
```

Putting it all together : 
```javascript
  let arr = [[0,1,0,1,0],
            [1,0,0,1,0],
            [0,0,0,0,0],
            [0,0,0,0,0],
            [0,1,0,1,0]];

  function knows(i,j){
    return arr[i][j];
  }

  function celebrity(n){
    
    let A = 0;
    let B = n-1;

    while(A<B){
      if(knows(A,B)){
        A++;
      }else{
        B--;
      }
    }

    for(let i=0;i<n;i++){
      if( i!=A && (knows(A,i) || !knows(i,A))){
        return -1;
      }
    }

    return A;
  }           
```

I hope you liked my explanation :) 

Github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/FindCelebrity.js