Facebook Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
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 ""
}
}
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.
======
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;
}
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'))
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;
}
//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;
}
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;
}
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")
#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;
}
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;
}
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;
}
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;
};
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