Thursday, March 29, 2012

Celebrities

In a group of persons, a celebrity is know by everyone and all the other people are known by none. Detect all the celebreties

2 comments:

  1. Based on problem reduction.

    Given N celebrities. Exclude N-1 celebrities which can be found recursively. If the N-th celebrity (?) knew the celebrity of N-1 celebrities, and the celebrity of N-1 group doesn't know N-th celebrity, our answer is (N-1)-th celebrity. Otherwise, better by pseudo code

    int celebrity(Queue[1...N])
    {
    remove N;
    c = celebrity(Queue[1...N-1])

    if( N know c ) // possible that c can be
    {
    if( c doesn't know N ) return c;
    else return -1; (No celebrity)
    }
    // directed graph, failing if doesn't imply that
    // c know N
    else if( c know N )
    {
    if( N doesn't know c ) return N;
    else return -1; (No celebrity)
    }

    return -1; (No celebrity) // data incorrect
    }

    But the run time is O(n^2) :(. Any other better approach? May be like Moore's elimination voting algorithm?

    ReplyDelete
  2. http://www.geeksforgeeks.org/archives/19622

    ReplyDelete