Tuesday, February 26, 2008

Brainteaser Interview Questions

This list of Brainteasers is brought to you by Gabe M., a summer analyst with Bear Stearns. Feel free to post a comment if you know the answer to these questions. I will add more questions to this list in the coming month.

  1. There are 100 people in line to board a train. Each person is holding a ticket corresponding to both his place in line and his seat (i.e. Person 1 is supposed to sit in Seat 1, Person 2 is supposed to sit in Seat 2, etc.). All of the people in line are normal, except for Person 1, who is "crazy". When Person 1 boards the train, he will ignore his seat number and sit in a random seat. Following Person 1, each person will sit in his own seat, unless his seat is occupied. In this case, the Person who's seat is occupied becomes the new "crazy person" and will sit in a random seat. For example, if Person 1 sat in Seat 2, Person 2 will become the "crazy person" and sit in a random seat. What is the probability that Person 100 will end up in Seat 100?


  2. McNuggets come in boxes of 6, 9, and 20. What is the largest number of McNuggets that is not possible to obtain using some combination of these three box sizes?


  3. There are 100 closed windows and 100 people. The first person opens every window. The second person closes every 2nd window. The third person visits every 3rd window; if the window is closed, he opens it; if it is open, he closes it. So on and so forth. After the 100th person, how many windows are open?


  4. Three men are at a picnic. One man brought 3 loaves of bread, one man brought 4 loaves of bread. The third man did not bring any bread, but promised to pay the other 2 men the $14 he had in his pocket for a share of the bread. The men agreed, and each subsequently eats an equal share of the bread. Following the lunch, the men had a dispute as to how the $14 should be divided; what is the most fair way?


  5. Three men (A, B, C) are in a dual, where they take turns shooting. Person A gets to shoot first, Person B gets to shoot second, and Person C gets to shoot third. Person A and C are both amateur shots; Person A hits his target 1/3 of the time, person C hits his target 1/2 of the time. Person B is an expert and hits 100% of the time. Where should person A first shoot to maximize his chances of winning the game?


  6. There is a spider in the corner of a 10 ft x 10 ft x 10 ft room. The spider wants to get to the opposite corner of the room [i.e. he is in the bottom back left corner and wants to get to the top front right corner]. He can not fly; thus must stay along the wall at all times. What is the shortest distance to the opposite corner?


  7. What is the present value of a zero-coupon perpetuity?*


  8. It’s 9:45 pm, how would you go about finding the angle between the minute and hour hand?*


  9. Two boats are going at 10miles/hour. They are 5 miles from one another. How long before they hit?*


  10. What is the sum of all the numbers between one and one hundred?*


  11. If this table was full of pennies, do you think they could stack up to measure this building?*



*Source: http://royandy.wordpress.com/2007/07/01/interview-questions-investment-bank/

28 comments:

Anonymous said...

the window riddle, hmm lets see:
1st guy:100 windows open, 2nd guy: 50? windows open 3rd guy:no net change?, and so continuing this pattern, the after the 99th guy (the 3rd in the pattern) the next guy (the 1st) will reset and open all windows again, thus 100 windows open after 100 ppl. thats my quick guess:)

Anonymous said...

It is a 50% probability. There is either someone in your seat or there isn't. It is binary.

Unknown said...

for the window brain teaser...

a)after the first guy everything is open...

b)after the 2nd guy....50 are open

c)the 2nd guy ...is basically closing all of the even numbered windows

d)and the 3rd guy...is closing all of the opened odd numbered windows

the answer is 0

Anonymous said...

1. 50%
2. 43 Chicken Nuggets
3. 10 windows open
4. Guy who brought 3 loaves gets $4, other guy gets $10
5. Shooting at B gives him a 7/36 chance to win, but it's obvious without math.
6. Heading at an angle of 26.57 degrees will give a length of 22.36 feet, but this seems like too much of a calculator answer to this sort of brain teaser.

Anonymous said...

For the window question:

It comes down to looking at numbers that have an odd number of factors. It's easy to see if you just count from 1 to 10.

1 opens all the windows.
2 shuts 2,4,6,8,10...100.
3 shuts 3, opens 6, shuts 9...shuts 99.
4 opens 4, 8...100
5 shuts 5, 10...100
6 shuts 6 ... 96
7 shuts 7
8 shuts 8
9 opens 9 ... 99
10 shuts 10 ... opens 100

