A Microsoft Interview Question (aka basic Bayes' Theorem)

[Ed Miller]

If you don't know or understand Bayes' Theorem, this problem is for you. If you do, this problem will be trivial, and I ask you not to answer. Really, it isn't worth your time. /images/graemlins/smile.gif

When I worked at Microsoft, I used to ask this as an interview question. Most of the candidates struggled with it. Hopefully you will figure it out quickly. Also, try to figure it out on your own before you read anyone else's answer.

You and a friend are playing Russian Roulette with a six-chambered revolver. You place two rounds in adjacent chambers and give the wheel a final spin. You hand the gun to your friend. He pulls the trigger...

Click. He hands the gun to you. You have a choice. You can spin it again, or you can simply shoot the next chamber. Does it matter which one you choose? If it does, why?

[dtbog]

Isn't this sort of like the Monty Hall problem?

-DB

EDIT: Never mind, you said "adjacent chambers". That changes things.

[snowbank]

Wouldn't you want to spin it again, because once he hands the gun to you, you would have a 2/5 chance of shooting youself, because the chamber before was empty. If you spun it again, you would have a 2/6 chance of shooting yourself.

Is this correct?

[lossage]

[ QUOTE ]
Wouldn't you want to spin it again, because once he hands the gun to you, you would have a 2/5 chance of shooting youself, because the chamber before was empty. If you spun it again, you would have a 2/6 chance of shooting yourself.

Is this correct?

[/ QUOTE ]

Not quite, but you're close. Like the Monty Hall problem, this is an exercise in conditional probability. Think about this: Your friend just pulled the trigger and hit an empty. How many total states could the revolver have been in when your friend shot, and how many of these cause you to blow your own brains out?

[VBM]

ok, dont' laugh you bayesian snobs, but i drew 6 empty holes in a circle and filled in 2 of them. there are 4 possible states its in when your friend pulls the trigger and didn't kill himself. afterwards, there are only 3 possible empty chambers that won't kill you; b/c if he was on the one just before the filled one, you're on the filled one and you're fcuked. your chances are 3/6 which is not as good as 4/6 so you should spin again and point it at your friend for convincing you to play this stupid game.

[lossage]

[ QUOTE ]
there are 4 possible states its in when your friend pulls the trigger and didn't kill himself. afterwards, there are only 3 possible empty chambers that won't kill you; b/c if he was on the one just before the filled one, you're on the filled one and you're fcuked. your chances are 3/6 which is not as good as 4/6 so you should spin again and point it at your friend for convincing you to play this stupid game.

[/ QUOTE ]

I disagree with the "3/6" number, but I agree with turning the game around on your dumbass friend. I'm pretty sure that happened on 24 a couple of seasons ago.

[DQPaulie]

First look, it is 4/6 to live on first shot and 3/5 to live on second shot. 66% is higher than 60% so spin? But looking at where the first shot could have landed, the next shot will kill 25% and let me live 75% if i just pull the trigger. So I guess no spin ......click.

[VBM]

[ QUOTE ]
But looking at where the first shot could have landed, the next shot will kill 25% and let me live 75% if i just pull the trigger. So I guess no spin ......click.

[/ QUOTE ]

huh? i got the 1st part on 4/6 vs 3/5 (not 3/6 like i thought)...a little help w/ this part?

[rt1]

i drew this out on a piece of paper and it seemed rather easy to me. and im not smart.

your friend shot and hit a blank. that means that no bullet was about to fire so therefore the trigger wont be on the next bullet or the next empty slot. leaving 1 bullet and 3 empty slots (4 slots total) left for the next pull. 1/4 you kill yourself, 3/4 you live.

if you choose to respin, you land on a bullet 2/6 times or 1/3 of the time.

so, i dont respin, i just pull the trigger.

[RJT]

If you spin again you have a 4/6 chance of surviving. The chance that your friend had chamber next to live one is 1 / 4. That leaves 3 /4 chance it wasn’t next to live one. 3 / 4 = 9 /12. 4 /6 = 8/ 12. Chances are better not to spin?

[TomCollins]

This is all it takes to get a job at MS? Wonder what went wrong.

Number the chambers 1-6. 1-2 are loaded. So if your friend shoots and its empty, you know that he had 3-6. Only chamber 6 has the chamber next to it loaded. So your chances are 1/4 of dying.

On the other hand, if you choose one randomly, your chances are 2/6 = 1/3, which is worse.

So you shoot without turning the chamber.

[mr pink]

i'll give it a shot...after your friend blanks on his first shot, you've got at best 3 more blanks and at worst 0. there's really only 1 chamber that you have to be worried about, the one adjacent to the 2 remaining bullets...4 chambers - so 1/4 times, you'll be dead, and 3/4 times you'll survive. i'd rather take a 25% shot after my friend than another spin looking at 33% (2/6).

peace - jeff

[smartalecc5]

I havent read any replies but it is best to spin it again because if you spin it again you have 2/6 chance of being killed, but if you dont you have a 2/5 chance of dying.

2/6 < 2/5 so you should spin.

[TomCollins]

The amount of incorrect answers on this trivial problem baffle me.

[smartalecc5]

how is my response not correct?

[RJT]

Had he shot himself, are you better off spinning or not?

[dtbog]

[ QUOTE ]
The amount of incorrect answers on this trivial problem baffle me.

[/ QUOTE ]

You're obviously superior to those who knew the answer but chose not to post... and certainly leagues above anyone who attempted the problem and got an incorrect answer.

Enjoy that little ego boost!

-DB

[dtbog]

[ QUOTE ]
Had he shot himself, are you better off spinning or not?

[/ QUOTE ]

For the love of God, spin! /images/graemlins/smile.gif

If he shot himself, you're 50/50 to die.

-DB

[dtbog]

[ QUOTE ]
how is my response not correct?

[/ QUOTE ]

Your response is wrong because you didn't take into account the information that you learned from your friend surviving the pull of the trigger. Remember, the bullets are in adjacent chambers.

Think about that.

-DB

[RJT]

I know - it was a joke (or an attempt at one).

[dtbog]

[ QUOTE ]
I know - it was a joke (or an attempt at one).

[/ QUOTE ]

Then the answer is "don't spin, just clean up all of the brains on the floor and then run like hell!"

-DB

[VBM]

ok, feeling dumb...i get it now...and i think you guys dont' wanna get into a russian roulette game w/ me now!!! lol...

[RJT]

[ QUOTE ]
[ QUOTE ]
I know - it was a joke (or an attempt at one).

[/ QUOTE ]

Then the answer is "don't spin, just clean up all of the brains on the floor and then run like hell!"

-DB

[/ QUOTE ]

See things aren't always so obvious. At first we both thought the answer was to spin after he shot himself. Now that you say it - the answer is to not spin and get the heck out of there. I am not quite sure of your logic regarding cleaning up the brains, though. Nite bud.

[pzhon]

[ QUOTE ]
[ QUOTE ]
Had he shot himself, are you better off spinning or not?

[/ QUOTE ]

For the love of God, spin! /images/graemlins/smile.gif

If he shot himself, you're 50/50 to die.


[/ QUOTE ]
Though this variant can be understood by considering two simple cases, it isn't easier than the original. The 1/3 chance to die from from spinning is the weighted average of this 1/2 and the probability from the original question, firing after the first chamber was empty. Since 1/2 is greater than 1/3, the chance to die from firing without spinning (1/4) must be less than 1/3.

[Marm]

Actually, that helped me understamd the 'states' end of the problem. Thanks.

Been up a long time, i'm moving slow......

[Marm]

Wrong, You are 50/50 to die if you don't spin, but spinning has only a 1/6 chance of dieing now, since one of the roudns has been fired, and can now be considered empty.

But I agree, leaving is the best idea.

[JoshuaD]

there are 4 pairings that start with a blank hole, we're on one of those. 1 of those pairings will kill me, so it's 1/4 to die if I don't spin, and 1/3 to die if I do.

That said, what happens if I shoot a blank? No one's looking past step one (I haven't yet either, so we could end up w/ the same result, I just think it's interesting):

So my chance of getting blown away with

No Re-spin: 1/4 - 3/4 * 1/3 + 1/4 * 1/6 = 1/18
Re-Spin: 1/3 - 1/9 + 1/27 - 1/81... = 1/2


So you should definitely, definitely re-spin.

edit: this math is wrong, fixing.

[pzhon]

[ QUOTE ]
Wrong, You are 50/50 to die if you don't spin, but spinning has only a 1/6 chance of dieing now, since one of the roudns has been fired, and can now be considered empty.


[/ QUOTE ]
Thank you for pointing out that triviality for those who missed it. However, when I said "The 1/3 chance to die from spinning..." I still referred to the original situation, spinning with 2 bullets in the gun.

[ QUOTE ]

But I agree, leaving is the best idea.

[/ QUOTE ]
That wasn't my point at all. I pointed out that the two variants must have probabilities differing from 1/3 in opposite directions. That is not trivial.

[Supern]

If you spin you have 4 chambers without a round and
2 with a round. You have 4/6 to survive when you pull the trigger.

When you just have pushed the trigger:
There are 4 empty chambers. Lets name them 1-4.
If he clicked chambers 1-3 you will get an empty chamber.
If he clicked chamber 4 you are in trouble. /images/graemlins/smile.gif
That means you will survive 3/4 times.

The conclusion is: just pull the trigger (75% > 66%)

[JoshuaD]

Alright, my math up above was all done in my head, and was wrong. Here's the actual right answer:

Assuming every previous shot is a blank, here are the chances on each round of getting blown away:

1) 1/3
2) 1/4
3) 1/3
4) 1/2
5) 1

