Note that there cannot be more than one celebrity in the group.
Here is an O(n) solution:
Choose a random candidate x as a possible celebrity.
Let S be the set of remaining n-1 candidates.
While (S is not empty)
Remove another candidate y from S and ask if y follows x.
consider it as a directed graph and sink is the celebrity.do dfs to find
sink...
On Sat, Dec 18, 2010 at 11:30 PM, snehal jain wrote:
> In a n twitter set, a celebrity is defined as someone who is followed
> by everyone, but who follows no one. You need to identify the
> celebrities by asking to
In a n twitter set, a celebrity is defined as someone who is followed
by everyone, but who follows no one. You need to identify the
celebrities by asking to twitters the question: "do you know person
x?" The answer will be yes/no. Find the celebrity by asking only O(n)
questions.
--
You received
