Facebook Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
11
of 13 vote

This is the classic case of celebrity problem. You basically put all the persons in a stack, then pop first 2, pass it to isKnow(p1, p2) method, if return true, then p2 might be celebrity so push p2 back in stack, if returns false then p1 might be celebrity, so put p1 back in stack and discard p2. So, you are eliminating one element in every iteration. End of the operation you will be left with one element in stack and that is your famous person.

- pulz June 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

find the sink in a graph, that can be done in linear time

- rtrombone June 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

In Scala using a functional approach:

object FindFamous {
  def main(args: Array[String]): Unit = {   
    val a = Array(
        ("Joe", "John", true), 
        ("Suzy", "John", true),
        ("Jay", "John", true),        
        ("Jack", "John", true),
        ("Jay", "Jack", false),
        ("Joe", "Suzy", true),        
        ("Jay", "Suzy", false),
        ("Jack", "Suzy", true),
        ("John", "Suzy", false)
    )     
    println(getFamous(a))
  }   
    
  def getFamous(arr:Array[(String,String,Boolean)]) : String = {            
    val a = arr.filter(_._3 == true)
    val copy = a.clone()
    
    val result = a.filter {
      case (p1,p2,r) => !copy.exists(_._1.equals(p2)) 
    }
    
    if (result.size > 0) {
      return result(0)._2
    }
    return ""
  }

}

- guilhebl June 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

More interestingly, here is a very simple approach that solves the problem.
[stackoverflow.com/questions/4137481/detecting-the-sink-in-a-directed-acyclic-graph]
====
As there are no cycles in the graph, and all vertex connect with the sink, just select any starting node and start walking randomly. When you can't continue walking, you are at the sink, in at most n steps.
======

- NoOne June 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Something like this?

public Person findCelebrity(List<Person> list) {
        Stack<Person> stack = new Stack<>();
        for(Person p : list)
            stack.push(p);

        Person a = null;
        Person b;
        while(!stack.isEmpty()) {
            if(stack.size() == 1) {
                a = stack.pop();
                break;
            }
            a = stack.pop();
            b = stack.pop();

           if (isKnow(a,b) )
                stack.push(b);
           else
                stack.push(a);
        }

        for(Person p : list) {
            if(!isKnow(p, a))
                return null;
        }
        return a;

    }

- KC June 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is awesome , except a minor change

for(Person p : list) {
            if(!isKnow(p, a))
                return null;
        }

to

for(Person p : list) {
            if(p!=a){ // celebrity doesn't know itself , so we should not check isKnow 
                if(!isKnow(p, a))
                    return null;
            }
        }

- Mayank Jain August 07, 2017 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

in Python, with a graph

class famousGraph:
    def __init__(self, adjacency_list):
        self.graph = adjacency_list
        self.visited = set()
        self.famous = None
        
    def findFamous(self, start):
        # Bit of memoization
        if self.famous != None:
            return self.famous
        
        # DFS
        self.visited.add(start)

        knowlist = self.graph[start]

        if len(knowlist)==0:
            self.famous = start
            return start
        else:
            # Generator is important; list comp would make this O(n^2)
            return self.findFamous(next(x for x in knowlist if x not in self.visited))

# Tests
person_graph = famousGraph({'a':['b','c'], 'b':['a','c'], 'c':[], 'd':['b','c']})
print(person_graph.findFamous('a'))
person_graph = famousGraph({'a':['b','c'], 'b':['a','c'], 'c':[], 'd':['b','c']})
print(person_graph.findFamous('c'))
print(person_graph.findFamous('d'))

- sunfire June 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

lets have a set of people not knowing any one in the given list:
start from the list, and if found in the set, then remove that person from the set
else at the end of iterator insert the list current person into the famous person set
// since its just the iteration over the famous people, any ds will do. as long as the insertion and removal is not expensive
Set : O(logn),
Unordered Set/list/dequeue O(1).
I have implemented using the set, though the above choices are better

struct people {
  string name;  
};

set<people> get_famous_people(const list<people> &c) {

    if (c.empty()) {
        return set<people>();
    }
    
    set<people> famous; 
    set<people>::iterator fit;
    
    for(list<people>::const_iterator it = c.begin(); it!= c.end(); ++it) {
        fit = famous.begin();
        bool is_seen = false;
        
        while(fit != famous.end()) {
            if (know_each_other(*fit, *it)) {
               fit = famous.erase(fit);
            } else {
                ++fit;
            }
        }
        // what to do with it. 
        if (!is_seen) {
            famous.insert(*it);
        }
    }
    
    return famous;
    
}

- ali.kheam June 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Assumptions: there may or may not be a famous person. Time Complexity: O(n). Space Complexity: O(1)

public int getFamous(int n){
	int i = 1;
	int j = 0;
	while(j < n){
			if(i == m.length){
				return j;
			}
			if(isKnow(i,j)&& !isKnow[j][i]){
				i++;
			}
			else{
				int tmp = j;
				j = Math.max(i, j + 1);
				i = j;
		
			}
	
	}
	return -1;
}

- divm01986 June 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int know_someone(int *ara, int n, int index) {
    if (index == n) {
        return index;
    }
    int current_celeb = know_someone(ara, n, index+1);
    // current_cele is celeb of people [index+1, n]
    if (current_celeb != -1 && !knows(current_celeb, ara[index])) {
        // if current celeb
        return current_celeb;
    }

    int i = index+1;
    // check whether the ara[index], know anyone from [index+a, n]
    for(; i <=n; i++) {
        if (knows(ara[index], ara[i])) {
            break;
        }
    }
    if (i == n+1) {
        // doesnt know 
        return ara[index];
    }
    return -1;
}