HOWEVER, this answer suggests flawed results:

If we don't assume every previous shot is a blank, here are the chances of the person getting blown away on each round if there is never a respin, (That is, you're at round one, what are the chances of the gun going off on each round).

1) 1/3
2) 2/3 * 1/4 = 1/6
3) 2/3 * 3/4 * 1/3 = 1/6
4) 2/3 * 3/4 * 2/3 * 1/2 = 1/6
5) 2/3 * 3/4 * 2/3 * 1/2 = 1/6

So, if you're firing on all even rounds, and he's firing on all odd rounds, you get blown away 1/3 of the time, he gets blown away 2/3 of the time. So handing him the gun first was definitely a good idea.

However, if you assume he already shot the first round and he missed, AND if there is never a re-spin, the chances of the gun going off in each round is:

1) 0 < (already happened)
2) 1 * 1/4 = 1/4
3) 1 * 3/4 * 1/3 = 1/4
4) 1 * 3/4 * 2/3 * 1/2 = 1/4
5) 1 * 3/4 * 2/3 * 1/2 = 1/4

Giving you even money on getting blown away and not.

The problem here is, I can't remember how to figure out your chances of getting blown away if you just spin between every shot, but I'm pretty sure the person who shoots first is at a disadvantage. If that's true, you should take the even money proposition in Ed's example.

