wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> microsoft >> MS INterview Question
        
(Message started by: Joel Burlingham on Apr 12^th, 2003, 10:25am)

Title: MS INterview Question
Post by Joel Burlingham on Apr 12^th, 2003, 10:25am

There are 10 dwarfs of different heights and they get captured by a giant. The giant says, "Tomorrow I am going to put either a red feather or a blue feather on your head. You won't be able to see it. You will have to guess your feather. If you guess wrong, you die. If you guess right you live. I am going to line you up like this:"

----->

|
| |
| | |
| | | |
| | | |

So the tallest guy can see everyone's feathers. But he can't see his own. He will have to either say red or blue. So the dwarves have a night to figure out a plan of what they can do.

What is the max guaranteed # of dwarves that can be saved?

Title: Re: MS INterview Question
Post by BNC on Apr 12^th, 2003, 10:38am

duplicate of this riddle (http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#singleFileHatExec)
It's a nice riddle, BTW!

Title: Re: MS INterview Question
Post by Raymond on Apr 13^th, 2003, 9:24pm

if I'm thinking it right this might be a possible solution:
- If we let the dwarfs stand in ascending order then dwarf2 can see dwarf1 and so on......so this way we can save 9 dwarfs at least....

does it makes sense?...

Title: Re: MS INterview Question
Post by aero_guy on Apr 13^th, 2003, 11:42pm

Check the linked discussion. Yours is a seemilngly common mistake.

Title: Re: MS INterview Question
Post by Joel Burlingham on May 14^th, 2003, 9:58am

I'm still not sure about this one.....any help is appreciated.....

Title: Re: MS INterview Question
Post by Ganon on Feb 8^th, 2005, 11:09pm

9. Though the 10th guy has a 50% chance.

[hide]
Think parity bit.
Let red feather = 0.
Let blue feather = 1.
Have the tallest guy count the number of blue feathers mod 2 and say the corresponding feather (ie. say red if he counts even number of blue feathers and blue if he counts an odd number of blue feathers).

eg. if the dwarves are 1011011010 (10th guy on left)
Then the 10th guy counts 4 blue feathers and says red (blam, he's dead, too bad).
The 9th guy knows there are an even number of blue feathers and sees an even number of blue feathers, so he says red and is happy.
The 8th guy knows there are an even number of blue feathers left and sees an odd number of blue feathers, so he says blue.
The 7th guy knows there are an odd number of blue feathers left (because the 8th guy's was a blue feather) and sees an even number of blue feathers, so he says blue.
...
[/hide]