..MindWrite..

Posts Tagged ‘puzzles’

Some Interview puzzles by Apple

Posted by guptaradhesh on April 18, 2013


http://www.businessinsider.com/apple-brain-busting-interview-questions-answers-2012-6?op=1

Posted in puzzles/ algorithms, tech | Tagged: , , , | Leave a Comment »

3000 bananas and 1000 miles and a camel?

Posted by guptaradhesh on December 1, 2010

This seems a common puzzle but has a good logical solution. My TA for algorithms subject posted it on his webpage and I then worked around to figure out the solution. Here is a good solution explanation which I found somewhere on web:

It initially seems that the answer is 0 since it would take 3 trips to the market and the camel will have eaten all 3000 bananas by then. But this doesn’t take into account that his load is going to be reduced along the way as the camel eats the bananas.

Let’s take it mile by mile. Since initially there are 3000 bananas and the camel only can carry 1000 at a time, the camel must make 3 trips forward: forward with the 1st 1000, back, forward with the 2nd 1000, back, and forward with the last 1000. Note that it takes 3 trips forward and 2 trips back to go the mile. For the 1st mile the camel carries 1000 bananas forward and eats 1, it eats 1 banana on the way back, carries 1000 bananas forward and eats 1, eats 1 going back, and 1000 bananas forward and eats 1. So, after the 1st mile there are 1000 – 1 – 1 + 1000 – 1 – 1 + 1000 – 1 or 2995 bananas left. So initially, for every mile traveled forward (in 3 trips), the camel eats 5 bananas.

However, after 200 miles the load will be down to 2000 bananas and the camel only needs to make 2 trips forward: forward, back, forward. For each of the next 333 and 1/3 miles the camel will eat 3 bananas to carry the load ahead. So after 533 1/3 (200 + 333 1/3) miles the load will be eaten down to 1000 bananas.

For the next 466 2/3 miles till the camel gets the market, it will eat 1 banana per mile to carry the load. 1000 – 466 2/3 = 533 1/3 bananas left. So the camel will eat a total of 200 * 5 + 333 1/3 * 3 + 466 2/3 = 2466 2/3 bananas to get the entire 3000 bananas to market so the grower will have 533 1/3 bananas left to sell. Maybe 533 because who would want to eat a banana 2/3 of which a smelly camel has eaten. The script accepted 532, 533, 533 1/3, 533.333, and 534 depending on rounding and fractions.

Also, he’ll have to sell his camel there because he doesn’t have the bananas to get it back.

Posted in puzzles/ algorithms | Tagged: , , , | 1 Comment »

Some very simple “Probability” problems

Posted by guptaradhesh on November 26, 2010

1. In a lotto game, one has to choose 6 numbers from a total of 40.  Julio has chosen 1, 2, 3, 4, 5, 6.  Alison has chosen 39, 1, 17, 33, 8, 27.  Who has a greater chance of winning?

A. Julio has a greater chance of winning.
B. Alison has a greater chance of winning.
C. Julio and Alison have the same chance to win.

2. If you roll two dice simultaneously, which of the following has a greater chance of happening?
A. Getting the pair 5-6.
B. Getting the pair 6-6.
C. Both have the same chance.

3. The likelihood of getting heads at least twice when tossing three coins is…

A. Smaller than
B. Equal to
C. Greater than

…the likelihood of getting heads at least 200 times out of 300 times.

Answers:
1. C. Julio and Alison have the same chance to win.  (B option looks tempting though)
2. A: Getting the pair 5-6
3. C: The likelihood of getting heads at least twice when tossing three coins is greater than the likelihood of getting heads at least 200 times out of 300 times

Posted in puzzles/ algorithms | Tagged: , | Leave a Comment »

Birthday Paradox

Posted by guptaradhesh on November 26, 2010

Something amazing paradoxical given by probability which is hard to accept in real life.

I had to sit and analyze the proof to accept this:

“In a room of just 23 people there’s a 50-50 chance of two people having the same birthday. In a room of 57 there’s a 99% chance of two people matching.”

Here is the explaination:  (reference: http://mathworld.wolfram.com/)

Consider the probability Q_1(n,d) that no two people out of a group of n will have matching birthdays out of d equally possible birthdays. Start with an arbitrary person’s birthday, then note that the probability that the second person’s birthday is different is (d-1)/d, that the third person’s birthday is different from the first two is [(d-1)/d][(d-2)/d], and so on, up through the nth person. Explicitly,

Q_1(n,d) = (d-1)/d(d-2)/d...(d-(n-1))/d
=  ((d-1)(d-2)...[d-(n-1)])/(d^(n-1)).
 Q_1(n,d)=(d!)/((d-n)!d^n),  

so the probability P_2(n,d) that two or more people out of a group of n do have the same birthday is therefore

P_2(n,d) = 1-Q_1(n,d)
= 1-(d!)/((d-n)!d^n).

If 365-day years have been assumed, the number of people needed for there to be at least a 50% chance that at least two share birthdays is the smallest n such that P_2(n,365)>=1/2. This is given by n=23, since

P_2(23,365) = (38093904702297390785243708291056390518886454060947061)/(75091883268515350125426207425223147563269805908203125)
 approx 0.507297.

Hence the astounding Birthday Paradox..

Posted in puzzles/ algorithms | Tagged: , , | Leave a Comment »