Monday, 16 July 2012

Search for Celebrity

Consider a party of n people. Consider a matrix A (nXn) with each entry being either 0 or 1. 
A(ij) = 1 if the ith person knows jth person in party
A(ij) = 0 if the ith person doesn't know jth person in party
Also note that A(ij) is not always equal to A(ji)

A celebrity is the one who doesn't know anybody but everybody knows him. 
Can you find the celebrity in O(n).

Disclaimer: This was again asked in GSach Interview which I was unable to answer. I guess you can try using directed graphs for solving this but not sure.