However, if you can spin the gun whenever you want, you should spin everytime after you shoot, and never after he does.

In short:

If you can spin whenever you want, optimal strategy is to let him shoot, then you shoot, then to re-spin.

If you have to decide before he shoots whether to always spin or never spin, you should choose to never spin.

And to answer Ed Miller's exact question: You shouldn't spin. (I assumed it's worse than even money for the first shooter to go back and forth spinning then shooting).

[Ed Miller]

Then the answer is "don't spin, just clean up all of the brains on the floor and then run like hell!"

Don't forget to take his wallet and watch too.

[Ed Miller]

This is all it takes to get a job at MS? Wonder what went wrong.

/images/graemlins/smile.gif

The majority of my interview candidates really struggled with this question. To me it shows how superior the Microsoft style of interviewing (solve these problems now, please) is to a more traditional style ("So, tell me about a time when you faced a challenge, and how did you overcome it, blah blah blah..."). I learned stuff in five minutes about the candidate that a traditional interviewer couldn't know in an hour or more.

You'd be surprised how many people show up with "solid" resumes for CODING positions, yet balk when you ask them to write a function in C that calculates the fibonacci series. "Can I do it in pseudocode?" "Do I have to get the syntax right?" "Can I just tell you how to do it?"

[JoshuaD]

Hey Ed,

Is my answer right? I'm not familiar with the theorem you mentioned in your original post, so I'm not 100% confident in my answer.

Thanks,

Josh

[TomCollins]

In my expirience with MS, mediocre female and minority candidates from my university (not MIT), were the only ones who ever got hired. I was pretty sure that I was there for song and dance, since they couldn't just only interview those candidates.

[TomCollins]

Check the history, I did post.

[TomCollins]

You didn't take the information that the bullets are adjacent.

[dtbog]

[ QUOTE ]
Check the history, I did post.

[/ QUOTE ]

I didn't imply that you didn't...

-DB

[rt1]

[ QUOTE ]

You'd be surprised how many people show up with "solid" resumes for CODING positions, yet balk when you ask them to write a function in C that calculates the fibonacci series. "Can I do it in pseudocode?" "Do I have to get the syntax right?" "Can I just tell you how to do it?"

[/ QUOTE ]

No offense or anything here Ed, but I think you are way off here. I’ve worked as a coder for about 6 years now, with no college education or any of that jazz. I don’t think there is anything wrong about writing such functions in pseudocode… I mean, when are they going to have to code something that trivial from scratch, and when wont they have the resources right there in front of them? I don’t think its knowing code the counts, but more of knowing how to apply the coding to the app (process or writing the app etc). I mean, come on, now a days it takes 2 days to learn the syntax of a language. They are all pretty much the same.

I am a little touchy on this subject. My first 4 years of coding I worked for a great company out of boston. Lots of major schools there and anyone who showed up to our door from MIT got job. While some of these guys knew theyre [censored], a lot were right out of the classroom with no experience and couldn’t code for [censored]. Sorry to get way off subject…

Thanks!

[JoshuaD]

If you're applying for a position coding C, you should be more than familiar with the syntax of C. I learned on Java, and it took about a month to get very fluent in C, until that time, I was less than 100% productive. I can understand MS not wanting you to pick up the fluency on their buck.

[Piz0wn0reD!!!!!!]

This problem is flawed; anyone you would play this game with would not be your freind. So your prolly on acid and playing it w/ the lamp and a banana.

[Duke]

Seems trivial. You know your buddy didn't get shot, so there is only one way it could have spun such that you will get killed with the next pull (knowing that the bullets are right next to each other).

There's a 1/6 chance of that having happened.

If you spin, there's a 1/3 chance that you'll be in position to blow your brains out.

The only way this could be countered that I can see is if there were an inherent flaw with the gun, and spinning it would always make it stop in non-lethal positions relative to the current placement of rounds.

Assuming a fair firearm, though, do not spin.

EDIT: I'm a tard and it should be 1/4 because the 2 slots gotta be thrown out.

~D

[dtbog]

I can see it both ways, but I once worked at a company where a woman -- hired as a C++ programmer -- was fired after two weeks. Management cited her lack of productivity.

Her problem? She didn't know C++.

-DB

[smartalecc5]

ahh, adjacent chambers. Thank for the clarification- I missed that little part- haha /images/graemlins/laugh.gif

[Ed Miller]

Bayes' Theorem is a way to adjust a prior probability given new information.

In this case, the prior probability of finding a bullet directly after a spin is 2/6 or 1/3.

The new information is that your friend pulled the trigger, and there was no bullet in the chamber. That tells you something about which chambers can or cannot be next. There are only four chambers that held no bullet in them. Thus, you know the gun must have been on one of those chambers when your friend fired.

Of those four chambers he could have fired, three of them have empty chambers next to them. Only one of those four has a bullet next. So while the prior probability of finding a bullet is 1/3, the probability GIVEN THAT YOUR FRIEND DIDN'T FIND A BULLET, is only 1/4. Thus, you should just shoot the next chamber.

[jason1990]

Bayes' Theorem relates the conditional probability of A given B to the conditional probability of B given A. Often, it is necessary to invoke Bayes' Theorem in order to transform a prior probability distribution into a posterior probability distribution.

However, in our case, A is the event that the second shooter finds a bullet and B is the event that the first shooter does not. While it is true that P(A|B)=1/4, nowhere do we need to relate this to P(B|A). In fact, we can just compute this directly from the definition of P(A|B) without using Bayes' Theorem at all.

Definition of Conditional Probability:
P(A|B) = P(A and B)/P(B)

Bayes' Theorem:
P(A|B) = P(B|A)*P(A)/P(B)

It is the first formula, not the second, which captures the essence of the (correct) answers given in this thread. So while it may just be a matter of terminology, this is technically not an example of the use of Bayes' Theorem. It is simply an exercise in the computation of conditional probabilities. I just wanted to point this out for the benefit of those who may want to look further into this topic.

[CountDuckula]

Ok, after rethinking my initial answer, I think my reasoning still applies, even though I overlooked the fact that there were 2 bullets. Since the friend has exposed one of the empty chambers, there is a 40% chance that the next chamber contains a bullet. However, if I spin, there is a 33% chance that the chamber that comes up will hold a bullet. Therefore, I spin.

Now to read on and see why I'm wrong.... /images/graemlins/wink.gif


-Mike

[CountDuckula]

[ QUOTE ]
Ok, after rethinking my initial answer, I think my reasoning still applies, even though I overlooked the fact that there were 2 bullets. Since the friend has exposed one of the empty chambers, there is a 40% chance that the next chamber contains a bullet. However, if I spin, there is a 33% chance that the chamber that comes up will hold a bullet. Therefore, I spin.

Now to read on and see why I'm wrong.... /images/graemlins/wink.gif


-Mike

[/ QUOTE ]

Alllllllrighty, then; I stand corrected. /images/graemlins/blush.gif Somehow, I didn't manage to realize that the fact that the bullets were adjacent made that much difference. /images/graemlins/smile.gif Nice problem.

BTW, I seem to recall hearing of a problem that was also supposed to be a Microsoft interview question; it was something about 4 people walking at different speeds, crossing a bridge that could only hold 2 people at a time, and having to make the crossing while their flashlight held out. I remember being unable to solve it at the time (someone in my group at work relayed it to us), but I don't remember what the details were. Anybody else recognize this, and what the solution was?

-Mike

[TomCollins]

I am not 100% sure of the details of the numbers, but I believe it was, 4 people must cross a bridge and have one flashlight. The people walk across at the slowest persons speed. Only 2 people can cross at a time. The people travel at 1 min, 2 min, 3 min, 4 min. Can they get across in 12 minutes? (warning my numbers are probably wrong).

[pzhon]

From the rec.puzzles archive: "Four people need to get across a bridge that can only support two at a time. It is night and one of the two must carry a flashlight. There is only one flashlight. How can they get across in 17 minutes if their crossings speeds are 1, 2, 5 and 10 minutes?"

Solution (http://rec-puzzles.org/new/sol.pl/decision/crossing/bridge.crossing)

The above is often described involving the band U2. There are other variants with different speeds, the solutions are essentially the same.

[GuyOnTilt]

Hey Ed,

Haven't read through any of the responses, but here's my knee-jerk reaction without having thought it through. There are 6 possible placements. After your friend pulls a blank, there's only 4 possible placements, all of them equally likely. One of them gives you death, the other three let you live. Your chances of survival if you don't respin are 75%. If you respin, you get a random chamber and your chances of survival are 67%. So you should choose to respin or stand accordingly, depending on your goal.

GoT

[AEKDBet]

[ QUOTE ]
If you spin you have 4 chambers without a round and
2 with a round. You have 4/6 to survive when you pull the trigger.

When you just have pushed the trigger:
There are 4 empty chambers. Lets name them 1-4.
If he clicked chambers 1-3 you will get an empty chamber.
If he clicked chamber 4 you are in trouble. /images/graemlins/smile.gif
That means you will survive 3/4 times.

The conclusion is: just pull the trigger (75% > 66%)

[/ QUOTE ]

This is the exact reasoning I came up with. I am googling bayes theorm now to see if my math is wrong, but I think that the reasoning here is correct.

[karr2242]

Ok I believe I have solved it, however I did think I solved it quickly, and read a post and saw `conditional probability.` That led to some further thought and then I solved it ( I think ).
Take the six-chambered gun. Take spots 1,2,3,& 4 and leave them blank, thus leaving bullets in spots 5 and 6.
When your friend first shoots and misses, this tells you he is in Spot 1 through 4. This rules out the possibility of your next shot being in spot 6 (if it is Spot 6 next, then your friend bleeding on the floor is probably not still alive /images/graemlins/grin.gif ). Since the first shot was in one of the spots 1-4, and not in spots 5 and 6, the next shot Cannot be in spots 6 and 1.
The next shot is in spot 2, 3, 4, or 5 (shot). There is equal probability that it is Now in any of those 4 spots.
Thus it is 3 spots safe, and 1 spot dead.
Leaving 3/4 , or 75% survival rate.
If you instead spin the revolver, you deal with BOTH bullets as your shot could land in EITHER spots 5 or 6. So 4 spots save you, and 2 spots kill you.
That means 4/6, and a 66.67% Survival rate.

Your best bet to Survive is to Shoot again after your friend does.
This explanation may be a little long winded, but thats just best how I can explain the answer I came too.
I would appreciate a reply back from Ed if I got this (atleast for the most part) right.
Thanks for reading and good Poker to you.
MasterTrav

[EliteNinja]

There are 4 configurations in which the chambers can be in after your friend clicks off an empty chamber.

O - denotes an empty chamber
B - denotes a bullet
X - denotes the empty your friend has clicked off.
() - marks the chamber you will fire (after your friend)

The 4 situations are as follows:

1. X (O) O O B B

2. O X (O) O B B

3. O O X (O) B B

4. O O O X (B) B (in this case you die)


These 4 situations all have the same chance of occurring. And since there is one case where you will shoot a bullet through your head, your chance of staying alive is 75%.

Had you spun, your chance of staying alive is only 66%

On top of having 1.136 times better chance of surviving, you can also appear as being MANLIER to the not so statistically inclined.

Any friend who can convince me to play Russian Roulette with him is not my friend. He can play with himself if he so chooses.

[soko]

I think I solved it. I dont think it matters if you spin it agian or not. Because before the spin there is a 1/3 chance that gun will fire, after a blank you now know the round can not be in the very first position before the round or else the previous round would have been a bullet, and you also know it can't be in the position of the bullet adjacent from there or else the round would have also gone off. so you still have a 1/3 chance that that next round will be lethal.

This is right? /images/graemlins/cool.gif /images/graemlins/cool.gif

[TomCollins]

[ QUOTE ]
I think I solved it. I dont think it matters if you spin it agian or not. Because before the spin there is a 1/3 chance that gun will fire, after a blank you now know the round can not be in the very first position before the round or else the previous round would have been a bullet, and you also know it can't be in the position of the bullet adjacent from there or else the round would have also gone off. so you still have a 1/3 chance that that next round will be lethal.

This is right? /images/graemlins/cool.gif /images/graemlins/cool.gif

[/ QUOTE ] No.

[Dan Mezick]

Guys, at the time the first player pulls the trigger, there are SIX possible states for 2 bullets in the 6-gun:

2 Bullets adjacent in 6 possible chambers:

1&2
2&3
3&4
4&5
5&6
6&1 (whoops)

OK, six.

Let's assume chamber #1 was the chamber that clicked for player #1.... with no bullet inside.

That eliminates the first possible state (1&2) and the last possible state (6&1) from consideration, leaving 4 possible states (of initially 6 possible) remaining for the 2nd player to deal with.

Only one of them can kill you now (2&3) so you are looking at 1 chance out of 4 that you are going to die if you do not spin.

If you choose to instead spin the 2 bullets in the 6 chambers, there is a 2/6 = 1 out of 3 chance you will get a headache.

Don't spin and you have a 1 in 4 chance of a bullet.

Spin and you have a 1 in 3 chance of a bullet.

Don't spin.

[JoshuaD]

Why is everyone ignoring the rounds subsequent to that one round? Your analysis ends up coming to the right answer, but there are times where not re-spinning is immediately +EV, but ends up being in the longterm (after a round or two more) -EV.

[na4bart]

I know nothing of Baye's Theorem, read the name somewhere, but that is it, so...

If I spin it the odds are 2:1 I survive.
If I don't spin it would appear either I die or live. Even money.

I opt to spin as I like 2:1 better than even money.

Did I get it?

Edit: [censored], I had it ass backwards. Glad I play poker and am not appling at MS

[CardSharpCook]

PULL THE TRIGGER!!!!!

Your friend has a one in three chance of redecorating the living room. If you were to spin the chamber, the same would be true for you. However, because you know that the loaded chambers are adjacent, if you pull the trigger NOW, your odds of living are 1 in 4.

Of the four empty chambers, only one of them is next to a loaded chamber (as the gun turns). So, your friend shot one of the empty chambers, there is a one in four chance it was the empty chamber next to a loaded one.

FIRE AWAY!

CSC

[Eclypse]

Well, I didn't read any of the replies, so forgive me if this has already been answered this way.

You should pull the trigger again without spinning. The reason is that the revolver always turns in the same direction which means there is a 3-to-1 chance the next pull will be an empty chamber whereas if you spin you're only getting 2-to-1.

The key is that the bullets are in "adjacent" chambers.

[alThor]

[ QUOTE ]
To me it shows how superior the Microsoft style of interviewing (solve these problems now, please) is to a more traditional style

[/ QUOTE ]

Since I can't stand seeing M$ being credited with anything, let me point out that consulting firms (e.g. McKinsey) have used this style of interview for quite awhile.

alThor

[SomethingClever]

[ QUOTE ]
This problem is flawed; anyone you would play this game with would not be your freind. So your prolly on acid and playing it w/ the lamp and a banana.

[/ QUOTE ]

DING DING DING!

[theTourne]

I like the following riddle. It took me a while.

There are 8 people who need to cross a river. They have a boat, but it only holds two at a time. The people are:
Father
Mother
2 Sons
2 Daughters
Policeman
Thief

Due to the disfunctionality of the family, and the fact that the thief is a bad, bad man; the following three rules most be observed at all times.

1. The thief cannot be with any members of the family unless the policeman is present.

2. The mother cannot be with either of the sons unless the father is present.

3. The father cannot be with either of the daughters unless the mother is present.

Finally, since the current is strong (and the thief isn't to be trusted) only the father, mother or policeman may row the boat.

Can you get them all across?

[Blackjack]

Haven't read any of the other replies.

If he has fired it and there was no bullet. That means he landed in any of 4 places. 1/4 of those places will result in the next shot fired meaning bye bye for you.

If you spin it again, there are 2 slots that will kill ya out of 6 possible.

So the answer is... Shoot it again if you wanna maximize your chances of staying alive by 8%.

[pudley4]

[ QUOTE ]
I like the following riddle. It took me a while.

There are 8 people who need to cross a river. They have a boat, but it only holds two at a time. The people are:
Father
Mother
2 Sons
2 Daughters
Policeman
Thief

Due to the disfunctionality of the family, and the fact that the thief is a bad, bad man; the following three rules most be observed at all times.

1. The thief cannot be with any members of the family unless the policeman is present.

2. The mother cannot be with either of the sons unless the father is present.

3. The father cannot be with either of the daughters unless the mother is present.

Finally, since the current is strong (and the thief isn't to be trusted) only the father, mother or policeman may row the boat.

Can you get them all across?

[/ QUOTE ]

Here's a link (http://www.gsart.com.br/midia/riverIQGame.swf) to a flash version

Hint: <font color="white"> it takes 9 trips across </font>

[SumZero]

I like this question on conditional probability because it quickly sees if the person has an intuitive sense of probability. And, since it is a pretty easy question IMHO, it has a nice followup question which could be useful in a situation where the person got it right (although I'm not sure logic/math questions are the best questions to ask potential programming interviewees, I'd much prefer asking them to put real code on the board).

So you ask the question about maximizing the probability of survival through the next round. The person thinks for 5 to 10 seconds and says 3/4 chance to survive if you don't spin versus 2/3 chance if you do spin, so you should not spin if you want to win.

Followup question: Assume you are now the first player. You pulled the trigger and got a click. Your opponent didn't spin, pulled the trigger and got a click. The gun is now handed to you (unspun). You are faced with the decision to spin the chambers and shoot or just straight up shoot the gun as is. Does it matter what your strategy should be?

[DQPaulie]

I would say our strategy matters. If we look at the situation now, we have a 2/3 probability of survival either way. Our odds are the same either way, but are the situations to follow the same? If our opponent knows all the same odds as we do, we have to pull the trigger unspun. Reason is if we survive we leave hime with a 1/2 chance of survival if he just pulls the trigger, so he will spin to better his probability of survival to 2/3 and if he misses we get the 3/4 probability to survive again. If we spin we get the same odds as not spinning, but then leave him with the favorable odds of 3/4 . We would rather have the 3/4 odds if we get that far.

[Slow Play Ray]

I didn't post an response (already too many correct answers, no point), but I did get the right answer. Since then, I have been asking everyone I know this question, and I am in awe of how many got it wrong. My boss is the ONLY person I asked to get it right, with the right reasoning, on the first attempt.

GREAT post Ed!

[AviD]

[ QUOTE ]
Does it matter which one you choose? If it does, why?

[/ QUOTE ]

My answer would be no it doesn't matter which one you choose...you're an idiot for playing Russian Roulette with a friend (no less). Just keep squeezing until it goes off, but be sure to tell your "friend" (before you start) to follow suit after the first one goes off. He shouldn't have to wait too long for his turn.

Sounds like a fun interview...is this Microsoft's way of "thinking outside the box"? /images/graemlins/grin.gif

[TomCollins]

ARG, I got it, but now I can't remember how I started.

[TomCollins]

River crossing answer:

P = police, T = thief, F = Father, M = Mother, D = Daughter, S = Son.


PT-&gt; Cross
P-&gt; Back
PS-&gt; Cross
PT-&gt; Back
FS-&gt; Cross
F-&gt; Back
FM-&gt; Cross
M-&gt; Back
PT-&gt; Cross
F-&gt; Back
MF-&gt;Cross
M-&gt; Back
MD-&gt;Cross
PT-&gt;Back
PD-&gt;Cross
P-&gt;Back
PT-&gt;Cross

WINNA!

[slogger]

I feel like I must be missing something, but I would not spin the chamber again. If I spin the chamber again (assuming that doing so would produce a random result), I will have a 1-in-3 chance of getting a bullet in the head when I pull the trigger.

If I do not spin the chamber, then, because the bullets are in adjacent chambers I have only a 1-in-4 chance of shooting myself because I know there is one full chamber and one empty that cannot be "on deck." I know this because my friend did not get bullet No. 1 or bullet No. 2. Therefore, the next chamber cannot be Bullet No. 2 or Empty No. 1.

The only possible chambers for my pulling of the trigger are Empty No. 2, No. 3 or No. 4 or Bullet No. 1.

[slogger]

If he had shot himself, then I would be the winner, and I wouldn't need to guess.

But assuming I had to play on after he shot himself, then I would spin because w/o a spin, I would have a 1-in-2 chance of getting a bullet. With a spin, I would have a 1-in-5 chance, assuming that the gun was not reloaded.

If the used (just fired) chamber was reloaded, a spin would still be correct, giving me a 2/3 chance of survival.

Edit: change 1-in-5 to 1-in-6 in the 2nd graph; mental note: read your post in the made-for-checking pre-submit mode rather than the post-submission "view your post" mode.

[Slow Play Ray]

[ QUOTE ]
He pulls the trigger...

Click. He hands the gun to you.

[/ QUOTE ]

I think this part implies the gun didn't go off...LOL

[The Yugoslavian]

I haven't read any posts to the original question but drawing some quick pictures to help my well below genius IQ out I'd have to say that you have a 75% chance of living if you do not spin the chamber again and a 67% chance of living if you do spin it again.

After your friend discovered a blank chamber you know that the revolver was in one of 4 states. 1 of those four states is fatal and the other 3 are safe (for the next shot anyway). So, 75/25 you live/die. If you spin it then you're going to get 67/33 live/die.

Yugoslav

Now to check my answer!!! /images/graemlins/grin.gif

Edit: In a hurry and apparently rounded 66.66 down ... meh. I'm still right baby!

[Sparks]

Mau!


Sparks

[binions]

[ QUOTE ]
Bayes' Theorem is a way to adjust a prior probability given new information.

In this case, the prior probability of finding a bullet directly after a spin is 2/6 or 1/3.

The new information is that your friend pulled the trigger, and there was no bullet in the chamber. That tells you something about which chambers can or cannot be next. There are only four chambers that held no bullet in them. Thus, you know the gun must have been on one of those chambers when your friend fired.

Of those four chambers he could have fired, three of them have empty chambers next to them. Only one of those four has a bullet next. So while the prior probability of finding a bullet is 1/3, the probability GIVEN THAT YOUR FRIEND DIDN'T FIND A BULLET, is only 1/4. Thus, you should just shoot the next chamber.

[/ QUOTE ]

This answer assumes that the weight of the 2 bullets chambered side-by-side does not influence their position after a robust spin in an oiled, well-maintained, perfectly balanced revolver.

[eldyna]

[ QUOTE ]
This answer assumes that the weight of the 2 bullets chambered side-by-side does not influence their position after a robust spin in an oiled, well-maintained, perfectly balanced revolver.

[/ QUOTE ]


Just point the gun straight up when spinning and the effect of gravity is nullified, no?

Tim

[QuadsOverQuads]

back-of-the-envelope calculation:

There are 4 possible states in which your friend would have fired a blank. Of those four, three will lead to a blank for you and 1 will not. So, your odds of pulling a blank here are 3/4 or 75%.

If you just randomly spin the chamber, the normal odds would be 4/6 for a blank, or 66%.

Thus, at least by my math, your odds of living are 75% if you don't spin, but only 66% if you do.

Therefore, you shouldn't spin.


q/q

[Jamper]

Did you take off points, if the applicant pulled out a pen &amp; paper? That's how i solved the problem &amp; would have taken the same approach in an interview.

====

I'm currently reading your book &amp; Theory and there's a couple of issues that i'm still trying to resolve. Here's my related Q for you -

HE, 10 players, a loose game, initial betting round. The 1st x players fold, say 4. It's now my turn to bet. Does the fact the 1st 4 folded mean that the remaining 5 are likely to have better cards than they would if a new deck was shuffled and these 5 were dealt another set of hole cards?

Before people jump into the discussion, consider these points:

- Don't just view this as 1 incident, imagine that it happened 10,000 times and all the results are tallied. [A billion times, whatever, high enough to smooth out the #'s]

- Regardless of your betting criteria, there should be an average of Y good hole card pairs on each deal. Assume my cards are no good as well. Does that mean that, on average, the remaining 5 players will have 0.5*Y good hole card pairs? Y? something in between?

- The 1st 4 folding could indicate that they didn't have good high cards --&gt; that as the cards were dealt to the remaining 5 players, there were more high cards in the deck &amp; the remaining 5 players had a greater % likelyhood of being dealt high cards than the 1st 4 players.

Anyone is welcome to comment

[Kaz The Original]

Ok. First off you're a freak : )

I do not understand Bayes Theorem and will give my laymans approach to this problem. You are in two situations and have the following piece of knowledge : The bullets are adjacent.

There is a 2 in 6 chance you will spin to bullet. 1/3rd of the time. The question is, does your friend having fired a shot increase, decrease or change this chance?

You now have 2 in 5 chance of shooting a bullet. This is obviously correct because if you fire 3 more times and get click you would then have a 2 in 2 chance.

The only information you gain from the bullets being adjacent is that their is not a bullet in both the next chamber and the chamber right before the one you just shot.

Spin again.

[tylerdurden]

I've asked this question to a lot of otherwise intelligent people, and almost every one of them got it wrong. The few that got it right were obviously guessing, except for one guy.

None of them (except the one guy) actually attempted to reason it out.

The education system (in the US, at least) emphasises rote memorization and discourages visualization and "working it out". When confronted with a question to which the student hasn't memorized the answer, guessing is the only remaining path.

Ever wonder why Asian kids are so good at doing arithmetic quickly in their heads? Nobody ever told them it was bad to use their fingers when counting. Using any means possible to visualize a problem is a much better skill than simply memorizing 7+8.

I had a professor for Differential Equations II that was from Japan and could do aritmetic very quickly. Now there are some people who can do simple arithmetic involving large numbers in their head, but don't understand how they do it, but I've met several of those people and this professor didn't seem like one of them (he was fast, but not instantaneous like the people that had the inherent ability). I asked him how he did it and he told me, "I just picture an abacus in my head."

The one guy who did get it right just drew the cylinder out on a whiteboard and had the answer in about 30 seconds.

[Paul2432]

[ QUOTE ]
From the rec.puzzles archive: "Four people need to get across a bridge that can only support two at a time. It is night and one of the two must carry a flashlight. There is only one flashlight. How can they get across in 17 minutes if their crossings speeds are 1, 2, 5 and 10 minutes?"

[/ QUOTE ]

The wiseass (and technically correct) answer to this question is that crossing the bridge is impossible. If the bridge can only hold two people, the added weight of the flashlight will collapse the bridge.

Paul

[Ed Miller]

Did you take off points, if the applicant pulled out a pen &amp; paper? That's how i solved the problem &amp; would have taken the same approach in an interview.

Use of pen and paper is encouraged. /images/graemlins/smile.gif

HE, 10 players, a loose game, initial betting round. The 1st x players fold, say 4. It's now my turn to bet. Does the fact the 1st 4 folded mean that the remaining 5 are likely to have better cards than they would if a new deck was shuffled and these 5 were dealt another set of hole cards?

What you're talking about has a name... it's called "bunching." You can search for that word and find more discussion of this idea. Some authors think this is a significant effect, but I think they are wrong.

Dan Kimberg did some simulations about it.. he wrote it up in a Card Player article.

My feeling (and I know it's Mason's as well) is that the remaining players are ever so slightly more likely to have better hands, but that the effect isn't nearly large enough to incorporate it correctly into your strategy. (That is, any adjustment you consciously make is almost certainly going to be an overadjustment.)

[ddubois]

So why are manhiole covers round?

The "Microsofty"-question I like to ask in interviews is: "You are in a small pond, in a boat, with a cannonball. You take the cannonball and plop it into the water. Does the water level (once it has calmed) on the shore go up, go down, or stay the same?" It always depresses me how few people get this question correct, and don't really try to work it out.

One of the coolest interview questions I've been asked was: "You wish to use two cubes to represent a day calendar. In other words, you want to be able to arrange the cubes such that the tops show anything from [0] [1] to [3] [1], inclusive. Can you do this, and if so, what numerals do you enscribe onto each face of each cube?" The reason I liked this so much is that there is the initial logical aspect of the solution that gets you 90% of the way, which has to be worked out like most of these puzzles, and then to get the last 10% there is an additional hurdle that requires some out-of-the-box thinking.

[Jamper]

Thanks for the reply.

It's puts my mind more at ease now b/c I knew there had to be some effect, however small. The Bunching keyword led to several threads and a link to the Card Player article.

It was getting to the point where I was comptemplating running my own simulation /images/graemlins/shocked.gif

-jamp

[buzzbait]

[ QUOTE ]

One of the coolest interview questions I've been asked was: "You wish to use two cubes to represent a day calendar. In other words, you want to be able to arrange the cubes such that the tops show anything from [0] [1] to [3] [1], inclusive. Can you do this, and if so, what numerals do you enscribe onto each face of each cube?" The reason I liked this so much is that there is the initial logical aspect of the solution that gets you 90% of the way, which has to be worked out like most of these puzzles, and then to get the last 10% there is an additional hurdle that requires some out-of-the-box thinking.

[/ QUOTE ]

For this I would set up one cube with faces of 0,1,2,3,4,5 and the other with 0,1,2,7,8,6 with this last face also used as 9, as 6 and 9 are never needed at the same time (In the day calendar that is, get your mind out of the gutter /images/graemlins/wink.gif )

[Derek in NYC]

Part of the confusion by those who failed to get the right answer may come from a lack of familiarity with the way revolvers work. In a revolver, with each trigger pull, the cylinder holding the bullets rotates exactly 1/6 of the way, the hammer cocks, and releases on the cylnder that has just rotated into alignment with the barrel. If there is a bullet in that cylinder, the gun goes bang; if not, it goes click. On the next trigger pull, the same thing happens. After 6 trigger pulls, the hammer has cocked and fallen on every cylinder of the gun, and discharged all the bullets in all the cylinders.

A different problem. You and your friend wish to play Iraqi Roulette, a variation on Russian Roulette. A friend hands you a Glock pistol, inserts a fully loaded magazine into the gun, firmly seats the magazine, and cycles the slide. Who should go first? You or your friend?

[guller]

I think I would bet against the odds on this one and spin. For all the marbles (my life) I would want to get some of my own luck involved on this decision.

If the cylinder was weighted by the 2 bullets wouldn't they tend to settle on the bottom away from the firing pin more often than not?

[dblgutshot]

[ QUOTE ]


A different problem. You and your friend wish to play Iraqi Roulette, a variation on Russian Roulette. A friend hands you a Glock pistol, inserts a fully loaded magazine into the gun, firmly seats the magazine, and cycles the slide. Who should go first? You or your friend?

[/ QUOTE ]


I have no knowledge of handguns, but is it more likely that a bullet or gun would get jammed on the first shot rather than the second?

The obvious answer is to go second, so your friend blows his brains out and you can leave!

[bobbyi]

[ QUOTE ]
Did you take off points, if the applicant pulled out a pen &amp; paper?

[/ QUOTE ]
We have whiteboards in our offices and applicants are certainly welcome to try to work out a problem like this on the board. For code/ pseudocode problems, writing the code on the whiteboard is pretty standard. Remember that the point of a problem like this isn't primarily to see what answer the applicant comes up with. It's to see how they think and reason. That means that it would be very silly to penalize someone for doing something that demonstrates how they are trying to arrive at the answer. If you were encouraged to just sit in silence and ponder the question and then blurt out an answer a few minutes later without showing how you came up with it, do you think that would really make for an effective interview process?

[stocktrader23]

I'd guess that I'd just pull the trigger. My simple reasoning being that if you spin it you have a 1/3 chance of landing on death. Considering all safe pulls are in a row I think you have a 1/4 chance since he already went and it was blank. If he had landed on the 1st, 2nd, or 3rd chamber after the bullets you would be safe. 4th one dead.

[reubenf]

Interestingly, if you you hear a *click* when you pull the trigger, your friend's next move it -still- not to spin.

[d10]

I don't know Bayes theorem, and I was tempted to say "Yes, spin it again, obviously your chances of killing yourself now are 2/5, where if you spin it will be 2/6." But the "trick question" flag popped up in my mind so I spent a little more time thinking about it. Then I realized that if you just take a second shot, you will have a 3/4 chance of survival, whereas spinning again reduces it to 2/3.