Given a function Know(A,B) If A knows B then the function returns true else false. Now in a given set of people a celebrity is one who is known by other people and he doesnt know any one. Given an array, find the number of celebrities and the celebrity in less than linear time.
I personally do not think it is possible in less than linear time.
Here is solution for same problem (with nice explanation) in linear time.
Hope it helps 
2 Likes
I think you can’t.
You have to read every people in the array, because if you forget one,
it could imply that the previously computed celebrity is in fact not one.
I don’t know if my explaination is clear enough, but the idea is basicly
you have ‘‘at least’’ to read the data to decide a problem where each part
of the data can change the solution of the problem. It’s the same reason
scientists don’t look for a matrix multiplication algorithm under O(N^2).
4 Likes
can u please give a link to the ques…or maybe explain what does the array exactly contain???
i also think the same… it cant be done… but in an interview ,it was asked thtz y??? 
maybe your interviewer wanted to know whether you were able to provide that explaination
2 Likes