Goldman Sachs Interview Question
Developer Program EngineersCountry: India
Interview Type: In-Person
Let A B C in line with C in front. Let D be somewhere else.
Now if B and C has same colors. A can immediately speak his color. B and C will know their colors and will speak theirs. Finally D will.
If both has different, A will be silent. After some time, B will realize his condition and can guess that his color is different from C's.
Therefore B will speak out his. C will listen B's answer and will come up with his color. Eventually all the prisoners will go free.
for the second case, when B and C are wearing different colored hats. They manage to guess their own color, But what about A and D in that case ?
if all sittinging same line but in same direction like A,B,C if A&B or B&C wearing same color hats.at that time if A & B (red or blue)same color then A will know all remaing three people color then he will tell.
otherwise B & C same color(red or blue) at the time B will know C also having same color and reamin two A & D are different color the that he tell to jailer.
If in a line where A can see B & C. And B can see only C. D is away.
A -> B -> C
If A see red-red or blue-blue then he knows his is blue or red respectively. If A sees red-blue or blue-red keeps silent.
If A keeps silent then B knows the hat on his is different than than on C. So, if B sees red on C's head he know his is blue and vice versa.
All prisoners go free.
Question looks too simple... and the 4th prisoner has no role in the solution... I believe some constraint is missing in the question.
Hey satish. Everything is given in the problem. See the solution below.
If in a line where A can see B & C. And B can see only C. D is away.
A -> B -> C
If A see red-red or blue-blue then he knows his is blue or red respectively. If A sees red-blue or blue-red keeps silent.
If A keeps silent then B knows the hat on his is different than than on C. So, if B sees red on C's head he know his is blue and vice versa.
All prisoners go free.
Here is the actual puzzle :
An executioner lines up 100 prisoners single file and puts a red or a blue hat on each prisoner's head. Every prisoner can see the hats of the people in front of him in the line - but not his own hat, nor those of anyone behind him. The executioner starts at the end (back) and asks the last prisoner the colour of his hat. He must answer "red" or "blue." If he answers correctly, he is allowed to live. If he gives the wrong answer, he is killed instantly and silently. (While everyone hears the answer, no one knows whether an answer was right.) On the night before the line-up, the prisoners confer on strategy to help them. What should they do?
If the third prisoner sees that both prisoners in front are wearing same-colored hats, then he knows he must be wearing a different-colored hat.
- rax March 05, 2013If he does not, and does not guess correctly, then the remaining two prisoners must be wearing a red and a blue hat. The second prisoner can see the hat in front of him and knows that his own hat must be the opposite color. So if he sees a red hat he answers blue and vice versa.