Wanna work at google?

[Fluffy]

17. You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)kes to work for Google?

Dammit I get 97. Can someone explain what I've done wrong here:

 

with three remaining: -, -, 100, 0, 0

with four remaining: -, 98, 0, 1, 1

with five remaining: 97, 0, 1, 2, 0 or 97, 0, 1, 0, 2.

I came to this as well

 

But then think of the 2 pirate problem

 

what would 1 do if '2' offered him 100 coins and 0 for him? He doesn't care to pick to pick the 100 now, or just kill the other and pick the 100 after, your solution says he would always die, but that doesn't have to these way.

 

Bad new is that even then, the result comes to 97-2-1 at the end :rolleyes:, but I think changing the way to solve ties leads to 98.

 

Also they said 98% of the gold, there is a famous similar problem wich ends with '33-33-33, and throw the 100th to the sea so nobody gets angry'

 

98% could stand for 97/99 I guess, it can be a point to take :)

 

 

What amsued me the most of this problem is that I first though 98 coins would probably go to the second or first.

 

Upon starting to solve I suspected for to the third or fouth, I was in bed a bit sleep, but untill the very end when I solved step 5 I didn't realice it was the original pirate to get almost all of the gold :). It hit me in the face, was fun.

[Fluffy]

number 2:

 

there is no liquid, only air, the ebst you can do is move into the middle of the glass to get into the 'eye' of the 'tornado'?

[jtfanclub]

number 2:

 

there is no liquid, only air, the ebst you can do is move into the middle of the glass to get into the 'eye' of the 'tornado'?

Don't have to.

 

The blades in a blender spin like a helocopter, pushing everything up. This means the heaviest stuff stays at the bottom and gets chopped up. If you run a blender with the lid off, you get a nice coat of whatever on the ceiling.

[pdmunro]

Funny, I recall Google was chosen as the most attractive US employer by some fancy magazine a couple of years ago. Maybe that position has made them arrogant.

I have read that Google interviews are technical. For example:

 

"Ok, regarding the interviews, yes they are tough. They grill you with specifics, so you really have to know your stuff.

 

Skills like C++ and Java were only secondary requirements for me, the main requirement being a different platform (I hesitate to mention it here, it would be too damning to me) so I can not give much specifics that would help most of you out there (plus I have to worry about the Non Disclosure agreement that I signed).

 

The phone interview was around 40 minutes. It was technical, but wasn't too in-depth. I think the guy sensed I knew my stuff, so he didn't really grill me.

 

On site interviews lasted almost 4 hours, and were rather grilling. Much of the technical questions they asked me were real design issues they were facing. They use whiteboards often, which was really cool for me, because I like hammering out solutions as I write and draw. They didn't throw any of the (in)famous puzzles that I hear about, nor did they try any kind of personality tests. They just grilled me on the platform that is my main expertise."

http://weblogs.asp.net/jasonsalas/archive/.../04/424378.aspx

[rbforster]

Dammit I get 97. Can someone explain what I've done wrong here:

 

with three remaining: -, -, 100, 0, 0

with four remaining: -, 98, 0, 1, 1

with five remaining: 97, 0, 1, 2, 0 or 97, 0, 1, 0, 2.

This pirates problem depends on 2 important things - how ties get broken, and what the incentives of the pirates are when faced with an equal $ choice. In the =>50% to win case, there are never issues with ties (they are broken in favor of the proposing pirate), and you get the recursive solution like this

 

-- -- -- 100 0 (sucks to be last)

-- -- 99 0 1

-- 99 0 1 0

98 0 1 0 1

 

In this case 98 is the right answer, and there are no issues with the pirates incentives in case of a tie. If you use the strictly >50% to win rule, and you assume that incentives are ordered Live > $ > Kill Others, then you get 97.

 

-- -- -- X 100 (X = killed)

-- -- 100 0 0 (#4 votes in favor, to avoid dying)

-- 98 0 1 1

97 0 1 2 0 (or 97 0 1 0 2)

[Echognome]

17. You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)

