## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
24
of 26 vote

There can be at most one celebrity. Suppose A and B are both celebrities. A knows B by virtue of B's celebrity. But then A can't be a celebrity, by virtue of the rule that celebrities can't know anyone. Given that you have only celebrity, you can use a linear algorithm. Start with person 1, and they're the provisional celebrity. With person 2, see if either 2 doesn't know 1 or 1 knows 2, and if so, 1 is no longer a celebrity, and swap 1 and 2. For each new person, try to see if you can eliminate the celebrity's status with two simple checks, and then swap as needed.

After the first linear pass, you'll have a provisional celebrity, and then take another linear pass to verify that he really is a celebrity.

If there are no celebrities, then the second pass will be terminate fairly quickly.

Comment hidden because of low score. Click to expand.
0

Well said.
+1

Comment hidden because of low score. Click to expand.
-2

I don't know if that finds all the celebrities.

Comment hidden because of low score. Click to expand.
1
of 1 vote

@bunnybare: Amazing. You managed to skip right past the very first sentence.

Comment hidden because of low score. Click to expand.
0

If his answer is only for doing one celebrity, then the well said comment is unworthy.

If his answer is saying only one celebrity look up is possible given the linear time restriction, then I'll accept it.

Comment hidden because of low score. Click to expand.
0

@bunnybare: Only one celebrity is possible. Period. Irrespective of the algorithm time complexity required.

Comment hidden because of low score. Click to expand.
0

@bunnyabare, According to the rules, there can be at most one celebrity. Proof: Suppose A and B are both celebrities. A knows B by virtue of B's celebrity and the rule that a celebrity is known by everybody. But then A can't be a celebrity, by virtue of the rule that celebrities can't know anyone. Since any pair of celebrities leads to a contradiction of the rules, there can be at most one celebrity.

Comment hidden because of low score. Click to expand.
1
of 1 vote

implement showell30's algorithm with c++

``````//a[i][j] =1 denotes person i know person j
int Celebrity(vector<vector<int> >& a)
{
int candidate=0;
int i=1;
while(i < a.size())
{
if(!a[i][candidate] || a[candidate][i])
candidate=i;
i++;
}
//check
for(int i=0;i<a.size();i++)
{
if(i!=candidate && (!a[i][candidate] || a[candidate][i]))
return -1;//no celebrity exist
}
return candidate;
}``````

Comment hidden because of low score. Click to expand.
0

@duckling That's a nice refinement of my solution. As your code illustrates, there's no need to actually perform a swap; just change the value of candidate to be the new i.

Comment hidden because of low score. Click to expand.
0

@duckling : Nice efficient implementation.. but could you please explain why are you using 'or' instead of 'and' in the if-condition ? because if a[i][candidate]=1, then i can be no way in which i can be the next possible candidate.. plz verify.

Comment hidden because of low score. Click to expand.
0

@ss,i think showell30 explained it very clearly," see if either 2 doesn't know 1 or 1 knows 2". if person i doesn't know the candidate or the candidate knows person i,then the candidate is not a celebrity

Comment hidden because of low score. Click to expand.
0

@duckling One possible optimization here is that we try to eliminate candidates more aggressively. When you have i and candidate, call both KNOW(i, candidate) and KNOW(candidate, i). If both know each other or both don't know each other, then you've eliminated both, and you can advance candidate to be i+1 and i to be i+2. I haven't thought this all the way through, and it might not be worth the trouble, but if you can get all the bookkeeping right, it might eliminate the final linear pass and possibly speed up the first linear pass, especially if the KNOW() function call is expensive for some reason.

Comment hidden because of low score. Click to expand.
0

Here is a full JavaScript solutions, including structure, which represents the relations among people:

The relations:
We have people A, B, C, D, E. In the example below "A" knows B, C and E.

``````var relations = {
A: {
'B': 1,
'C': 1,
'E': 1
},
B: {
'A': 1,
'C': 1,
'D': 1
},
C: {},
D: {
'B': 1,
'C': 1,
'E': 1
},
E: {
'A': 1,
'C': 1
}
};``````

Here is the code:

``````find: function(array, relations) {
for (var i = 0, j = array.length - 1; array.length > 1;) {
if (this.isRelated(array[i], array[j], relations)) {
array.splice(i, 1);

--j;
}
else if (this.isRelated(array[j], array[i], relations)) {
array.splice(j--, 1);
}
else {
array.splice(j, 1);
array.splice(i, 1);

j -= 2;
}
}

if (array.length === 1) {
return array[0];
}
}``````

The answer is C. The time is O(n)