- ali.kheam June 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from TreesAndGraphs.graph import Graph
from StacksAndQueues.Stack import Stack
from nose.tools import assert_equal


class FamousPerson(Graph):
    def __init__(self):
        super().__init__(directed=True)

    def does_know(self, u, v):
        if self.get_edge(u, v):
            return True
        return False

    def find_famous(self):
        persons = self.vertices()
        stack = Stack()
        for person in persons:
            stack.push(person)

        while not stack.is_empty():
            person1 = stack.pop()
            try:
                persons2 = stack.pop()
            except:
                return person1
            if self.does_know(person1, persons2):
                stack.push(persons2)
            else:
                stack.push(person1)

if __name__ == "__main__":
    fp = FamousPerson()
    av = fp.insert_vertex("arshad")
    uv = fp.insert_vertex("Umar")
    bv = fp.insert_vertex("bilal")
    zv = fp.insert_vertex("zareen")
    tv = fp.insert_vertex("Tahir")
    qv = fp.insert_vertex("qasim")

    fp.insert_edge(av, uv)
    fp.insert_edge(bv, uv)
    fp.insert_edge(zv, uv)
    fp.insert_edge(tv, uv)
    fp.insert_edge(zv, tv)
    fp.insert_edge(qv, uv)
    assert_equal(fp.find_famous().element(), "Umar")
    print("Success")

- tahir.rauf1 June 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>

#define SIZE 4

using namespace std;

bool _relation[SIZE][SIZE] = { {true, true, false, false},
        {false, true, true, true},
        {true, true, true, true},
        {false, false, false, true}};

bool knows(int i, int j) {
        return _relation[i][j];
}

int findFamus(const vector<int> &people) {
        int candidate = 0;

        for (int i = 1; i < people.size(); ++i) 
                if (candidate != i && knows(people[candidate], people[i])) 
                        if (!knows(people[i], people[candidate]))
                                candidate = i;
                        else 
                                candidate = i + 1;

        if (candidate == people.size())
                return -1;

        for (int i = candidate - 1; i >= 0; --i)
                if (knows(people[candidate], people[i]) || 
                                !knows(people[i], people[candidate]))
                        return -1;

        return candidate;
}

int main(void) {
        vector<int> people {0, 1, 2, 3};

        int famus = findFamus(people);

        cout << famus << endl;

        return 0;
}

- CRSC June 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int celebrity(People[] people)
{
   int candidateIdx = 0; //pretend the first person is the celeb
   for(int idx = 1; idx < people.Lenght; idx++) {
      if(knows(candidateIdx, idx)) { //if the candidate knows anyone it can't be the celeb
         candidateIdx = idx; // but that person could be, so make it the candidate
      }
   }
   for(int idx = 0; idx < people.Length; idx++ { //validate that the candidate is indeed a celeb
      if(idx != candidateIdx &&
         (!knows(idx, candidateIdx) || knows(candidateIdx, idx)) { //if the candidate is not known by someone or knows someone it can't be the celeb
          candidateIdx = -1; //there is no celeb
          break;
      }
   }
   return candidateIdx;
}

- max June 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Objective-C. Below code will give O(n) complexity. Each time in a loop we will compare currentIndex Person with nextIndex person. If we find that currentIndex person knows nextIndex person but nextIndex person doesn't know currentIndex person then our famousPerson would be nextIndex person for the time being. We will use this famous person to compare with next person in the array untill we reach the end of loop. At the end of loop, we will have famous person.

-(NSString*)personWhoIsFamous:(NSArray*)listOfPersons
{
	NSString* famousPerson = nil;
	
	for(NSUInteger currentIndex = 0; currentIndex <  [listOfPersons length] ; currentIndex++)
	{
		if(famousPerson == nil)
		{
		 	famousPerson = [listOfPersons objectAtIndex: currentIndex];
		}		
		
		NSString* personAtNextIndex = [listOfPersons objectAtIndex: currentIndex +1];

		if( [famousPerson knows: personAtNextIndex] && 
			![personAtNextIndex knows: famousPerson])
		{
			famousPerson = personAtNextIndex;
		}
		if([personAtNextIndex knows: famousPerson] && ![famousPerson knows: personAtNextIndex])
		{
			continue;  //famousPerson continues to be famous here.
		}
		else  // In this else either both know each other or both don't know each other, so discarding both of them
		{
			famousPerson = nil;
			currentIndex = currentIndex+2;
		}
		
	}
	
	return famousPerson;
}

- Adesh June 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function findCelebrity(n, knows) {
  let a = 0;
  
  for (let i = 1; i <= n; i++) {
    if (knows(a, i)) { // if current assumed celebrity (a) knows someone, we guessed wrong
      a = i; // but i still can be a celebrity
    }
  }
  
  // the only thing we don't know is if current celebrity (a) knows anyone in front of queue
  for (let i = 0; i < a; i++) {
    if (knows(a, i)) {
      return -1;
    }
  }
  
  // if everybody in the end of queue knows the current celebrity, then it's a right answer
  for (let i = a + 1; i < n; i++) {
    if (!knows(i, a)) {
      return -1;
    }
  }
  
  return a;
};

- mrj July 05, 2018 | Flag Reply


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