Finding Celebrity logical interview puzzle

Puzzle: You are on a party with N guests. Some people at the party know each other some don’t. However there is a celebrity who joined the party. Everyone knows him, but he knows no one. There is only one celebrity at this party. Imagine you have a function bool IsKnown(P1, P2) which takes two people as an input and returns true if P1 knows P2 or false if P1 doesn’t know P2.

Question: Write an algorithm to find a celebrity. What is the complexity of this algorithm?

Bonus question: What if there are m celebrities? How would you change the algorithm? What would be the complexity?

Answers and Comments