BitTorrent

## Interview Question

QA Automation Engineer Interview San Francisco, CA

`BitTorrent`

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

## Interview Answer

16 Answers

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

the question does not mention that there will be equal number of white and black hats !

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

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.

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

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.

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

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.

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

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

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 :'(

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?

## Add Answers or Comments

To comment on this, Sign In or Sign Up.

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.