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!
There are 3 doors behind which are two goats and a car. You pick door 1 hoping for the car but don’t open it right away. Monty Hall, the game show host who knows what's behind the doors, opens door 3, which has a goat. Here's the game: do you want to pick door No. 2? Is it to your advantage to switch your choice?
You have given n-bulbs connected in a circle with a switch for each bulb. The connection is such that if you change the state of anyone bulb may be on or off, it will toggle the state of its adjacent bulbs. All the bulbs are initially switched off. You have to find the number of steps such that all the bulbs are switched on.
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.