## Facebook Interview Question

Android Engineers**Country:**United States

**Interview Type:**In-Person

```
public class FindTheCelebrity {
public static void main(String[] args){
int[] input = new int[] {1,2,3,4,5,6};
FindTheCelebrity ftc = new FindTheCelebrity();
int left = 0;
int right = input.length-1;
while(left<right) {
if (ftc.knows(input[left], input[right])) {
left++;
} else{
right--;
}
}
int id = right;
for(int i=0; i<input.length; i++) {
if(i != right) {
if(!ftc.knows(input[i], input[right])) {
id = -1;
}
if(ftc.knows(input[right], input[i])){
id = -1;
}
}
}
System.out.println("Candidate " + right);
System.out.println(id == -1 ? -1 : input[id]);
}
public boolean knows(int a, int b) {
int[][] map = new int[][] {{0,1,0,1,0,1},
{0,0,0,0,0,0},
{0,1,0,0,0,1},
{0,1,0,1,0,1},
{0,1,0,0,1,0},
{0,1,0,0,0,0}};
return map[a-1][b-1] == 1;
}
}
```

Based on your question, the problem is asking us to find the celebrity given the person list and the person number. So, this can be done in O(N+N) = O(N) time where N = number of rows/cols. If this was problem was finding the celebrity given the matrix, then it would be a different problem. I present a solution in Python below.

I assume I am given an adjacency matrix. My solution in Python:

```
def determineCelebrity(peopleList, person):
# Scan the adjacency matrix
actualPersonIndex = person - 1
# Scan the cols and make sure everyone knows the person
for i in range(len(peopleList)):
if i != actualPersonIndex and peopleList[i][actualPersonIndex] != 1:
return False
# Make sure the celebrity knows no one else in the party
return all(x == 0 for x in peopleList[actualPersonIndex])
```

Test code:

```
celebrityMatrix = \
[
[0, 1, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 1],
[0, 1, 0, 1, 0, 1],
[0, 1, 0, 0, 1, 0],
[0, 1, 0, 0, 0, 0]
]
print(determineCelebrity(celebrityMatrix, 5)) # False
print(determineCelebrity(celebrityMatrix, 2)) # True
print(determineCelebrity(celebrityMatrix, 3)) # False
```

1. Given problem of finding whether the given person is celebrity or not can be solved in 0(n) just by checking row corresponding to that person should be all 0's, and column should be all 1's.

2. If the problem is to find the celebrity, then also complexity will be O(n), ie. starting from the first person, iterate it's row and find out the first 1 say at element i, all elements/persons before that one cannot be celebrity as first person does not know them, so direct skip to i, and start iterating its row from i+1 th position and keep skipping .

We could represent the persons as the array of Qubits:

- denis.zayats March 13, 201800: Celebrity - knows nobody in the room

01: No celebrity - knows only celebrity

10: No celebrity - knows everybody but no celebrity

11: No celebrity - knows the celebrity and everybody else

If we sort the array - then we know where to look for the celebrity.