[Snapchat] Celebrity Problem

1. Example

N people , only one person is known to everyone.
Find out the minimum question need to ask to find the celebrity?

A <-  B <- D
 A <-C < -B
A<-  D < -E
A<- E <-B
2. Implementation
Methods1 n*n
Q1: ask anyone whom he or she know?

A1: nxn matrix, aij=1 means i know j, otherwise 0.

So all i know j means column j all 1, j is the celebrity. Otherwise, there is no celebrity.
Methods2 n-1 + 2n-2
Q1: bubble ask ABCDE
A1:
STEP1 : 1 question former knows later
1 Questions*(N-1 ) person
A vs B,(A knowB) take out A or B and leave A or B keep going down
? knows C
? knows D
? knows E
STEP2: 2 question , (LEFTOVER!= later)LEFTOVER knows later or later knows LEFTOVER
2Questions * (N-1) person
Methods3 n-1 + 2n-2 - log2n (n-1 + 2n-2 is like Methods2 when one left we need to ask thru all other uses but there are already log2n have been asked in the TREE)
n = 2^k
Q1: two person a pair and within a pair, they ask to each other

A1: (A,B) eliminate one person by asking if A knows B. Left n/2 persons. Until 1 left

BINARY TREE

N/2(level 1) + N/4(level 2)+..+1(level k)= N(1/2+1/4+...1/2^k)= N-1

N = 8 = > 7 Qs

   1 2    3y  4'   5 6   7 8

     1y     4'         6     7

         4'                  6y

                  4'

http://www.slideshare.net/SriHarsha1508/lec10-31843573

3. Similar Ones