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

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

By definition there can be only one celebrity.

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

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

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

is this O(N)?

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.

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

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?

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

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.

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

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

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

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.

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

Perfect solution!

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

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

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

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

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

Because that means B is not known by everyone.

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

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?

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

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

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

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.

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

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.

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++) {
}

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);
}
}``````

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

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

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++) {
}

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
}
}``````

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

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

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``````

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
}``````

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];
}``````

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.

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);``````

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
p
}

Person isKnown(Person p) {
isknown  << p
p.knows << this
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}"

}
}``````

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.

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

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)

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

graph may have cycles. Consider the following adjacency matrix

``````1111
1111
0010
1111``````

celebrity is 2 (indexing starts from 0)

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.

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

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

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

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

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

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.