Hi Abhi,
About Sol2: The only question that can be asked to P is "do u know Q?", for some Q. No one knows who the celebrity is, it's our job to find out by asking these questions. How we eleminate a person for each question is not clear to me, can you explain that. I think the assumption can be that, there's only one celebrity. And celebrity also may kn ow some of the people. If celebrity does not know anyone then your the solution is easy and we can elimiate one person for every call. I came up with this solution, please point out any mistakes. This is similar to a depth first search in directed graph where each vertex is a person and a directed edge connects vertices P to Q if P knows Q. Maintain a list of to be examined people T which is originally empty. First take any person P1 and add all people whom P1 knows into T. Color those vertices as grey (originally all vertices are white colored). Now, the celebrity has to be in T. Take first vertex from T and enquire from him about whom he knows from T, if he doesn't know some one from T then that guy can't be a celebrity so delete him from T. Continue this process. Ultimately we'll be left with one person in T. Just everyone if he knows that one person in T, if everyone knows him then he is the celebrity else there's no celebrity. I am not sure about the time complexity but I think it takes O(E) time where E is the number of edges which in the worst case is O(n^2). This problem is same as finding the "sink" node in a directed graph, where sink means every node has an edge to it. Any more ideas ? About Sol3: From where I got the problem, it asks for linear time solution. I did not understand your hashing solution, can you please elaborate on that. First question is same as Sultan's dowry problem, so I consider it solved. Thanks to guys here for pointing out the resources on this. Abhi wrote: > Sol1: > I'm not sure of the perfect algorithmic answer. But here is what I feel > can be done. > It is not necessary that the Best programmer should be selected. right? > So in this case the interviewer need to decide on the min. threshold > for selection. Any first programmer passing that would be selected > leaving others being not interviewed and saving interviewer's time ;-) > > Sol2: > Here I guess the question for P would be that "is Q celebrity?" > One doubt here, if by chance P is the celebrity, what would he answer? > just No or something else also? > If he is going say that I'm celebrity then our time complexity comes > down considerably. > In this case in every call we can eliminate two people, so we can find > the celebrity with-in n/2 calls. > > In case the reply is just binary - Yes or No, then we can elimiate only > 1 person in every call. So it would take n-1 calls. > Simplest would be to keep P=1 and interate Q from 2 to n. > So time complexity is O(n) > > Sol3: > sort and search is simple way with n lg n complexity. > If there is no memory constraint then, We can create a hash. > Read through the array and keep adding it to the hash and at the end > just go through the hash to find the required pair. The time taken > would be N + N i.e. time complexity of O(n) > > -Abhishikt
