Difficulty: Medium, Asked-In: Facebook, Microsoft, Yahoo
There are n+1 people at a party. They might or might not know each other names. There is one celebrity in the group, and the celebrity does not know anyone by their name. However, all the n people know that celebrity by name.
You are given the list of people present at the party, and we can ask only one question from each one of them. “Do you know this name”? How many maximum numbers of questions do you need to ask to identify the actual celebrity?
This problem can be solved by reducing the problem size by one — decrease and conquer strategy, a recursive technique helpful in solving many problems. In the decrease and conquer strategy, we reduce the problem size by one (or sometimes by more than one) and then recursively apply the same strategy to the reduced problem till the problem size becomes small. Let’s understand this by solving the celebrity problem.
Among n person, we start by choosing 2 persons, say A and B and ask A whether he/she knows B. If “Yes”, then A cannot be a celebrity and can be eliminated. If “No”, then B cannot be a celebrity and can be eliminated. This reduces the problem size by one. We repeat the same strategy among the group of n persons. After n questions, one person (say X) will remain. It is given that, there is a celebrity present at the party then it should be this person (why? think!). So we have to ask a maximum of n questions to find the celebrity.
Suppose it is given that a celebrity may not be present at the party, then what would be the maximum questions we ask to identify a celebrity or determine that a group has no such person? The idea would be simple: from the above approach, if there is a celebrity, then it should be the last remaining person after n number of questions(why? think!). To check whether person X is a celebrity, we ask X whether he knows everybody else and whether everybody else knows X. Total number of questions = n + n + n = 3n.
Whenever there occurs some problem of connections or some relationship we can model that problem in terms of a graph? Can we convert this problem into a graph problem? Well, yes indeed it is a problem of graph which you can be visualized by the diagram below.
The person in the middle is the celebrity
The image has been represented as an undirected graph where the in-degree represents the number of people who know him and the out-degree represents the number of people he knows. So by assigning all the indegrees and out-degree if we could find the one with zero outdegrees and n in-degree would be our celebrity. Now let's see how can we code it.
Solution code C++
Now in this approach, we will see the beauty of stack and matrix representation. We try to represent the situation in the boolean matrix and then we will use the power of stack to reach to celebrity. To analyze this problem in this approach we will require an n*n matrix if we have n people. Now let ‘i’ represent the row and ‘j’ column. Then any cell (i, j) will represent whether i know j or not. If a cell contains 1 means yes i know j otherwise No.
The matrix after filling in the information
After getting this information we will process it using stack. Firstly, we will store all n people in the stack and each time we will pick up two-person A and B and ask questions about whether A knows B or not, and this time we will simultaneously ask B whether he/she knows A or not. If both say ‘Yes’ We will not put them back to stack and if one of them say’s ‘No’ we will put him/her to stack. In the end, we will have only two-person remaining and thus we will get the celebrity there. Let’s see how can we code this out.
Solution code C++
Hope you enjoyed this blog. Enjoy learning, Enjoy thinking!
A group of four people, who have one torch, need to cross a bridge at night. A maximum of two people can cross the bridge at one time, and any party that crosses (either one or two people) must have the torch with them. The torch must be walked back and forth and cannot be thrown. Person A takes 1 minute to cross the bridge, person B takes 2 minutes, person C takes 5 minutes, and person D takes 10 minutes. A pair must walk together at the rate of the slower person’s pace. Find the fastest way they can accomplish this task.
You’ve got someone working for you for seven days and a gold bar to pay him. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. What is the fewest number of cuts to the bar of gold that will allow you to pay him 1/7th each day?
The summation formulas are used to calculate the sum of the sequence. In this blog, we have discussed the visual proofs: the sum of numbers from 1 to n (arithmetic series), the sum of infinite geometric series, the sum of squares of numbers from 1 to n, etc.