Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
5
of 7 vote

If we make the assumption about there is always one and only one celebrity in the group,

c = -1; // celebrity index
   for i in 0..n-1
     if c == -1
       c = 0
     else 
       if knows(a[c], a[i]) && !knows(a[i], a[c])
         c = i

Its almost like finding the max from a list, by assuming the first element as the max and as you are iterating updating the current max.

- Anonymous January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

By definition there can be only one celebrity.

- Anonymous January 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

There can't be more than one but there can be no celebrity at all. In this case the solution breaks.

However, if we can't assume there is exactly one, we can add another O(n) loop at the end, checking whether the person we found is indeed a celebrity. It they are not, there simply isn't one in the set (otherwise we'd find them).

Still works in O(n).

- black.marvolo February 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

In the end we need to verify if the celebrity even exists or not. (Consider a scenario where no-one knows each other). If it does not exist, return -1.

public int findCelebrity() {
		int celebrity = 0;
		for (int i = 1;  i < N; i++) {
			if (knows(celebrity, i)) {
				celebrity = i;
			}
			else if (knows(i, celebrity)) {
				// No need to do anything here.
			}
			else if (i + 1 < N) {
				// None of them are celebrity, lets select a new one.
				celebrity = i + 1;
				i++; // Increment the counter as none of these two are celebrity.
			}
		}
		boolean noCelebrity = false;
		// We need to confirm if the celebrity is correct or not.
		for (int i = 0; i < N; i++) {
			if (!knows(i, celebrity) || (i != celebrity && knows(celebrity, i))) {
				noCelebrity = true;
			}
		}
		if (noCelebrity) {
			return -1;
		}
		return celebrity;
	}

- Sumeet Singhal January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

is this O(N)?

- Anonymous February 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

That is a classic problem. If A knows B, we can eliminate A, otherwise we can eliminate B. We can eliminate one person after each time we call knows(i, j), so it will take O(n) to find the celebrity.

- Henrywang0113 January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Suppose there are four persons A B C and D

lets say A doesn't know B. It means B MAY know A or C or D. Then how can you eliminate B?

Please explain.

- MIG January 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If A doesn't know B, that means B can't be the celebrity since celebrity is known by everyone.

Really neat O(n) algorithm, surprisingly hard to figure out on the fly.

- Anonymous January 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not so simple.
lets say that A knows B. So we can eliminate B and move to C.
let say that A doesn't know C. Then obviously A is not the celebrity.

Now what? we move to C right? because A and B are not the celebrity.
we need to make sure that the other people (in this case person B) know C (in order for him to be a celebrity. We did not check that before, we just eliminate B.

So we need to **go back** to person B and check if he knows C.

in other words, we don't have n steps, because we need to go back to previous persons....

- Matoy January 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That is right, that's why whatever celebrity you find in the end, you need to verify if that person is indeed a celebrity. The first part of algorithm establishes that the rest of n - 1 person are not celebrities and that this person might be a celebrity, which you can verify (or reject) in O(n) time.

- Sumeet Singhal January 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Perfect solution!

- Anonymous January 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why would we be able to eliminate one person after each call to know(i,j). Imagine the following scenario:
A B C D E F
F is the celebrity. And A B ... E do not know each other but only F. F doesnt know anyone since it is a celebrity. If you go sequentially, you would make O(n^2) comparisons

- siddhupiddu December 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

if A doesn't know B how do you eliminate B?

- Anonymous January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

Because that means B is not known by everyone.

- Anonymous January 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Suppose there are four persons A B C and D

lets say A doesn't know B. It means B MAY know A or C or D. Then how can you eliminate B?

Please explain.

- MIG January 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Definition of Celebrity:
Everyone in the set knows this person
Celebrity knows only himself and no one else in the set.

So if A (some one in the set) doesn't know B then B cannot be a celebrity. OTH A can potentially be a celebrity (unless already ruled out).

- Anonymous January 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Assumed that there is only one celebrity in the group
Person function FindTheCeleb(List<Person> persons)
{
    Stack stk = new Stack(persons);
    Person theCeleb = new Person();
    
    theCeleb = stk.pop();
    while(stk.size)
    {
        Person tmpPerson;
        tmpPerson = stk.peek();
        if(knows(theCeleb, tmpPerson) || !knows(tmpPerson, theCeleb))
        {
            theCeleb = stk.pop(); //The new celeb is the tmpPerson(the next person in the stack)
        }
        else
        {
            stk.pop();
        }
    }
    
    return theCeleb;
}

- Anonymous January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I believe this can be solved using graphs.
Lets say we have N nodes in directed graph. Each node represents a person. If a node sees only incoming edges, then its a celebrity. If a node sees both incoming and outgoing, then its a normal person. For the sake of simplicity, we wont draw self edges (to convey that a person knows himself and since its same for all). Thus we would need to traverse all node edges (Adjacency list) once to find out number of celebrities in the event. This would be O(n).

I am new to this topic. Please suggest if the solution above seems doable.

- Anonymous January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Building the tree will take O(n2) because to make edges you'll have to for each node call for knows() about each other node.

- Anonymous January 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

my 2 cents.
lets model the problem as a adjacency matrix one.
lets define int arr[][] and for each arr[i][j] is 1 <=> i knows j.

so we acutally need to find 2 thing:
1. all of the k rows that follow this rule: (arr[k][i]==0 iff k!=i) for (0<=i<=arr.length)
2. all of the m colums that follow this rule: (arr[i][m]==1) for (0<=i<=arr.length)

the 1's rule checks if the person k doesn't know no one else but himself.
the 2's rule checks if all the other person know who person m is.

we need to find k such as (k==m), meaning both of the conditions are followed.

for i.e. this is a matrix that has person with index 3 (starting from 0) as a celebrity:

1 0 0 1 1
1 1 1 1 1
0 0 1 1 0
0 0 0 1 0
0 0 0 1 1

note that there can be no more than one k and no more the one m.

we can travel in a manhattan distance path from the first line until we encouter the last line or column of the matrix fo find the celebrity (we are actully finding k which is unique and can only be equal to m).

1-0-0 1 1
1 1 1 1 1
0 0 1 1 0
0 0 0-1-0
0 0 0 1 1

and the code:

package findCelebs;

import java.util.HashSet;
import java.util.Set;

public class FindCelebrity {
	static int knows[][];

	public static void main(String[] args) {
		knows = new int[][] { 
				{ 1, 0, 1, 1, 1 }, 
				{ 1, 1, 1, 1, 1 },
				{ 0, 0, 1, 1, 0 }, 
				{ 0, 0, 0, 1, 0 }, 
				{ 0, 0, 0, 0, 1 } };
		
		Set<Integer> people = new HashSet<Integer>();

		for (int i = 0; i < 5; i++) {
			people.add(i);
		}

		System.out.println(findCelebrity(people));
	}

	public static int findCelebrity(Set<Integer> group) {
		return isCelebrity(group, 0);
	}

	public static int isCelebrity(Set<Integer> group, int personInKRow) {
		if (personInKRow >= group.size()) {
			return -1;
		}

		// a celebrity must knows himself
		if (!knows(personInKRow, personInKRow)) {
			// so check the next person in line
			return isCelebrity(group, personInKRow + 1);

		}
		for (int j = personInKRow + 1; j < group.size(); j++) {

			if (knows(personInKRow, j)) {
				// personInKRow is not the celebrity - knows some one else but
				// himslef
				// so check the person in line j
				return isCelebrity(group, j);
			} else {
				// personInKRow does not know j -j is not the celebrity
			}
		}
		return personInKRow;
	}

	private static boolean knows(int i, int j) {
		return (knows[i][j] == 1);
	}
}

- Patrick January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This program fails if there is no celebrity,
For Example, it fails if,
knows = new int[][] {
{ 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1 },
{ 0, 0, 1, 1, 1 },
{ 0, 0, 0, 1, 1 },
{ 0, 0, 0, 1, 1 } };
The program returns 4 whereas it should return -1

- xyz January 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

A small modification to the above program will give the result.

import java.util.HashSet;
import java.util.Set;

public class FindCelebrity {
	static int knows[][];

	public static void main(String[] args) {
		knows = new int[][] { 
				{ 1, 0, 1, 1, 1 }, 
				{ 1, 1, 1, 1, 1 },
				{ 0, 0, 1, 1, 1 }, 
				{ 0, 0, 0, 1, 1 }, 
				{ 0, 0, 0, 1, 1 } };
		
		Set<Integer> people = new HashSet<Integer>();

		for (int i = 0; i < 5; i++) {
			people.add(i);
		}

		System.out.println(findCelebrity(people));
	}

	public static int findCelebrity(Set<Integer> group) {
		return isCelebrity(group, 0);
	}

	public static int isCelebrity(Set<Integer> group, int personInKRow) {
		if (personInKRow >= group.size()) {
			return -1;
		}

		// Everyone including celebrity knows themself.
		// Hence even if knows[i][i] == 0 (i.e. a person who does not know himself)[which is an exception case]
		// then also we should move forward
		if (!knows(personInKRow, personInKRow)) {
			return isCelebrity(group, personInKRow + 1);
		}
		
		for (int j = personInKRow + 1; j < group.size(); j++) {

			if (knows(personInKRow, j)) {
				// personInKRow is not the celebrity - knows some one else but
				// himslef
				// so check the person in line j
				return isCelebrity(group, j);
			} else {
				// personInKRow does not know j then j is not the celebrity
			}
		}
		return checkCandidate(personInKRow,group.size());
	}

	private static int checkCandidate(int candidate, int size) {
		int count=0;
		for(int i=0;i<size;i++){
			if(i!=candidate && knows(i, candidate) && !knows(candidate,i)) // check if all rows are 0 and the columns are 1
				count++;
		}
		if(count==(size-1))
			return candidate;
		else
			return -1;
	}

	private static boolean knows(int i, int j) {
		return (knows[i][j] == 1);  // returns true or false
	}
}

- xyz January 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

string FindCelebrity(vector<string> persons)
{
	if (persons.empty())
	{
		return NULL;
	}

	if (persons.size() == 1)
	{
		return persons[0];
	}

	// First find the person that might be a celebrity because he doen't know anyone else
	string celebrity = persons[0];
	for (int i = 1; i < persons.size() - 1; i++)
	{
		if (Knows(celebrity, persons[i]))
		{
			celebrity = persons[i];
		}
	}

	// Now we can check if the candidate is known by everyone else
	for (int i = 0; i < persons.size() - 1; i++)
	{
		if (!Knows(persons[i], celebrity))
		{
			return NULL;
		}
	}

	return celebrity;
}

- Anonymous January 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In this problem, there will either be only one celebrity or no celebrity.

Now iterate over list of people picking two at a time say A & B. Check function knows(A,B). If A knows B, then eliminate A (as it knows someone else, so not a celebrity) and pick next person C. If A does not know B, then eliminate B (as celebrity should be known by all) and pick next person C. This will be O(n) and at the end only one person will remain (as we are eliminating one at each step) say P.

Now either this person is celebrity or none is celebrity. So again iterate over all elements picking each element once (say E) and check knows(P,E) & knows(E,P). If any of the E returns knows(P,E) as true or knows(E,P) as false, then return no celebrity found. Else return P as celebrity.

This will take O(3n) steps ie. O(n).

- paroksh.saxena January 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Based on the henrywang's suggested solution I implemented this quickly. Ideally you would want to use a set implementation that can return n distinct objects randomly but efficiently. Here I'm converting the set to an array each time and taking the first two objects. This might be efficient in a Ruby set, not sure.

require 'set'

def knows(i, j)
  #
end

def celebrity(set)
  while set.length > 1
    # ideally use a set that can
    # return any two distinct objects
    array = set.to_a
    a = array[i]
    b = array[i + 1]
    
    if knows(a, b)
      set.delete(a)
    else
      set.delete(b)
    end
  end
  
  set.to_a[0]
end

- fungled January 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Go implementation

package main 
import "fmt" 

func main() {
	arr := []string {
		"Selena",
		"Miley",
		"Justin",
		"Katy",
		"Taylor",
	}

	findCelebrity(arr)
}

func findCelebrity(arr []string) {
	index := 0
	for i := 1; i < len(arr); i++ {
		if knows(index, i) || !knows(i, index) {
			index = i
		}
	}

	for i := 0; i < index; i++ {
		if knows(index, i) || !knows(i, index) {
			fmt.Println("No celebrity found")
			return
		}
	}

	fmt.Println(arr[index], "is the celebrity")
}

func knows(a, b int) bool {
	arr := [][]uint8{
		{ 1, 0, 1, 1, 0 },
		{ 1, 1, 0, 1, 0 },
		{ 0, 0, 1, 1, 0 },
		{ 0, 0, 0, 1, 0 },
		{ 1, 0, 0, 1, 1 },
	}

	return arr[a][b] > 0
}

- DP February 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static Person FindCelebrity(IEnumerable<Person> P)
{
	if(P == null) return null;
	
	// Creating a working list
	P = new List<Person>(P);
	int pos = 0;
	while(P.Count > 1)
	{
		int p1 = pos;
		int p2 = pos + 1;
		bool p1kp2 = Knows(P[p1], P[p2]);
		bool p2kp1 = knows(P[p2], P[p1]);

		if(p1kp2 && !p2kp1)
		{
			P.Remove(p2);
		}
		else if(!p1kp2 && p2kp1)
		{
			P.Remove(p1);

			if(pos != 0)
				pos--;
		}
		else if(p1kp2 && p1kp2)
		{
			P.Remove(p2);
			P.Remove(p1);
		}
		else
		{
			pos++;
		}
	}
	
	// There is no celebrity
	if(P.Count == 0)
		return null;

	return P[0];
}

- Nelson Perez March 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

By the requirement, Celeb is someone who only knows himself.

Thus solution can be very simple:

for(i = 1 to n)
if (knows(i,i))
return celeb;

Thats it.

- Anonymous March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

From the given info:

Celeb is someone who only knows himself, everyone else knows the celeb.

So here, we find someone who only knows himself, rather than finding someone whom everyone knows.

for (i = 1 to n)
	if (knows(i,i)==true)
		return (i is celeb);

- psisanon March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import groovy.transform.EqualsAndHashCode

/**
Given a set of n people, find the celebrity.
Celebrity is a person who:
1. Knows only himself and no one else
2. Every one else knows this person

You are given the following helper function:
bool knows(i, j);
Returns:
True: If i knows j
False: otherwise

I proposed the O(n2) algorithm at first but he wanted me to improve on it. He wanted an O(n) algorithm

Ex: A->B->C
A->C<-D

A->C means A knows C
C<-A means C is Known for A
C is celebrity

* Created by Felipe on 21/03/2015.
*/

class Celebrity {

    static class Person {
        private String name
        List<Person> knows = new ArrayList<>()
        List<Person> isknown = new ArrayList<>()

        // the ideal would be a structure that was a list and set together
        //private static Set<Person> friendsSet = new TreeSet<Person>([compare:{a,b->  b.knows.size() <=> a.knows.size() }] as Comparator)
        private static Set<Person> friendsSet = new LinkedHashSet<Person>()
        private static List<Person> friendsList = new ArrayList<>()

        Person know(Person p) {
            knows << p
            p.isknown << this
            addFriends(p)
            addFriends(this)
            p
        }

        Person isKnown(Person p) {
            isknown  << p
            p.knows << this
            addFriends(p)
            addFriends(this)
            p
        }

        private void addFriends(Person p) {
            if (friendsSet.add( p )) {
                friendsList.add( p )
            }
        }

        boolean knows(i, j) {
            if (i>=0 && j>=0 && i < friendsSet.size() && j < friendsList.get(i).knows.size()) {
                friendsList.get(i).knows.get(j) != null
            }
            false
        }

        Person findCelebrity() {

            // with java 7 using the TimSort Average case performance  O(n log n)
            //def cmp =  [compare:{a,b->  b.knows.size() <=> a.knows.size() }] as Comparator
            friendsSet = friendsSet.sort {a,b->  a.knows.size() <=> b.knows.size() }

            friendsSet.find { Person p ->
                // Every one else knows this person
                (p.isknown.size() == friendsSet.size() -1) && (p.knows.size() == 0) //Knows only himself and no one else
            }

        }
    }

    static void main (String[] args) {
        def personA = new Person(name: "a")
        def personC = new Person(name: "c")
        def a = personA
                    .know(new Person(name:"b"))
                    .know(personC)
                    .isKnown(new Person(name:"d"))
        personA.know(personC)

        println "Celebrity is Person ${personA.findCelebrity()?.name}"

    }
}

- fop.net March 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

seeing the problem , i am not sure whether we have to find only one celebrity or there exist more than one. but in any case, the simpler means is the true value return for knows(i,i) ...as celebrity only has self loop. i am thinking interviewer was not iterated in knowing data structure skill but simple common sense or how well we try understanding the question.

When i see the problem i thought this as a graph and with the assumption that there is only one celebrity , in that case the graph Vertex whose adjust size is n-1 is the celebrity.

- rahul.singh4899 April 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is C++ version of solution.
DFS was used to search the relationship.

Running complexity is O(N) based on the assumption that there isn't anyone knows nobody.

#include <iostream>
using namespace std;

bool relation[5][5];


bool knows(int knower, int knowee)
{
	return relation[knower][knowee];
}

void dfs(int * visited, int pos, int len)
{
	for (int i = 0; i<len; i++)
	{
		if (pos != i && visited[i] !=1)
		{
			if (knows(pos, i))
			{
				visited[pos] = 1;
				dfs(visited, i, len);
			}
		}
	}
}
int find_celebrity(int len)
{
	int * visited = new int[len];

	for (int i = 0; i <len; i++)
	{
		visited[i] = 0;
	}

	for (int i = 0; i < len; i++)
	{ 
		if (visited[i] != 1)
			dfs(visited, i, len);
	}

	for (int i= 0; i<len; i++)
	{
		if (visited[i] ==0)
			return i;
	}
	return -1;
}



int main()
{
	relation[0][1]= true;
	relation[0][4] = true;
	relation[1][4] = true;
	relation[2][1] = true;
	relation[2][4] = true;
	relation[3][2]  = true;
	relation[3][4] = true;

	int pos = find_celebrity(5);
	cout << "celebrity is = " << pos <<endl;
}

- hankm2004 July 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is like finding a sink in a directed acyclic graph which is O(n)

- Skor January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

graph may have cycles. Consider the following adjacency matrix

1111
1111
0010
1111

celebrity is 2 (indexing starts from 0)

- Darkhan.Imangaliev January 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

We can use union-find to find the highest ranking candidate, and use union find to create disjoint set, the node in the union-set doesnt know anyone, but everyone knows the root node.

- Anonymous January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

that would work O(n * alpha(n)) - where alpha(x) is Ackermann function

- Darkhan.Imangaliev January 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

This is impossible to solve it in O(n). Assume everyone is celebrity, i.e., nobody knows any one. In that case, you have to make (n-1)*(n-1) comparison, this is O(n^2) complexity. This is the worse case. The best case would be
- 1 knows 2, eliminate 1
- 2 knows 3, eliminate 2
- (n-1) knows n, eliminate (n-1)

this is the only corner case that would result in O(n). Otherwise, it will be between O(n) to O(n^2), thus O(n^2).

- w.y January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

By the problem definition there can be only one celebrity, so you cant assume everyone is a celebrity

- Anonymous January 17, 2015 | 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