Pregunta de entrevista
Entrevista de QA Automation Engineer
A dwarf-killing giant lines up 10 dwarfs from shortest to tallest. Each dwarf can see all the shortest dwarfs in front of him, but cannot see the dwarfs behind himself. The giant randomly puts a white or black hat on each dwarf. No dwarf can see their own hat. The giant tells all the dwarfs that he will ask each dwarf, starting with the tallest, for the color of his hat. If the dwarf answers incorrectly, the giant will kill the dwarf. Each dwarf can hear the previous answers, but cannot hear when a dwarf is killed. What strategy should be used to kill the fewest dwarfs, and what is the minimum number of dwarfs that can be saved with this strategy?
Respuestas de entrevistas
Think broadband communication. Exploit the capabilities of the communications medium. A minimum of nine dwarves can be saved based on the information provided in the original post I viewed. The strategy is for each dwarf to employ the expected language to communicate the color of their own hat to the giant, while simultaneously employing a vocal pitch protocol to indicate the color of the hat of the dwarf in front of him, high pitch for white and low pitch for black. The original post, indicates the dwarves may collude prior to the distribution of hats, so there is opportunity to negotiate such a simple broadband communication protocol. The tallest dwarf only has a 50/50 chance since the number of black and white hats in play is not known (rhetorical question, what are the odds the tallest dwarf's hat is black if he turns to find that all nine hats in front of him are white? I don't know, but odds are high that the giant is a sadistic bloke). The original post I viewed is here. http://www.businessinsider.com/toughest-job-interview-questions-2013-7#a-dwarf-killing-giant-lines-up-10-dwarfs-from-shortest-to-tallest-each-dwarf-can-see-all-the-shortest-dwarfs-in-front-of-him-but-cannot-see-the-dwarfs-behind-himself-the-giant-randomly-puts-a-white-or-black-hat-on-each-dwarf-no-dwarf-can-see-their-own-hat-the-giant-tells-all-the-dwarfs-that-he-will-ask-each-dwarf-starting-with-the-tallest-for-the-color-of-his-hat-if-the-dwarf-answers-incorrectly-the-giant-will-kill-the-dwarf-each-dwarf-can-hear-the-previous-answers-but-cannot-hear-when-a-dwarf-is-killed-the-dwarves-are-given-an-opportunity-to-collude-before-the-hats-are-distributed-what-strategy-should-be-used-to-kill-the-fewest-dwarfs-and-what-is-the-minimum-number-of-dwarfs-that-can-be-saved-with-this-strategy-11
What is the minimum number of dwarfs that can be saved with this strategy? 9 First of all, let's numerate the dwarfs as N1, N2, N3, etc. with N10 being the tallest. Now, N10 will state the color of N9 as his own answer, "My hat is WHITE". Based on this answer, N9 will state his color with a positive statement if the color of N8 is the same as his, "My hat is WHITE". Based on N8's answer, N8 knows that his color is WHITE, now, he will state his color depending on N7. Let's say N7 is black, so N8 will state, "My hat is NOT BLACK". N7 knows that his color is BLACK, but N6 is white, so he will use a negative statement, "My hat is NOT WHITE" and so on. Full example: N10 = BLACK N9 = WHITE N8 = WHITE N7 = BLACK N6 = WHITE N5 = WHITE N4 = WHITE N3 = BLACK N2 = BLACK N1 = WHITE N10: My hat is WHITE (Dies) N9 = My hat is WHITE N8 = My hat is NOT BLACK N7 = My hat is NOT WHITE N6 = My hat is WHITE N5 = My hat is WHITE N4 = My hat is NOT BLACK N3 = My hat is BLACK N2 = My hat is NOT WHITE N1 = My hat is WHITE N10 will have a 50/50 chances of survival... I'm sorry N10, I couldn't save you :'(
Jorge R en
the question does not mention that there will be equal number of white and black hats !
not a genius en
Since they do not know, how many black or white hats there are, the following strategy will save min 5 dwarfs: The first dwarf asked names the color of the hat of the 2. dwarf. He has a 50% chance that that's correct. Anyway, the second dwarf then knows, the color of his hat and names it correctly. the 3. dwarf again names the color of the hat of the 4th dwarf and has a 50% chance to survive, while the 4th dwarf can name the correct color of his hat. a.s.o. => all dwarfs with an even number will survive and all the others have a 50% chance
Each dwarf can state the color of the hat worn by the dwarf in front of him, but the thing is, that color may not be the color of his own hat.So he may be killed by the giant.In that case, as mentioned above all odds should tell the color of next so that all even number will be alive and they have 50% chance of surviving.
So reading the answers provided they all have some assumptions e.g. that there are as much white hats as there are black hats. I think that Christian's comment on aug 13-2013 was very close but I'm thinking about communication integrity confirmation techniques. One of them is using a parity bit to confirm the message was correct. This could be applied right here to save at least 9 with a 50/50 chance of saving the 10th (and tallest dwarf). I will explain it but for ease of explanation I will use binary 1 and 0 for black and white. Number 1 being black hat and number 0 being white hat. Let's say we got a (random) hat sequence of 0001011101 with the tallest dwarf on the right and the shortest on the left. While colluding prior to the distribution of hats the dwarfs agree upon even or uneven parity. This means the total amount of 1's (black hats) must be even or uneven including the parity bit. In this case the 10th dwarf will count as parity bit. So if we'll take an even parity, the number of 1's must be an even number in total. When the questioning starts the tallest dwarf will see the hats in front of him being 000101110. The tallest dwarf counts four 1's (black hats) so to make the parity even he has to say 0 (white hat). He will get killed but the dwarfs in front of him will know the parity bit is 0 so the 2nd tallest dwarf will see the hats in front of him as 00010111. He will also count 4 and knowing that the dwarf behind him said 0 he'll know that the total amount of 1's is an even number thus concluding he has a 0 (white hat) and will state he has a white hat. Same goes for the rest of the dwarfs and so 9 will be saved. The 10th would've been saved it the dwarfs agreed on an uneven parity. That's why there's a 50/50 chance the 10th will be saved. I'm pretty confident this is the answer but if you want to understand it better (maybe my explanation is a bit vague) go search for "parity bit" on the internet.
@JustJanek- Your solution is close, but not correct. Every dwarf needs to consider the parity of a number composed of all the following dwarfs and all the dwarfs behind. The first dwarf says the parity of the 9-bits number in front of him. Assuming that all the other dwarfs know the trick and they stay alive, each dwarf needs to compare the initial parity with the parity of an 8-bit number composed of the hats in front of him and the hats behind (assuming that the dwarfs behind gave the right answer), if the parity is the same, he knows that he has a white hat, otherwise he has a black hat.
You can save 9 dwarves at least. Dwarves agree that the tallest one says he is wearing black hat if he sees odd number of black hats in front of him and he says white hat if he sees even number of black hats in front of him. So, the tallest one has 50-50 chance of survival and other dwarves survive 100%.
If each dwarf say the colour of hat in front of him..(dwarf can hear previous answer) then at least five people are saved.
@Kristen - you have so underthought it! What if the dwarf behind you says "black" and the dwarf in front of you has a white hat????
What is the minimum number of dwarfs that can be saved with my strategy? - 10 My strategy doesn't make any unmentioned assumptions (such as equal number of white and black hats, etc). At the same time, it doesn't add any unmentioned constraints either. The strategy is simple to the point of appearing simplistic. But it meets all the requires. The strategy is: When asked, every dwarf answers "Not RED". This is not an incorrect answer and the Giant, if he were an honourable giant that is :), would have to let the Dwarf live. On a different page altogether, I went through all of the above answers. Not to sound patronizing, but some of the solutions were quite brilliant. I was thinking if I could even come up with that even after years of pondering. But I must admit, all of the above strategies are made by an outsider (ie. us) who is not impacted by this fate. Whereas in the casestudy, the strategy has to be devised by the 10 dwarfs, who face the impact of this strategy. Not to bring in factors such as emotion, the bell curve distribution of intelligence, and other such anal considerations. But I thought it was important to bring in Game Theory, and that all Dwarfs are rational, and that all rational people do not want to harm themselves in any way. In other words, when a strategy's success depends on the conformance to that strategy by ALL the participants, the strategy should also benefit ALL the participants if it is to succeed (or in the least, should not harm even ONE participant). In all the above strategies, since even in the best case scenario the poor Tallest Dwarf has only a 50% chance of living, can we assume that he would conform to this strategy?
Well, Once the dwarfs are lined up in descending order. Without any kind of assumption, 9 people can be saved with a 50% probability of the 10th (tallest). Here is how it can be achieved, The strategy is to call the color of odd number of hat. Say for example, the tallest dwarf sees 3 Black and 6 whites, it will call out Black(it may or may not die with 50% chances). Now, the 9th tallest dwarf knows what the 10th dwarf could see and if it (9th) dwarf sees the same odd number of black hats, it will know it has white hat. Next, 8th dwarf knows number of odd (black) caps 9th dwarf could see and if it(8th) finds 1 less black cap, it would know it is wearing a black cap.. and so on. 10- White (calls out Black because it sees odd number of black hats) -dies(assume) 9- White (calls out White because it could still see 3 black hars) 8- Black (sees that there is one less black hat as mentioned by 9th, hence identifies that is wearing black) 7-White (calculates that 8th is wearing black and he could see 2 black, hence identifies itself wearing whiteO( 6-White 5-White 4- Black 3-Black 2-White 1-White Sorry if there is confusion in the way I have answered.
all can b saved... They will exchange their hats in Circular form...person10 can see the person1 color of hat and after exchange every dwarf will tell color to their previous ones and person 10 knows the color before changing it from dwarf 1. d10->d9->d8->d7->d6->d5->d4->d3->d2->d1->d10 CIRCULAR EXCHANGE OF HATS
janmanjay banerjee en
First lets look at number of back and white hats...To satisfy the condition "black and white" hata there is minimum one black or white hat present. So its minimum (9 black & 1 white) or (1 white & 9 black) hat being distributed randomly amoung dwarfs. The story says dwarfs are alowed to speak before execution. Lets make a strategy of saying only one colour before execution eg) black or white. Minimum probability of (9 black & 1 white) hats and all the dwarfs say "white"...In this case one is saved but all nine dead. If all dwarfs say "black"..Nine are saved but one is dead. The same applies for the minimum probability of (1 black and 9 white)hats. Thus minimum one dwarf is saved and maximum nine dwarfs can be saved.
Each dwarf should pronounce color of hat of dwarf before him. This way they can save atleast 9 dwarf out 10.
Shuaib ahmad en
There is only one strategy, does not matter how many white or black hats they are. They are always 9 dwarfs that could be saved. You just have to know about XOR.
Well... In my opinion all can be saved! The tallest dwarf can see 9 hats in front of him ( 4 white and 5 black hats or the other way around). Then he knows the color of his hat because there has to be 5black and 5 white hats. The next dwarf by the size just has to believe to the tallest dwarf that he is right-(and he is) In addition ,he can see 8 hats in front of him and when he adds the color of the tallest dwarf he knows which color he has. Again,the 3rd one in a row knows about 2 colors before and can see 7 colors in front of him.And when he adds 2 colors he already had heard of -he knows total number of 9 hats as well.So he just has to see which color is less presented and that is the color of his hat. And so on until the last dwarf...All saved
Easy. The tallest is the only one that cannot be saved so instead of trying to guess his color, he yells out a sequence of letters starting from the shortest like BWBBBWWBB. Next :)
Your going to definitly get 9 because when the dwarves collude the tallest tells the next tallest his hat color and so on down the line. Now you have a 50/50 chance that the tallest will get his color correct and live so you have 9 with a 50% chance of 10
There are 2 different strategies, each dependent on whether there are an even or odd number of white and black hats in play. The minimum number of dwarfs that can be saved with the correct strategy is 9.
Don't over-think it. Each dwarf simply has to state the color of the hat worn by the dwarf directly in front of him. The tallest would have to sacrifice himself in order to save the other 9.