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.

- showell30@yahoo.com February 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well said.
+1

- Anonymous February 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

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

- bunnybare February 27, 2013 | Flag
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.

- Anonymous February 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- bunnybare February 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- showell30@yahoo.com February 28, 2013 | Flag
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;
}

- duckling February 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- showell30@yahoo.com February 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- ss February 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- duckling February 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- showell30@yahoo.com February 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Ed February 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

And here is isRelated function, forgot to paste it:

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

    return sourceRelations[dest];
}

- Ed February 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ss March 12, 2013 | Flag
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)

- Barry Fruitman March 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- showell30@yahoo.com March 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- mani 4m sklm June 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Showell nice answer.
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.

- goutham467 February 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- showell30@yahoo.com February 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- goutham467 February 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- showell30@yahoo.com February 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#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;
}

- talk2kush March 07, 2013 | Flag
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

- Anonymous March 04, 2013 | Flag Reply
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++);
}

- ajit March 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

geeksforgeeks . org /the-celebrity-problem/

- jimmy514in March 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

idk dude

- Henry Vo. April 26, 2013 | Flag Reply
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;
    }

- Viacheslav August 24, 2013 | Flag Reply
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.

- lodhi.harshil August 31, 2013 | Flag Reply
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];
  }

- Anonymous October 05, 2013 | Flag Reply
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];
  }

- Anonymous October 05, 2013 | Flag Reply
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)

- evi April 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- evi April 14, 2015 | Flag
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.

- trevorvanloon April 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your check doesn't work.

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.

- bunnybare February 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- showell30@yahoo.com February 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

public static Integer getMax(List<Integer> list)
    {
	Queue<Integer> queue = new LinkedList<Integer>(list);
	Queue<Integer> que = new LinkedList<Integer>();

	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.add(first);
		}
	    }
	    queue.addAll(que);
	    que.clear();
	}
	
	return queue.poll();
    }

- Anonymous June 16, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More