Optimal solution for the "celebrity" algorithm

Question

Among n persons,a "celebrity" is defined as someone who is known by everyone but does not know anyone. The problem is to identify the celebrity, if one exists, by asking the question only of the form, "Excuse me, do you know the person over there?" (The assumption is that all the answers are correct, and even that celebrity will also answer.) The goal is to minimize the number of questions.

Is there a solution of the order less than the obvious O(n^2) here?

Answer 1

Using the analysis of the celebrity problem here

Brute-force solution. The graph has at most n(n-1) edges, and we can compute it by asking a question for each potential edge. At this point, we can check whether a vertex is a sink by computing its indegree and its outdegree. This brute-force solution asks n(n-1) questions. Next we show how to to do this with at most 3(n-1) questions and linear place.

An elegant solution. Our algorithm consists of two phases: in the elimination phase, we eliminate all but one person from being the celebrity; in the verification phase we check whether this one remaining person is indeed a celebrity. The elimination phase maintains a list of possible celebrities. Initially it contains all n people. In each iteration, we delete one person from the list. We exploit the following key observation: if person 1 knows person 2, then person 1 is not a celebrity; if person 1 does not know person 2, then person 2 is not a celebrity. Thus, by asking person 1 if he knows person 2, we can eliminate either person 1 or person 2 from the list of possible celebrities. We can use this idea repeatedly to eliminate all people but one, say person p. We now verify by brute force whether p is a celebrity: for every other person i , we ask person p whether he knows person i , and we ask persons i whether they know person p . If person p always answers no, and the other people always answer yes, the we declare person p as the celebrity. Otherwise, we conclude there is no celebrity in this group.

Answer 2

1. Divide all the people in pairs.

2. For every pair (A, B), ask A if he knows B.

   • if the answer is yes, A can not be the celebrity, discard him.
   • if the answer is no, B can not be the celebrity, discard him.

   Now, only half the people remains.

3. Repeat from 1 until just one person remains.

Cost O(N).

Answer 3

Here is O(N) time algorithm

1. Push all the elements into stack.
2. Remove top two elements(say A and B), and keep A if B knows A and A does not know B.
3. Remove both A,B is both know each other or both does not know each other