Facebook Interview Question for Android Engineers


Country: United States
Interview Type: In-Person




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

public class FindTheCelebrity {

	public static void main(String[] args){
		int[] input = new int[] {1,2,3,4,5,6};
		
		FindTheCelebrity ftc = new FindTheCelebrity();

		int left = 0;
		int right = input.length-1;
		while(left<right) {
			if (ftc.knows(input[left], input[right])) {
				left++;
			} else{
				right--;
			}
		}
		
		int id = right;
		for(int i=0; i<input.length; i++) {
			if(i != right) {
				if(!ftc.knows(input[i], input[right])) {
					id = -1;
				}
				if(ftc.knows(input[right], input[i])){
					id = -1;
				}
			}
		}
		
		System.out.println("Candidate " + right);
		System.out.println(id == -1 ? -1 : input[id]);
	}
	
	public boolean knows(int a, int b) {
		int[][] map = new int[][] {{0,1,0,1,0,1},
			   					   {0,0,0,0,0,0},
			   					   {0,1,0,0,0,1},
			   					   {0,1,0,1,0,1},
			   					   {0,1,0,0,1,0},
			   					   {0,1,0,0,0,0}};
		return map[a-1][b-1] == 1;
	}
	
}

- mvb13 March 13, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We could represent the persons as the array of Qubits:
00: Celebrity - knows nobody in the room
01: No celebrity - knows only celebrity
10: No celebrity - knows everybody but no celebrity
11: No celebrity - knows the celebrity and everybody else

If we sort the array - then we know where to look for the celebrity.

- denis.zayats March 13, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Based on your question, the problem is asking us to find the celebrity given the person list and the person number. So, this can be done in O(N+N) = O(N) time where N = number of rows/cols. If this was problem was finding the celebrity given the matrix, then it would be a different problem. I present a solution in Python below.

I assume I am given an adjacency matrix. My solution in Python:

def determineCelebrity(peopleList, person):
    # Scan the adjacency matrix
    actualPersonIndex = person - 1
    # Scan the cols and make sure everyone knows the person
    for i in range(len(peopleList)):
        if i != actualPersonIndex and peopleList[i][actualPersonIndex] != 1:
            return False
    # Make sure the celebrity knows no one else in the party
    return all(x == 0 for x in peopleList[actualPersonIndex])

Test code:

celebrityMatrix = \
[
    [0, 1, 0, 1, 0, 1],
    [0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 1],
    [0, 1, 0, 1, 0, 1],
    [0, 1, 0, 0, 1, 0],
    [0, 1, 0, 0, 0, 0]
]
print(determineCelebrity(celebrityMatrix, 5)) # False
print(determineCelebrity(celebrityMatrix, 2)) # True
print(determineCelebrity(celebrityMatrix, 3)) # False

- prudent_programmer March 13, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Given problem of finding whether the given person is celebrity or not can be solved in 0(n) just by checking row corresponding to that person should be all 0's, and column should be all 1's.

2. If the problem is to find the celebrity, then also complexity will be O(n), ie. starting from the first person, iterate it's row and find out the first 1 say at element i, all elements/persons before that one cannot be celebrity as first person does not know them, so direct skip to i, and start iterating its row from i+1 th position and keep skipping .

- as7tomar March 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class FindTheCeleb
{
	public static void main (String[] args) throws java.lang.Exception{
	    
	    /*
	    Assumption: whoIknow matrix 
	    Everyone knows themselves, so a 1 for themselves
	    Everyone may or maynot know the others in the party thus 0/1 for the rest of the fields 
	    
	    */
		Integer[][] whoIknow=new Integer[][]{{1,0,0,0,0,0},
		                     {1,1,0,0,1,0},
		                     {1,1,1,0,0,0},
		                     {1,0,0,1,1,0},
		                     {1,0,0,1,1,0},
		                     {1,0,0,1,1,1}};
		                     
		Integer[] people= new Integer[]{1,2,3,4,5,6};
		
		Integer testPerson1 = 4;
		Integer testPerson2 = 1;
		System.out.println("Person "+ testPerson1 + 
		                    (isCelebrity(whoIknow, testPerson1)? " is a isCelebrity": " is not a celebrity"));
		                    
		System.out.println("Person "+ testPerson2 + 
		                    (isCelebrity(whoIknow, testPerson2)? " is a isCelebrity": " is not a celebrity"));
	}
	
	public static boolean isCelebrity(Integer[][] whoIknow, Integer testPerson){
	    int i=0;
	    for(;i<whoIknow.length;i++){
	        //System.out.println(whoIknow[i][testPerson-1]);
	        if(whoIknow[i][testPerson-1]==0){
	            //System.out.println("testPerson=" + testPerson);
	            return false;
	        }
	    }
	    
	   return true;
	}
}

- shah.hiral15 March 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FinaCelebrity {

    public static void main(String[] args) {

        // initialize Person instances assuming Tom is the celebrity
        // John
        Person john = new Person("John");
        john.friendsList.add("Eric");
        john.friendsList.add("Kevin");
        john.friendsList.add("Tom");
        john.friendsList.add("Joey");

        // Eric
        Person eric = new Person("Eric");
        eric.friendsList.add("John");
        eric.friendsList.add("BM");
        eric.friendsList.add("Tom");

        // Jeff
        Person jeff = new Person("Jeff");
        jeff.friendsList.add("Amy");
        jeff.friendsList.add("Tom");

        // Tom (the celebrity who knows no one in the room, so no friends)
        Person tom = new Person("Tom");

        // add persons into people
        ArrayList<Person> people = new ArrayList<Person>();
	people.add(john);
        people.add(eric);
        people.add(jeff);

        // check if a person is the celebrity
        String name = tom.name;
        if (findCelebrity(people, john))
            System.out.println(name + " is celebrity");
        else
            System.out.println(name + " is NOT celebrity");
    }

    // find if a person is celebrity among people
    static public boolean findCelebrity(ArrayList<Person> people, Person person) {

        // check if the person doesn't know any in the room
        if (!person.friendsList.isEmpty())
            return false;

        // check if everyone know the person
        int len = people.size();
        for (int i = 0; i < len; i++) {
            if (people.get(i).name != person.name) { // skip himself
                if (!people.get(i).friendsList.contains(person.name)) // check if person is included in the friend list
                    return false;
            }
        }

        return true;
    }

    static class Person {

        ArrayList<String> friendsList = new ArrayList<String>();

        String name;

        public Person(String _name) {
            name = _name;
        }

        public boolean knowSomeone(String person) {
            if (friendsList.contains(person))
                return true;
            else
                return false;
        }
    }
}

- CJ September 01, 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