Microsoft Interview Question Software Engineer / Developers
Team: Bing
Country: India
Interview Type: In-Person
This answer is almost correct.
Some corrections: "which color occurs even number of times"
this is not correct since there are 100 prisoners and the number of hats are both even or both odd.
Actually first prisoner should count the one color (say it is agreed to be RED) and should say RED if the reds are even or Black if the reds are odd.
In any case there will be even number of hats that can be seen by the last prisoner.
Say there are 96R and 4B. If the last prisoner has a R had he sees 4B, if he has a B, he sees 96R.
Say there are 95R and 5B, if last prisoner has a R he sees 94R, if he has a B, he sees 4B.
Hence, shouting the number of even hats would work with the last prisoner having 50% chance of survival.
Artur can you give and example when this will not work?
since all are known of this problem one day before,
CODE FOR 1ST MAN-- HE WILL COUNT NO OF REDS AND they will agree that that red== even and blue== odd ONLY FOR THE FIRST MAN...
first will sacrifice himself with 0.5 prob , counting the number of RED's in line excluding him.
If this number of red's in line is even he shouts RED (as per our code red== even and blue == odd for 1st person) and if it is odd he will shout BLUE ...
the person next to him will know what his color is --- as follows
for ex, the 1st person shouted red
below is what 2nd person shud cal
-info from 1st person means no of reds of all persons infront of him and including him
is even
-he will count if no of persons infront of him is even or not
-if it is even he will say blue else red
EACH PERSON SHUD LISTEN AND KEEP TRACK IF NO OF REDS IS EVEN OR NOT
FROM WHAT 2ND PERSON IN LINE SAYS TILL HIS NUMBER COMES (he can hear ryt so he can keep track)
99 prisoners 100% chance to alive, 1 prisoner 50% chance to alive
Define: Red =1; Blue = 0
The 100th will announce: (1st + 2nd + 3rd +...+ 99th) mod 2
So, the 99th, who can see the value of (1st, 2nd, 3rd.., 98th), and total of them, will know his value (color of hat)
... the same to other prisoners
Since last prisoner can see hat of the rest of the prisoners, he should count number of blue hat and shout say "10 blue", now he has 50% probablity of survival (he anyways have 50% probablity of survival), irrespective of that, rest of the prisoner will know that there are 10 blue hat and 89 red hat remaining so the second prisoner can count how many blue hat are remaining ahead of him, if it is 9, he has a blue hat, if it is 10 he has red hat, and so on. So this way on an average they can save 99.5 lives.
First 2 come out and form a line, the next one puts him self in the middle of the first 2 if their hats are different, if not he goes to one side. Each prisoner that comes to the line should put him self where there are 2 prisoners with different color hats.
This looks like the only correct answer, since all other answers assumed something that wasn't in the question, i.e that prisoners can say anything else except the color of their hat. But even this solution suffers in one corner case. That is when there are 99 hats of one color and only one of the other color, and that prisoner is the last to stand in line. To cover this case, in the beginning one prisoner should pick two other prisoners with different hat colors to start the line (by pushing them in front of the others).
He should probably say which one is odd because the commander most likely printed out an even number of each hat. This improves the likelihood of the man in the back surviving.
Unless you fix total number of a specific color hats out of 100, every solution will yield 50% chance of survival, which is no good than a prisoner saying random color.
If we forget algo finding here, one clever solution would be each prisoner telling his neighbors colors of their hats and this yields 100% chance of survival. I just wonder if this cheat is allowed.
it did not say what kind of line. you assume it is vertical. but it can be horizontal, in which case the person next to you can turn, tell you what color your hat is, your repeat it. you look to your left say that persons color, they repeat it, so on and so forth. no one gets shot. or did it occur to anyone they may be standing in front of a glass or mirror. or if in a vertical line they can turn and tell each other
Let's just define one strategy for prisoners. Prisoners decide this strategy. If the prisoner announces the answer immediately, then the next prisoner is having a blue hat. And if there is a delay(like 2 mins- any sufficiently large value) , then the next prisoner is having a red hat. Using this strategy, only the backmost prisoner is at a loss(as he has no one to tell him), so he has to guess(50%).
So we can save n-1 prisoners
99 prisoners 100% chance to alive, 1 prisoner 50% chance to alive
Define: Red =1; Blue = 0
The 100th will announce: (1st + 2nd + 3rd +...+ 99th) mod 2
So, the 99th, who can see the value of (1st, 2nd, 3rd.., 98th), and total of them, will know his value (color of hat)
... the same to other prisoners
My question: Can prisoner allow to speak any word beside the color that s/he of the hat that s/he wearing or not?
If yes:
Let define 0 for Red and 1 for Blue. Every prisoner will say his color followed by number 0 or 1 depended on the next prisoner is wearing. The first prisoner will have 50% chance to survive and the 99 prisoner will be 100% chance.
If No:
They better use leg signal. :) By if the back prisoner kick the next prisoner with his/her right foot then it means red otherwise blue.
What do you think? :p
The one in the back will just say which color occurs even number of times. Than all th rest can figure out what his color is. The one in the back will die with %50 probability rest will survive for sure.
- Rayden December 06, 2011