Microsoft Interview Question for Software Engineer in Tests

Comment hidden because of low score. Click to expand.
1
of 1 vote

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??

Comment hidden because of low score. Click to expand.
0

Looks right to me.

Comment hidden because of low score. Click to expand.
0

You missed the part when 1 and 2 don't know each other, any of them can be the celebrity.

Comment hidden because of low score. Click to expand.
0

gcm is right, think again.

Comment hidden because of low score. Click to expand.
0

correct and smooth answer by gcm :)

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

If we don't know whether or not there's a celeb, n-1 is not enough.
In the worse case, 2*(n-1), i.e. the last guy is the celeb, we have to ask him if he knows everybody else.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

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.....

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0

where does it say that the rest of the people know each other???

Comment hidden because of low score. Click to expand.
0

LOL.

I guess they are just visiting this new town and came to the party uninvited.

It does not mean everyone knows everyone else, btw, it only means ppl might know some more ppl other than the celebrity.

btw, where does it say that they don't know other people?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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??

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

ya i also thought of that after posting..

Comment hidden because of low score. Click to expand.
0
of 0 vote

K my answer with the assumption everyone other than celebrity may know some of the others but know the celebrity for sure. The answer is n-1 if we know there always exists a celebrity and if there exists no celebrity it is 2(n-1) want explanation?

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the person can ask each one whether he knows anyone. Others will be knowing at least one person( celebrity) but celebrity wont know anyone. so we need to ask max of N people. so its is O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

i guess gcm's explanation is ok...as everytime we keep getting rid of one person...so finally we need (n-1) questions...right? so the answer must be (n-1).

Comment hidden because of low score. Click to expand.
0
of 0 vote

you are right.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Lets say you have, by luck, the first person you pick is the celebrity himself; then in order to verify if he/she is the celebrity, we'd have to ask n-1 questions. Since the question asked is the minimum number of questions required, n-1 is the right answer.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Anon on September 08, 2009:
I like your smart approach. Nice one ! Thanks.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.