I am going to stick my neck out and say you are all wrong (except possibly David C and Rob F) on this.

 

First comment, this is NOT the same as the classic five pirate problem where the proposer gets to vote. Note that in the setup of this problem, the proposer doesn't vote, but the others do. And if fewer than half of those that vote agree with him, he is killed. (It is not stated, but assumed that if half or more do agree, then the proposal is accepted.)

 

Second comment, no discussion of ties is discussed. Furthermore, beliefs are not discussed. Let me propose a Nash equilibrium. Pirate A proposes 100, 0, 0, 0, 0. Pirates B, C, D, and E all vote yes and they all believe all of the other pirates are going to vote yes. Given their beliefs (which are true in equilibrium), they have no incentive to vote no (because it will not change the outcome). No need for any backward induction at all! There are, of course, other equilibria.

 

Third comment, so let's do this the way the problem was intended and say you must break ties with at least one gold coin. Then let's apply backward induction as it was meant to be.

 

If only D and E left, E will not accept any offer less than 100. Why would he when he could just vote no and D is killed. (If he votes no, then fewer than half of the others agree with the proposer, D.) So the only equilibrium is:

(dead, dead, dead, 0, 100)

 

If C, D, and E are left, then D will accept any proposal where he gets more than 0 (lest he get nothing at all, or even worse, killed). So for C to maximize his gold, he only need to offer D one golf coin. Since C needs only 1 out of 2 votes, he can do no better than the equilibrium:

(dead, dead, 99, 1, 0)

 

If B, C, D, and E are left, then B knows that he needs to get 2 out of the 3 votes to have his proposal accepted. So the best he can do is offer the equilibrium:

(dead, 97, 0, 2, 1)

 

If all five pirates are left, then A needs only 2 out of 4 votes to have his proposal accepted. The cheapest votes he can buy are C's and E's, so the best he can do is propose:

(97, 0, 1, 0, 2)

[Joe de Balliol]

I agree with Echognome...BUT, I don't see any incentive to give E 2 rather than 1 - E will get 1 from either B or A so has no incentive to not accept A's proposal, and the slight negative incentive that if neither A nor B's proposal is accepted, he will get nothing, so is likely to accept 1 - maybe this is why the problem says 98? Or, as Echognome pointed out, it might be from the alternative form where all pirates vote.

[Blofeld]

As pointed out, some of these problems seem to have been garbled from their standard forms, presenting us with either a problem with not enough information or one with a trivial solution.

 

I'll skip the large-numbers-estimations because I'd encourage others to try these (they're fun and not too hard). But some of the other questions haven't been adequately answered, I think, so I'll have a go.

 

2. Standing on the blades seems to be asking for trouble. For one thing, my experience of blenders tells me that stuff is sucked down in the middle (and thrown up around the edges). At any rate the net airflow up/down must be zero. I'd rather not get stuck in a turbulent flow of this kind when another option presents itself:

 

I jump out. I'm not quite sure how big a nickel is, but it doesn't matter. Say we're being shrunk to 1/n of our normal size in linear dimensions. Then muscle strength, which is proportional to cross-sectional area, will be 1/n^2 normal. Our legs will be able to push us from the ground for 1/n the normal distance. Using E = Fs (E = Energy, F = force, s = displacement) to get kinetic energy gained from jumping, we should have 1/n^3 the normal amount. But our mass is also 1/n^3 normal, so when we leave the ground our velocity is just the same as when we jump at full size. If we neglect air resistance we'd thus be able to jump to the same height. Air resistance will play a bigger role on small-us, but not sufficiently big that we shouldn't be able to clear the blender walls.

 

9. If we assume that everyone involved is entirely logical and knows all the others to be so, then on the hundredth day all the wives kill their husbands. [Claim: if precisely n husbands have been unfaithful then their wives will kill them on the nth day. Obviously true for n=1. Proceed by induction.]

 

11. Probability of not observing a car in 30 minutes = 0.05. Therefore probability of not observing a car in 10 minutes has to be the cube root of 0.05. Probability of observing a car in 10 minutes is 1 minus this, or roughly 0.63.

[Fluffy]

you come to 98 coins if you asume people won't put their life in danger for no gain.

 

Pirate 2 would then accepet Anything so

 

100-0-0 is good

 

99-0-0-1 is good

 

99-0-1-0-0 is also good

 

Right?

 

No, pirate 2 has another chance of accepting 0 later, then he wouldn't accept getting 0 untill the last time at 100-0-0 since he has the chance of someone doing it wrong.

so.

 

100-0-0 is good

 

98-0-1-1 is good

 

----

 

97-0-1-2-0 or 97-0-1-0-2 :/

 

 

bah!

 

 

Another idea: If there are 2 solutions for an early case, you can offer the same ammount he gets on a previous round, because he doesn't know if he will get the same, or less.

[hotShot]

17. You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)