Any number that has an odd number of factors (1,4,9,16,25,36,49,64,81,100) will be open when all is said and done.

That means the answer is 10.

Anonymous said...

For the window question:

It comes down to looking at numbers that have an odd number of factors. It's easy to see if you just count from 1 to 10.

1 opens all the windows.
2 shuts 2,4,6,8,10...100.
3 shuts 3, opens 6, shuts 9...shuts 99.
4 opens 4, 8...100
5 shuts 5, 10...100
6 shuts 6 ... 96
7 shuts 7
8 shuts 8
9 opens 9 ... 99
10 shuts 10 ... opens 100

Any number that has an odd number of factors (1,4,9,16,25,36,49,64,81,100) will be open when all is said and done.

That means the answer is 10.

Anonymous said...

For the spider question, it's a matter of triangles. You can think of the two walls you have to cross as one long rectangle with sides of 10 and 20. It then becomes just finding the hypotenuse.

You take the square root of (100+400) and the answer is 22.36 feet.

Anonymous said...

For the spider question...I think it should be the square root of (100+200) =17.32 feet

pilania said...

formal response to first question:

generalize this problem to n people:

say f(n) is the probability that nth person sits in nth seat.

then my solution is

f(n) = 1/n*(f(n-1)+f(n-2)+....f(1))
where f(1) = 1

this recursive equation gives f(n) = 0.5 for every n...

does anybody need me to explain , how did i get this equation??

Anonymous said...

pilania,
please explain how u got to that equation

Anonymous said...

To whoever said "Shooting at B gives him a 7/36 chance to win, but it's obvious without math" for question 5 is wrong.

He is wrong because he failed to recognize that the shooters can shoot into the air.

3 men:
A (33.3% shot)
B (100% shot)
C (50% shot)

If they go in order, A should shoot in the air.

B will then shoot at C (because C is a better shot than A). Moreover, shooting at A would be stupid because he would kill A and then have a 50% of living as opposed to killing off C and having a 33.3%.

A then gets his turn again and has a 33.3% chance of living.

Yes. It's "obvious without math". It's called "Game Theory". Pwnd.

Anonymous said...

For Question 5:

To anon who said "Shooting at B gives him a 7/36 chance to win, but it's obvious without math" is absolutely wrong.

3 shooters:
A 33.3%
B 100%
C 50%

A should shoot in the air.

Then B (100% accuracy) would shoot at C (because C is next best shot). B does this because, if he kills A instead, C would have a 50% chance of killing him instead of giving the shot to A (who would have only a 33.3% chance of killing B).

The shot then goes back to A, who shoots at B with a 33.3% chance of living.

33.3% > 7/36

"it's obvious without math" true, but you need game theory.

Pwnd.

Prady said...

For the Picnic and loaves problem

The man who contributed 3 loaves should be given = (3/7)* 14 = $6

the man who contributed 4 loaves should be given = (4/7)* 14 = $8

Unknown said...

for the "time is now 9:45" question:
if you look at a wall clock the little marks between each hour at 4 marks, 5 including the next hour (from 9-10 there are 4 marks + 1 (the actual 10)) so at 9:45, the hours should be closer to 10 than 9 because it's past 9:30. by dividing 5 marks /60 mins that gives us 0.083 which multiplied by 45 mins gives us 3.75 which is where the hours are at. the angle between 9 and 12 is 90 degrees, when divided onto three hours (9, 10, and 11) it is 30 degrees for each. that means that by dividing the 3.75 represents 75% of the 5. and hence the hours are at 75% of the 30 degrees which is 22.5 degrees.

extremum said...

back to first problem

1. lets assume 1st person sits on
nth place
2. persons numbered 2 to n-1 sit on right place
3. so 101-n persons standing and 101-n seats left including seat #1 at that time.
4. The prob that Per #100 sits on Seat #100 comes out as
1/(101-x) for x in 2 to 99
0 for x = 1 or 100
5. Summing over possible values of n i.e. 2 to 100 and probability of each seat occupied by Per#1 as 1/99 ( as he does not take 1) I get a very unpleasant ans which is

1/99 * ( 1/2 + 1/3 + 1/4 + .. + 1/99)

approx log(99.5)/99

