Microsoft Interview Question Software Engineer in Tests
You missed the part when 1 and 2 don't know each other, any of them can be the celebrity.
gcm gives the 100% correct answer
@"Anonymous on August 02, 2009", we ask P1 the question that "Do you know P2?" If yes, then P1 cannot be the celebrity; if no, then P2 cannot be the celebrity. As a result, we can always eliminate one person for one question, and therefore we just need (n-1) questions.
Reply to "Anonymous on August 02, 2009"
there cannot be a case when 1 and 2 does not know each other and still one of them could possibly a celebrity.
I suppose you misspelled while posting your comment.
http://www.cs.sunysb.edu/~skiena/373/notes/lecture22/lecture22.html
Among n people, a celebrity is defined as someone who is known by everyone but does not know anyone. We seek to identify the celebrity (if one is present) by asking questions of the form ``Hey, x, do you know person y?''. Show how to find the celebrity using O(n) questions. Note that there are possible questions to ask, so we cannot ask them all.
What if we ask 1 if she knows 2, and 2 if she knows 1? If both know each other neither can be a celebrity. If neither know each other, neither can be a celebrity. If one of them knows the other, the former cannot be a celebrity.
Thus in two questions we can eliminate at least one person from celebrity status. Thus in 2(n-1) questions, we have only one possible celebrity. It is now possible to check whether the survivor is really a celebrity using n-1 additional queries, by checking whether everyone else knows them.
the question was the rest of the other people know only the celebrity and no one else...
u have asssumed that the rest of the people know others too.....
LOL.
Read again himanshu. The case when neither knows each other is covered.
btw, no where does it say the rest of ppl don't know other ppl. In fact, this is a classic question and the standard interpretation is that ppl know other ppl (other than celebrity).
ok. there are n people..let us say 1,2,3,...N where anyone can be the celebrity or not at all.. assuming the everybody knows none other than celebrity, celeb knows none
ask the 1st person if he knows he 2nd person
if he says yes then definitely... 2nd person is a celebrity//
if he says no then 2nd is not a celebrity and there is a chance that 1st may be a celebrity..
continue this till u find the celebrity..
if u reach the nth person..
and if the nth person is not the celeb ask if the nth person knows the 1st person.
if yes the celebrity is the 1st person and if not noone is the celebrity..
I AM I RIGHT??
No himanshu... you are wrong. If everyone knew only the celebrity and not also other people, then the problem is.. well not a problem at all. It isn't a question worthy of any thought.. it becomes too trivial.
The guys who've written above are right.
n people, there is one celebrity among them.Define them as 1,2,3,4...n. First,ask the question: does 1 know 2, if yes, then 1 is not the celebrity, just delete 1, if no, then 2 can't be the celebrity, we delete 2. then we have 1 or 2 left, then ask if the left one know 3, we could always delete one person each time. so we would need n-1 questions to delete n-1 people. Am I right??
- gcm August 01, 2009