So pirate5 has to make he first suggestion and pirate1 will be the last.

 

This means:

Pirate1's live is in no danger and if he does not accept offers of less than 100, he will get all in the end.

Pirate2's live is in no danger, but he will have to offer pirate1 100, to stay alive. So he will accept any offer better than nothing.

Pirate3 is sort of a lucky guy, he knows pirate1 will reject his offer, but if pirate2 agrees, his live is save and he lives to spent his money. So in his position 99-1-0 would work.

So he does not need to agree to anything less than 99 coins.

Pirate4 is in a bad position, he knows that pirate3 and pirate1 will disagree with almost any suggestion he can make (maybe 0-99-1-0 would work). So his live is at risk if he does not agree to anything that pirate5 suggests.

So pirate5 will stay alive if he offers pirate4 and pirate2 a coin and keeping their lives.

So the solution is 98-1-0-1-0.

[matmat]

I jump out. I'm not quite sure how big a nickel is, but it doesn't matter. Say we're being shrunk to 1/n of our normal size in linear dimensions. Then muscle strength, which is proportional to cross-sectional area, will be 1/n^2 normal. Our legs will be able to push us from the ground for 1/n the normal distance. Using E = Fs (E = Energy, F = force, s = displacement) to get kinetic energy gained from jumping, we should have 1/n^3 the normal amount. But our mass is also 1/n^3 normal, so when we leave the ground our velocity is just the same as when we jump at full size. If we neglect air resistance we'd thus be able to jump to the same height. Air resistance will play a bigger role on small-us, but not sufficiently big that we shouldn't be able to clear the blender walls.

sorry. the lid was closed.

[paulg]

It's my guess that your answer has to be on the first page of responses to be considered for a job with Google.

 

Paul

[cherdano]

It's my guess that your answer has to be on the first page of responses to be considered for a job with Google.

 

Paul

You didn't know they always invite the author of the 37th response to an interview?

[han]

11. Probability of not observing a car in 30 minutes = 0.05. Therefore probability of not observing a car in 10 minutes has to be the cube root of 0.05. Probability of observing a car in 10 minutes is 1 minus this, or roughly 0.63.

Well done Owen.

[sceptic]

The pirates

 

Question

 

= 1 one of us gets 98 coins, 1 gets 1 coin another gets 1 coin , the rest get zero

 

Lets have a lottery

 

 

answer "ok yes lets go for it"

[1eyedjack]

Seems to me that the 8 ball problem is effectively the same if you extend it to 9 balls (of which 8 are of equal weight). Psychologically it would seem a more daunting problem the more balls are in the air.

[Guest Jlall]

11. Probability of not observing a car in 30 minutes = 0.05. Therefore probability of not observing a car in 10 minutes has to be the cube root of 0.05. Probability of observing a car in 10 minutes is 1 minus this, or roughly 0.63.

Well done Owen.

Oo hannie you'll have to explain this one to me on AIM lol

[Mbodell]

Seems to me that the 8 ball problem is effectively the same if you extend it to 9 balls (of which 8 are of equal weight).  Psychologically it would seem a more daunting problem the more balls are in the air.

