Find Celebrity [reviewed]

Question:

You are given the 2x2 array showing who is following and who is followed.
Example) If array[0][1] = true, this means Person 0 follows person 1.
Celebrity is one that everyone follows him/her but he/she does not follow anyone.

Your algorithm should print out who is celebrity, given the 2X2 Array with followee-follower relationship.

I think I saw this question from one of Facebook interview questions. Unfortunately, I did not write down the questions. I am recollecting the questions based on my old answer.

Feel free you correct me if I am wrong.

Brute-force search algorithm examining 2x2 array will run in O(N^2). However, we wants faster than that.

*New* Matrix based approach, O(N)

UPDATE(2019-07-31): solved the problem again and realized that I was overthinking when solving this problem.

The question defines a celebrity as "Celebrity is one that everyone follows him/her but he/she does not follow anyone". If we describe celebrity in N x N matrix, $R$, it will look like below:

If 3rd person is a celebrity,

• Condition 1: entire 3rd row will be False since he/she is not following anyone. 
• Condition 2: 3rd column will be True except for 3rd position because everyone is following 3rd person.

Now, we need to find is to iterate over each person and check if that person's sum value of row is 0 and sum of column value is N-1.

This algorithm can be changed to find the most popular person. In that case $Condition 1$ holds and find the person who's column value is the most. In the python solution below, I assumed there can be multiple celebrities. (but there can by only one meeting the current definition).

Here is a solution in python.

	def find_celebrity(relationship):
	celebrity = []
	total = len(relationship[0])
	#for all people
	for i in range(total):
	# if i th person follow no one and everyone follows i.
	if sum_rows(relationship, i) == 0 and sum_column(relationship, i) == total -1:
	celebrity.append(i)
	return celebrity
	def sum_rows(list, current):
	sum = 0
	for i in range(len(list[0])):
	sum += 1 if list[current][i] == True else 0
	return sum
	def sum_column(list, current):
	sum = 0
	for i in range(len(list[0])):
	sum += 1 if list[i][current] == True else 0
	return sum
	# 1 is the celebrity
	input = [[False, True], [False, False]]
	print ("input = {}, celebrity = {}".format(input, find_celebrity(input)))
	# 0 is the celebrity
	input = [[False, False], [True, False]]
	print ("input = {}, celebrity = {}".format(input, find_celebrity(input)))

view raw find_selebrity_given_matrix.py hosted with ❤ by GitHub

Practice statistics:

07:22: to come up with algorithm
13:48: to write the code (had two bugs found after running)

DFS based approach, O(N)

This is the one type of graph search problems locating the nodes that does not any outgoing edges.
Using the Depth-First search, we might be about to search this relationship in O(N).

In this case, if we use the DFS with tracking of visited node and extra arrays to keep track of the followers.  Here is the rough algorithm

1. For each person in the array. check if each person was visited.
  1-1. If not, perform DFS on from that person.
  1-2. If the person follows other person (has outgoing edge), mark that person as follower and increase the other person's follower count by one.
  1-3. If that person was not visited yet. Perform the DFS from that person.
  1-4. move on to the next person, current person is following and perform 1-1.
2. Move on to the next person on the array.
3. Find the person(s), who is not following anyone and has positive followers.


Original C++ solution based on Depth First Search.
Remember, that there can be multiple followers.

Here is the C++ code.

	#include <iostream>
	using namespace std;
	struct Stat{
	bool* visited;
	bool* following;
	int* followees;
	Stat(int size){
	visited = new bool[size];
	following = new bool[size];
	followees = new int[size];
	}
	};
	bool knows(int ** input, int s, int d)
	{
	return input[s][d] == 1;
	}
	void dfs(int ** input, Stat* stat ,int pos, int l)
	{
	for (int i = 0; i < l; i++)
	{
	if (knows(input, pos, i))
	{
	stat->followees[i] += 1;
	stat->following[pos] = true;
	if (!stat->visited[i])
	{
	stat->visited[i] = true;
	dfs(input, stat, i, l);
	}
	}
	}
	}
	void find_celebrity(int ** input, int h, int l)
	{
	Stat* stat = new Stat(h);
	bool found_celebrity = false;
	for (int i = 0; i < h; i++)
	{
	if (!stat->visited[i])
	{
	stat->visited[i] = true;
	dfs(input, stat, i, l);
	}
	}
	for (int i = 0; i < h; i++)
	{
	if(stat->followees[i] > 0 && !stat->following[i])
	{
	cout<<"celebrity is " << i<<" followers = "<<stat->followees[i]<<endl;
	found_celebrity = true;
	}
	}
	if (!found_celebrity)
	cout << "no celebrity is found"<<endl;
	}
	int main()
	{
	int ** input = new int*[6];
	for (int i = 0; i < 6; i++)
	input[i] = new int[6];
	input[0][1] = 1;
	input[1][0] = 1;
	input[1][2] = 1;
	input[1][3] = 1;
	input[2][3] = 1;
	input[2][4] = 1;
	input[4][3] = 1;
	input[2][5] = 1;
	find_celebrity(input, 6, 6);
	return 1;
	}

view raw find_celebrity.cpp hosted with ❤ by GitHub