[rona_]

Fluffy, on Sep 21 2007, 12:44 PM, said:

can someone help me with number 2?, I can't transate it properly.

nickell is a coin?

glass blender I have no idea of what it is

Fluffy,

A nickel is a US 5 cents coin.

A blender is a kitchen gadget that liquifies food, so I am guessing that a glass blender is a blender with a glass jar to put the food in. Come to think of it, I have only seen glass ones.

[Fluffy]

david_c, on Sep 21 2007, 01:03 PM, said:

Fluffy, on Sep 21 2007, 09:23 AM, said:

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 , 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]

Fluffy, on Sep 21 2007, 02:17 PM, said:

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]

helene_t, on Sep 21 2007, 07:52 AM, said:

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]

david_c, on Sep 21 2007, 08:03 AM, said:

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]

Fluffy, on Sep 21 2007, 12:23 AM, said:

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]

Quote

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]

Blofeld, on Sep 22 2007, 05:36 AM, said:

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]

cardsharp, on Sep 22 2007, 01:44 PM, said:

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]

Blofeld, on Sep 22 2007, 05:36 AM, said:

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.

[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.

[Mbodell]

1eyedjack, on Sep 24 2007, 02:35 AM, said:

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]

Hannie, on Sep 22 2007, 12:20 PM, said:

Blofeld, on Sep 22 2007, 05:36 AM, said:

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?