The normal good problem with weights and balls, of which this version is kind of a subproblem (with 8 balls, not 9, which is probably why this version only has 8 balls), is you have 12 balls and know that 11 are identical in weight but 1 is EITHER heavier OR lighter. Now with 3 weightings of the scales of justice style scale (I.e., one side goes up or down or stays the same but you don't get a number answer) you have to determine the defective ball AND if the ball is heavier or lighter.

 

Many of these types of problems are fun to work on, but few make good interview questions IME (both as a candidate who nailed all of these questions when Microsoft used to ask them [but still though the a-ha questions were poor] and an interviewer who has interviewed a couple hundred technical people).

[Echognome]

11. Probability of not observing a car in 30 minutes = 0.05. Therefore probability of not observing a car in 10 minutes has to be the cube root of 0.05. Probability of observing a car in 10 minutes is 1 minus this, or roughly 0.63.

Well done Owen.

Interesting as I came about the answer a different way, but still the same (up to whatever rounding issues we both have).

 

The underlying presumption here is that the arrival of cars is a homogeneous Poisson Process. Thus, we can simply use the Exponential Probability distribution to model our probabilities. To show this assumption is critical, imagine that we are observing cars at the end of a bridge between the time of 7:50am and 8:20am and that for some reason, the bridge doesn't open until 8am. In that case, the probability of observing a car in that 30 minute increment might be .95 and in the first 10 min increment it would be 0.

 

I'm not sure what constant default probability is referring to. Default probability is typically defined as the probability of defaulting on debt! Shrug.

 

Anyway, once we have independent time increments, we can use the exponential distribution.

 

Then, Pr(T > t) = Exp{-lambda*t}

 

We are given that the Pr(T < 30) = 0.95

 

or Pr (T > 30) = 1 - Pr(T < 30) = 0.05 (this is what Owen used when saying the probability we do NOT observe a car in 30 minutes)

 

Pr(T > 30) = Exp{-lambda*30} = 0.05

 

Solving for lambda yields it to be approx 0.1.

 

Then we can use Pr(T > 10) = Exp{-(0.1)*10} = 1/e or about 0.37.

 

Finally, Pr(T < 10) = 1 - Pr(T > 10) = 1 - 0.37 = 0.63.

 

I'll be interested to hear how Owen used the cube root.

 

Edit: Arend told me how Owen came about using the cube root. Using Pr(T>30) = Pr(T>10)*Pr(T>10)*Pr(T>10) as you have to not see the car in each 10 min increment. Nice way to solve it. Relies on the same independent time increment assumption.

 

Edit2: Bonus Questions - What's the probability of observing TWO cars in 10 minutes? Suppose you arrived at the observation point, how long do you expect to wait before you see the next car?

[cherdano]

What makes me think Owen gets the job and Echo doesn't? :)

[han]

Yes, I called Mr. Google and Owen gets the job.

 

I also talked with a google employer yesterday. He is well known to many here but I won't mention his name because google sees it all. He said Richard wasn't that far off with what he wrote in this thread so it isn't clear if Owen should be happy or sad.

[Echognome]

What makes me think Owen gets the job and Echo doesn't? :D

Yes, I called Mr. Google and Owen gets the job.

Silly mathematicians living in the theoretical world.

 

In the real world, Gnome has the job. Owen didn't show his work. :D

[hrothgar]

If Owen is really going to work for Google in Mountain View, I wish him luck...

 

More importantly, I THOROUGHLY recommend a sushi joint in Cupertino called Kitsho

The aji no tataki is to die for and they have some great saki (Go with the dewazakura oka)

 

Make sure to eat at the sushi bar and order Omakase.

[han]

In the real world, Gnome has the job.

It's hard to argue with that.

 

But I would claim that Owen did show his work, and that he demonstrated a healthy dosis of common sense as well.

[Blofeld]

[Richard: I'm not likely to go to work at Google any time soon, but if I find myself in that part of California I'll try and remember the sushi recommendation.]

 

Matt: I showed working! Sheesh, how much do you want? :)

 

Now I'll take my dosis elsewhere.