The correct ans i believe shouldnt be as ugly as this..

Thanks

extremum said...

@ prady i guess this is the fight about,,

one with three loaves shall get for what he contributes, i.e. remove what he ate i.e. 2/3
similarly for the one with 4 loaves contributes 5/3

So division would be fair if its in the ratio of what is contributed i.e. 2/5 or $4 to one with 3 loaves and $10 to the other..

extremum said...

okk.. my bad on first one...

Now the solution...

1. Prob when there are N ppl to be seater and crazy person is always 1st one of the group is
P(N)

So P(N) = E[ 1/N * P(N-n+1)]
for N >= 2
P(1) = 0
i.e. problem is the same when 1st sits on nth seat and the nth person becomes crazy..
So it can be seen as a same prob with N replaced by N-n+1, and probability of 1st of group sitting on n being 1/N
now n can be anything from 2 to N


Therefore
P(N) = 1/N ( 1 + P(2) + P(3)+..P(N-1)

replace N by N+1 and subtract two to get
P(N) = P(N+1)
and P(2) = 1/2

So 50% chance..

Anonymous said...

for the spider one, if the room is 10x10x10, and the spider is at the bottom corner of one end (i.e. floor) and wants to reach the opposite top end (ceiling), then he first has to reach a top corner, which is one hypothenuse: 10^2+10^2=200; sq. root of 200 = 14.14. Then, since the spider is already at one top corner (ceiling), all it has to go is go the length of one wall to the other top corner: 10 ft. Hence the total distance is 24.14 ft.

Anonymous said...

Almost all of you guys got the first question wrong, come on.. 50%??

Question is: What is the chance that the 100th person will sit in the 100th's seat.

So beginning with the first person, there is a 1/100 chance that the first person will sit in the 100th seat. If the first person didn't sit in there, the second person has a 99/100 (from first person) * 1/99 (from second person) chance to sit in the 100th seat...

repeating this process it is:
1/100 + 1/99*99/100 + 1/98*98/99*99/100 + ....

This is the percentage chance that the 100th person will NOT sit in the 100th seat, we simply use 1 subtract that and there you go.

To all the people thinking its 50%... come on really? by the end the 100 people get on the train every single seat is filled, what "filled or empty"...

Anonymous said...

The actual answer to number 5 is obvious - but can someone go over the math for the probability of winning against C? Theoretically, they could go on forever always missing.

Anonymous said...

Last Anonymous person- there is a 1/99 probability the first person will sit in the 100th seat. The first person is, by definition, crazy. If he sat in the first seat, he would not be crazy. Therefore, he has 99 seats to choose that will allow him to maintain his status as crazy. Therefore, your starting probability upon which the rest of your solution is based is wrong.

Unknown said...
This comment has been removed by the author.
Unknown said...
This comment has been removed by the author.
Anonymous said...

duel riddle is a popular game theory one. He should shoot into the air away from everyone. C takes out b since he's the biggest threat, leaving A a 10% chance of hitting C second time round.

Perpetuity is worthless? It pays 0% interest and the principle isn't repaid

Felix said...

Say Ak is the probability that Pk is crazy
Say Pk,i is the probability that Pk seats on seat i

Ak happens if one of the Ai and Pi,k happen for i between 1 and k-1

As there can only be one person on seat k we have
P(Ak) = sum(i=1 to k-1) P(Ai)/(100-i+1)

Then, using the trick 1/(n*(n+1))=1/n - 1/(n+1) you can prove by recurrence that P(Ak)=1/(100-k+2)

Therefor P(A100) = 1/2

Felix said...

AS P100 seat on seat 100 if and only if he isn't crazy

The result is 1/2

Anonymous said...

First one:
1/100

100th guy sits in seat 100 if he is sane
P that 2nd person is sane is 99/100
P that third is sane is 98/99 x by above
Fourth is 97/99 x by above

100th person sane: 99!/100!
Simplifies to 1/100

Anonymous said...

First question is not anywhere near as difficult as some of you made it.

Everyone will sit in their assigned seat unless it is taken... So it all depends on where the first person sits. But essentially there are 100! ways for everyone on the train to take a seat, each depending on where the previous passengers have decided to sit. There are 99! ways that include the 100th person sitting in seat #100. Thus, 99!/100! = 1/100. Which is the probability that the 100th person sits in seat 100