OK, to clarify more on the questions: 1) The interviewer is interviewing people one by one. At the time of interviewing 'i'th person, he has info on how the first 'i-1' fared and how 'i'th guy is compared to them. Based on this info, he has the choice of selecting or rejecting the 'i'th guy then and there. This continues. Now what strategy to adopt to maximize the rank of the person selected. No word games here.
2) It can't be O(1). The only call you are allowed to make is knows(Person p, Person q), which returns TRUE if 'p' knows 'q' else FALSE. How can you make constant calls to this function and get who the celebrity is? AFAIK, there's no solution which takes better than O(n). I hope the question is clear now. 3) The question talks about pairs only so your second algo takes O(n^2) time which is brute force. Any improvements on that?
