In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in minimum number of questions.
In a group of N people, find out if there is a celebrity (who knows no one, but evry one knows him).
Use the func. doesAknowB(A,B) returns true if A knows B.
Solution:
Maintain a stack of celebrities(possibly). Take two ppl A,B out from the stack and check if they know each other.
If doesAknowB(A,B) returns true, then A is discarded as he cant be the celeb. If it returns false, B is discarded as B cant be celeb bcoz evryone knows a celeb.
Keep discarding all the ppl till one last person remains. now validate if this person is celeb or not.
http://www.geeksforgeeks.org/archives/19622
In a group of N people, find out if there is a celebrity (who knows no one, but evry one knows him).
Use the func. doesAknowB(A,B) returns true if A knows B.
Solution:
Maintain a stack of celebrities(possibly). Take two ppl A,B out from the stack and check if they know each other.
If doesAknowB(A,B) returns true, then A is discarded as he cant be the celeb. If it returns false, B is discarded as B cant be celeb bcoz evryone knows a celeb.
Keep discarding all the ppl till one last person remains. now validate if this person is celeb or not.
http://www.geeksforgeeks.org/archives/19622
Reasoning: This solution uses the the fact that each comparison/question allows us to discard one of the person, who is not a celebrity for sure. So, after N comparisons we have 1 prospective celeb remaining, which we can confirm by asking another n-1 questions.
Don't take much of their time if u ever meet celebrities with herpes. The No. 1 thing their directors maintain a strategic distance from any sort of meet-and-welcome or other sort of obligation openly.
ReplyDelete