Programming Problems #1 : Celebrity Problem
Let’s discuss a very interesting coding problem known as the “Celebrity Problem” today. It has been asked frequently in interviews of companies like Google, Amazon and Apple. This article will present an overview of the problem with an explanation and solution coded in Python.
Problem Statement
“A celebrity among a group of N people is a person who knows nobody but is known by everybody else. Each person has been assigned a unique id between 0 to N- 1 (both inclusive). The task is to identify a celebrity by only asking questions to people of the form “Do you know him/her?” Print the id of the celebrity. If there is no celebrity at the party, then print -1.”
Right away, we can start interpreting the given data from the problem. You have to find a celebrity from a group of N people, based on their answers, Yes/No. This can easily be represented using a matrix, we will call this the ‘whoknowswho’ matrix. Using an example, it will look something like this :
# a b c d
#a {{0, 1, 0, 0},
#b {0, 0, 0, 0},
#c {0, 1, 0, 0},
#d {0, 1, 0, 0}}This can be a matrix of 1’s (Yes) and 0’s (No). Now that we have a nice representation of the given data, let’s go ahead and figure out what we need to do to find out the celebrity. There are two main conditions for a person to become a celebrity,
- The person (say A) should not know anyone. (i.e all the entries row containing A’s responses should be 0, except for A itself.)
- Everyone should know that person. (i.e all the entries in the column of A, should be 1 other than A itself.)
In the above example matrix, we see that applying these two rules gives us the id of the celebrity b(index : 1).
Naive Approach
Let’s solve this problem first using a brute force method. Since we have a matrix, we can use two loops to iterate through each value in the matrix and check for the above two conditions.
The running time of this solution is O(n²).
Efficient Approach
Whenever I encounter a matrix or an array I need to iterate through, the efficient method that solves the problem is usually one that uses the two-pointer method. In this case, you can use logic and the two pointer method to arrive at an O(n) running time method.
From the given data we can deduce the following :
- If person A knows B, A cannot be the celebrity.
- If B knows A, B cannot be the celebrity.
Say you have two pointers, start = 0, end = n-1. We will start checking the values of whoknowswho[start][end] one by one. The implementation of this solution is given below.
The running time of this solution is O(n). Now, we have an efficient algorithm to solve this problem. Stay tuned for more programming problem explanations like this one. Bye for now !
References