Comment hidden because of low score. Click to expand.
0

And here is isRelated function, forgot to paste it:

``````isRelated: function(source, dest, relations) {
var sourceRelations = relations[source];

return sourceRelations[dest];
}``````

Comment hidden because of low score. Click to expand.
0

@duckling - okk.. got it.. actually I was thinking the other way round..

Comment hidden because of low score. Click to expand.
1
of 1 vote

showell30@yahoo.com We can eliminate both A and B at the same time if they don't know each other. Since they cannot both be celebs, and neither is known, they must both be non-celebs. I'm not sure if you considered this but it isn't in your original description.

This reduces the runtime but not the complexity.

(Sweet solution BTW)

Comment hidden because of low score. Click to expand.
0

@Barry, thanks. If you scroll up in the comments, I respond to duckling about the optimization where you can eliminate A and B at the same time. As you point out, it doesn't reduce the overall complexity, which is why I'd be somewhat shy about trying to handle this case, unless I were really trying to squeeze out extra performance.

Comment hidden because of low score. Click to expand.
0

we can eliminate A and B if both knows or both doesnot know each other

Comment hidden because of low score. Click to expand.
0
of 0 vote

but at the first glance of the question, I was thinking about KNOWS(A,B) as some kind of comparative function, which can be used in sorting. and once we sort the list we would get the celebrities at one end, ofcourse there is no comparitive sort which can perform in linear time.

Comment hidden because of low score. Click to expand.
0

@goutham467, Instead of thinking of this as a sorting problem, think of it as a min-item-in-list problem. You can easily find the minimum element of an unsorted list in linear time, as long as the list has some sort of transitive ordering. The twist here is that you don't have a truly transitive ordering, since A can know B can know C can A. From the celebrity's standpoint, though, it doesn't really matter, because he or she is not allowed to be in any strange friendship cycles.

When you solve the traditional min-item-in-a-list problem, you have a provisional min and you keep trying to dethrone the provisional min as you iterate through the list. For the celebrity problem, it's the same algorithm with a slightly different mechanism to dethrone the provisional celebrity.

Comment hidden because of low score. Click to expand.
0

@showell
Thanks for a such a clear explanation."min-item-in-list" problem, how can I forgot a basic thing.
I am struggling with a question though, could you please comment on it, id=15489912

Comment hidden because of low score. Click to expand.
0

@goutham467 BTW here is a way to solve this that explicitly uses a comparison function with a generic algorithm:

``````def max_by(lst, cmp):
candidate = 0
for i in range(1, len(lst)):
if cmp(lst[candidate], lst[i]) > 0:
candidate = i
return lst[candidate]

def find_celebrity(lst):
# Simplifying assumption: assume the most famous
# person is indeed a celebrity.
return max_by(lst, famous_cmp)

def famous_cmp(i, j):
if know(i, j):
return 1
else:
return -1

def know(i, j):
# 40 is our celebrity
if i == 40:
return False
if j == 40:
return True
# For others, return something
# predictable
return  i == j + 10 or i == j - 10

print find_celebrity([10, 20, 30, 40, 50])``````

I omitted the extra step to fully verify celebrity status.

Comment hidden because of low score. Click to expand.
0

#include <stdio.h>
#include <stdlib.h>

int people;
extern int knows(int a, int b);

int celebrity() {
int celebrity, left = 1, right = people;
while (left < right) {
if (knows(left, right)) {
left++;
} else {
right--;
}
}
celebrity = left;
return celebrity;
}

