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.

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.