int main(int argc, char *argv[]) {
printf("Number of people: ");
scanf("%d", &people);
printf("The celebrity is number %d\n", celebrity());
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

given a and b : check Knows(a,b) and Knows(b,a). If both result match eliminate both a and b to move forward as none are celebrity candidate , if only one is true say Knows(a,b) then eliminate a , b is still a candidate. get the next person in the list . On each step you exhaust at least one and hence linear time

Comment hidden because of low score. Click to expand.
0
of 0 vote

I too tried something on it. Please let me know for impvements. My thought of doing it is as follows:
1. Assume list is {A,B,C,D,E} and i=0,j=1 initially. Since only one celebrity or none exists, start with first two elements in list.
2. If knows() returns true, change i,j to j,j+1 else i,j+1.
3. Once j reaches last position, it means either i or j can be celebrities. So check which one is celebrity using normal for loop. It returns position of celebrity in list. It visits each element for 2 times hence O(2N)=O(N).

``````public int findCelebrity(char[] arr,i,j){
if(j==arr.length-1){
if(knows(i,j){
for(int k=0;k<n;k++){
if(knows(j,k)) return -1; //no celebrity
}
return j; //position of celebrity
}else{
for(int k=0;k<n;k++){
if(knows(i,k)) return -1; //no celebrity
}
return i; //position of celebrity
}
}
if(knows(i,j) return findCelebrity(arr,j,j++);
else return findCelebrity(arr,i,j++);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

geeksforgeeks . org /the-celebrity-problem/

Comment hidden because of low score. Click to expand.
0
of 0 vote

idk dude

Comment hidden because of low score. Click to expand.
0
of 0 vote

Code in C#.

``````public static int Do(int[] people)
{
int c = 0;
int i = 1;
while (i < people.Length)
{
x1 = KNOWS(people[c], people[i]);
x2 = KNOWS(people[i], people[c]);
if (x1 == x2)
c = ++i;
else if (x1 == 1)
c = i;
++i;
}
if (c == people.Length)
throw new Exception("There is no celebrity!");
return c;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem is similar to finding a universal sink in a graph in linear time. If A knows B then there is a edge between node A and node B.

Universal Sink is then a node with all incoming edges and no outgoing edges

You can also find the universal sink problem in Cormen et al and its solution in its solution manual.

Comment hidden because of low score. Click to expand.
0
of 0 vote

if cur don't know next one means: next one is not celebrity so i++;
if cur know next one means: cur is not celebrity so cur = i;
the people between i and cur don't known by cur so they are all not celebrity.

``````public Person findCelebrity(Person[] arr){
ine len = arr.length;
int cur = 0;
for(int i = 1; i < len ; i++){
if(Knows(arr[cur] , arr[i] ) == 1){
cur = i;
}
}
return arr[i];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

sorry the last line should be return arr[cur];
if cur don't know next one means: next one is not celebrity so i++;
if cur know next one means: cur is not celebrity so cur = i;
the people between i and cur don't known by cur so they are all not celebrity.

``````public Person findCelebrity(Person[] arr){
ine len = arr.length;
int cur = 0;
for(int i = 1; i < len ; i++){
if(Knows(arr[cur] , arr[i] ) == 1){
cur = i;
}
}
return arr[i];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Define two slots: A and B.

Assume N persons are numbered as 1 to N.

Steps are like this:

put #1 into slot A, #2 into slot B.
If Knows(A, B) == 1, means A knows B, so the person #1 can be removed from slot A, because #1 is not possible to be celebrity; else eliminate #2 in slot B, because it means A does not know B, so B is not possible to be celebrity.
Then put #3 into the empty slot.

Every round of comparison will remove the person either in slot A or B.
After N round of comparison, the one remaining in Slot A or B is the possible celebrity.

Call Knows() between the remaining guy and any other person, to check whether the remaining one is truly the celebrity.

Time complexity is N to 2N, thus O(N)

Comment hidden because of low score. Click to expand.
0

Time complexity is N to 3N. Final check takes up to 2N calling of KNOWS method.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I have a nice one:
1. Starting with the first Person in the array, scan until you find someone that A knows. If there is no such person, A must be the celebrity. Else, we find some person K. Continue scanning left to right in our array until you find someone K knows. Repeat this process until we reach the end of the array. Then the last person L we considered is our only candidate celebrity as at most one celebrity can exist and:

a. Our celebrity can't have occurred before L or else some previous person would have detected L in our pass.
b. The celebrity can't occur past L in the list or else we would have seen it in our pass from L->end of list.

These observations imply either L is the celebrity or there is no celebrity at all (which can occur if and only if L knows someone earlier in the list.) So we do a final scan of the list and check that L knows nobody.

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

Better:

If A knows B, then A can’t be celebrity. Discard A, and B may be celebrity.
If A doesn’t know B, then B can’t be celebrity. Discard B, and A may be celebrity.

Comment hidden because of low score. Click to expand.
0

Although it's overkill for this problem, you can model this like an NCAA March Madness single-elimination, which runs in linear time. For each "game," see if A knows B. If A knows B, then B wins, else A wins. After 63 games, you will have a winner that is least as "famous" as all other contenders. To verify that they're actually a celebrity, you'd still need to check the winner's relationship to the 63 losers in another linear pass.

Comment hidden because of low score. Click to expand.
0

I like the NCAA solution better. Here's the semi-solution with modification to Integer.

``````public static Integer getMax(List<Integer> list)
{

while (queue.size() > 1)
{
while (!queue.isEmpty())
{
Integer first = queue.poll();
Integer second = queue.poll();

if (second != null)
{
que.add(first > second ? first : second);
}
else
{
}
}
que.clear();
}

return queue.poll();
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.