Question: John and Matt decide to play a game using a deck of cards. The game involves flipping two cards at a time. If both cards are black, they go into John’s pile and if both cards are red, they go into Matt’s pile. If one card is red and one card is black, they go into a discard pile. The game is played until all 52 cards have been flipped. The person with the most cards in their pile wins. If there is a tie, John wins. If Matt has more cards than John, then John pays Matt a dollar. What is the chance of Matt getting a dollar?

Answer: Any guesses? The chance of Matt getting any money is zero. Do you know why?

Say the deck is arranged in a way such that there are 13 black pairs. In this situation, John gets 13 black pairs. And since there are no other black cards left, Matt gets 13 red pairs too. So there’s a tie and John wins.

Suppose there are 12 black pairs in the deck. In this case, there would be 2 black cards left in the deck that would pair up with 2 other red cards in the deck. These 2 black cards would never be together since we have already claimed that there are only 12 black pairs in the deck. As a result, 2 pairs of cards end up in the discard pile. The remaining cards would all be red and Matt would get 12 red pairs too. So once again, there’s a tie and John wins.

We could continue this process through induction. Assuming there are 11 black pairs, there would be 4 other black cards that pair up with 4 other red cards and go into the discard pile. Once again, both John and Matt end up with 11 pairs of cards each and John wins.

Here’s a table to explain each case.

So we see that in any case, there is a tie between John and Matt. So Matt never ends up with a dollar.

Liked this post? Spread the word on Twitter and Facebook

Related posts:

1. Bulb Or No Bulb?
2. Trailing Zeros in 100 Factorial
3. Red and Blue Marbles

Question: You are given b boxes and n dollar bills. The money has to be sealed in the b boxes in a way such that without thereafter opening a box, you can give someone a requested whole amount of dollars from 0 to n. How should b be related to n for this to happen?

Answer: Stumped? Let’s think of an example to approach this problem.

Say we have $100. A good approach to distributing $100 would be the binary number system. So you’d have $1, $2, $4, $8, $16, $32 in the first six boxes. We can’t fill the next box with $64 dollars because we are only left with $37 dollars (from a total of $100). So we’d have to put $37 in the seventh box. To supply any requested amount, we’d have to use a combination of these boxes.

To find out the restrictions on the values of b and n, we have to think of different scenarios. For instance, with a million dollars and just one box, we would never be able to dispense any requested amount less than a million. However, if we are ever in a situation with more boxes than dollars, there is a never a problem.

Using this approach, we can create a table showing the best relationship between b and n

b = 1     n = up to $1
b = 2     n = up to $2 + $1 = $3
b = 3     n = up to $4 + $2 + $1 = $7
b = 4     n = up to $8 + $4 + $2 + $1 = $15

See a pattern yet? So the best way we would be able to dispense any requested amount is to have n <= 2^b – 1.

Liked this post? Let us know through our comments section!

No related posts.

Question: There are four dogs each at the corner of a unit square. Each of the dogs starts chasing the dog in the clockwise direction. They all run at the same speed and continuously change their direction accordingly so that they are always heading straight towards the other dog. How long does it take for the dogs to catch each other and where?

Answer: Let’s the dogs be A, B, C and D where A is chasing B, B is chasing C, C is chasing D and D is chasing A.

All the dogs will eventually meet in the center of the square. Since all the dogs move in symmetry, the only logical answer to the location of their meeting is the center of the square.

At any point in time, dog A is perpendicular to dog B and B perpendicular to C and so on. Dog A moves towards dog B but dog B does not move towards or away from dog A since it is moving perpendicular to dog A. Therefore, the distance that dog A needs to cover to reach dog B is the same as the original distance between them, one unit.

The speed of each of the dog towards the dog it is chasing is given by (1 + cos(t)) where t is the angle on each corner of the square.

Speed of dog = 1 + cos(90) = 1 + 0 = 1
Time needed = Distance/Speed = 1 / 1 = 1 unit.

Liked this question? Post this on Stumble, Twitter or Digg!

Have a better solution? Let us know through the comments section!

Related posts:

1. Trains and Birds
2. Chess Squares
3. Tunnel Trouble

Question: You have 50 red marbles, 50 blue marbles and 2 jars. One of the jars is chosen at random and then one marble will be chosen from that jar at random. How would you maximize the chance of drawing a red marble? What is the probability of doing so? All 100 marbles should be placed in the jars.

Answer: Seems tricky at first right? Given that the number of red and blue marbles are the same, you would tend to think that the odds are 50-50. You would try different combinations, such as 25 of each colored marble in a jar or putting all red marbles in one jar and all the blue in the other. You would still end up with a chance of 50%.

So lets think of a better way to distribute the marbles. What if you put a single red marble in one jar and the rest of the marbles in the other jar? This way, you are guaranteed at least a 50% chance of getting a red marble (since one marble picked at random, doesn’t leave any room for choice).  Now that you have 49 red marbles left in the other jar, you have a nearly even chance of picking a red marble (49 out of 99).

So let’s calculate the total probability.

P( red marble ) = P( Jar 1 ) * P( red marble in Jar 1 ) + P( Jar 2 ) * P( red marble in Jar 2 )
P( red marble ) = 0.5 * 1 + 0.5 * 49/99
P( red marble ) = 0.7474

Thus, we end up with ~75% chance of picking a red marble.

Have a better solution? Let us know through the comments section!

Related posts:

1. Pick a Random Byte
2. 10 Google Interview Puzzles
3. Probability of a Car Passing By

Question: A duck that is being chased by a fox saves itself by sitting at the center of circular pond of radius r. The duck can fly from land but cannot fly from the water. Furthermore, the fox cannot swim. The fox is four times faster than the duck. Assuming that the duck and fox are perfectly smart, is it possible for the duck to ever reach the edge of the pond and fly away to its escape from the ground?

Answer: One would think that the duck could swim directly away from the fox. So the duck would have to swim a distance r. The fox would have to cover half the circumference of the pond (pi * r). Since the fox is four times faster than the duck, we know that

(pi * r) < (4 * r)

This would make it seem like it is impossible for the duck to escape.

So how could the duck make life most difficult for the fox? If the duck just tries to swim along a radius, the fox could just sit along that radius and the duck would continue to be trapped.

The duck could swim in concentric circles, so that the fox has to continuously run along the circumference of the pond to stay on the same radius as the duck. If the duck swims near the edge of the pond, the fox could easily keep up since they would be covering approximately the same distance and the fox is four times faster. But what if the duck swam closer to the center of the pond? The duck would have to cover a smaller circumference, and could use this strategy to put some distance between the fox and itself. At a distance of r/4 from the center of the pond, the circumference of the pond is exactly four times the circumference of the duck’s path. Thus, to stay on the same radius as the duck, the fox would barely keep up.

Say, the duck circles the pond at a distance r/4 – e, where e is an infinitesimal amount. So as the duck continues to swim along this radius, it would slowly gain some distance over the fox. Once the duck is able to gain 180 degrees over the fox, the duck would have to cover a distance of 3r/4 + e to reach the edge of the pond. In the meanwhile, the fox would have to cover half the circumference of the pond (i.e the 180 degrees). At that point,

(pi * r ) > 4 * (3r/4 + e)

The duck would be able to make it to land and fly away.

Liked this question? Post this on Stumble, Twitter or Digg!

Related posts:

1. Chasing Dogs
2. Globe Walker
3. Trains and Birds

Question: You have two sticks and matchbox. Each stick takes exactly an hour to burn from one end to the other. The sticks are not identical and do not burn at a constant rate. As a result, two equal lengths of the stick would not necessarily burn in the same amount of time.  How would you measure exactly 45 minutes by burning these sticks?

Answer: This puzzle used to be asked in Wall Street interviews long time ago. It is very rare for this question to be asked now but it is a very good question to help you think a little outside the normal thought process.

The answer is really simple. Since the sticks do not burn at a constant rate, we can not use the length of the stick as any sort of measurement of time. If we light a stick, it takes 60 minutes to burn completely. What if we light the stick from both sides? It will take exactly half the original time, i.e. 30 minutes to burn completely.

0 minutes – Light stick 1 on both sides and stick 2 on one side.
30 minutes – Stick 1 will be burnt out. Light the other end of stick 2.
45 minutes – Stick 2 will be burnt out.

If you have any interesting questions, feel free to email them to support@mytechinterviews.com

Related posts:

1. Three Switches
2. Farmer’s Dilemma
3. 9 Minutes

Here is a list of 10 famous puzzles which have been asked on a Microsoft Interview. They are not in any specific order.

Clock Hands

How many times a day do the minute and hour hands of a clock overlap? Answer

Is Your Husband a Cheat?

A certain town comprises of 100 married couples. Everyone in the town lives by the following rule: If a husband cheats on his wife, the husband is executed as soon as his wife finds out about him. All the women in the town only gossip about the husbands of other women. No woman ever tells another woman if her husband is cheating on her.  So every woman in the town knows about all the cheating husbands in the town except her own. It can also be assumed that a husband remains silent about his infidelity. One day, the mayor of the town announces to the whole town that there is at least 1 cheating husband in the town. What do you think happens? Answer

100 Prisoners in Solitary Cells

100 prisoners are stuck in the prison in solitary cells. The warden of the prison got bored one day and offered them a challenge. He will put one prisoner per day, selected at random (a prisoner can be selected more than once), into a special room with a light bulb and a switch which controls the bulb. No other prisoners can see or control the light bulb. The prisoner in the special room can either turn on the bulb, turn off the bulb or do nothing. On any day, the prisoners can stop this process and say “Every prisoner has been in the special room at least once”. If that happens to be true, all the prisoners will be set free. If it is false, then all the prisoners will be executed. The prisoners are given some time to discuss and figure out a solution. How do they ensure they all go free? Answer

The Ant Problem

Three ants are sitting at the three corners of an equilateral triangle. Each ant starts randomly picks a direction and starts to move along the edge of the triangle. What is the probability that none of the ants collide? Answer

Gold for 7 days of Work

You’ve got someone working for you for seven days and a gold bar to pay them. You must pay the worker for their work at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker? (Assuming equal amount of work is done during each day thus requiring equal amount of pay for each day) Answer

Trains and Birds

A train leaves City X for City Y at 15 mph. At the very same time, a train leaves City Y for City X at 20 mph on the same track. At the same moment, a bird leaves the City X train station and flies towards the City Y train station at 25 mph. When the bird reaches the train from City Y, it immediately reverses direction. It then continues to fly at the same speed towards the train from City X, when it reverses its direction again, and so forth. The bird continues to do this until the trains collide. How far would the bird have traveled in the meantime? Answer

A Box of Defective Balls

You have 10 boxes of balls (each ball weighing exactly10 gm) with one box with defective balls (each one of the defective balls weigh 9 gm). You are given an electronic weighing machine and only one chance at it. How will find out which box has the defective balls? Answer

Globe Walker

How many points are there on the globe where, by walking one mile south, then one mile east and then one mile north, you would reach the place where you started? Answer

4 Quarts of Water

If you had an infinite supply of water and a 5 quart and 3 quart pails, how would you measure exactly 4 quarts? and What is the least number of steps you need? Answer

Four People on a Rickety Bridge

Four people need to cross a rickety bridge at night. Unfortunately, they have only one torch and the bridge is too dangerous to cross without one. The bridge is only strong enough to support two people at a time. Not all people take the same time to cross the bridge. Times for each person:  1 min, 2 mins, 7 mins and 10 mins. What is the shortest time needed for all four of them to cross the bridge? Answer

How many questions have you heard before? Post in comments.

Feel free to add to this list or leave a comment. Please Tweet, Digg or Stumble.

Related posts:

1. 10 Google Interview Puzzles
2. 100 Prisoners in Solitary Cells
3. Trains and Birds

Question: A train leaves City X for City Y at 15 mph. At the very same time, a train leaves City Y for City X at 20 mph on the same track. At the same moment, a bird leaves the City X train station and flies towards the City Y train station at 25 mph. When the bird reaches the train from City Y, it immediately reverses direction. It then continues to fly at the same speed towards the train from City X, when it reverses its direction again, and so forth. The bird continues to do this until the trains collide. How far would the bird have traveled in the meantime?

Answer: Yes, you read it right. The bird is actually the fastest moving object in the problem!

Knowing that the bird is the faster than both the trains, you would only imagine that theoretically, the bird could fly an infinite number of times between the trains before they collide. This is because you know that no matter how close the trains get, the bird will always complete its trip before the crash happens. At the time of the crash, the bird would probably get squashed between the trains!

I bet sometime in school, you learnt how to sum up an infinite series. But do we have to do that?

The concept of relative speed (rings a bell?) can work handy here. Let’s assume that the distance between City X and City Y is d miles. The trains are approaching each other at a relative speed of (20 + 15) = 35 mph. The sum of the distances covered by the trains when they collide is d (i.e. the distance between the cities). Since distance/speed gives us time, we know that the trains collide d/35 hours after they start.

Since the speed of the bird is constant at 25 mph, we know that the bird would have covered

25 * (d/35) miles = 5d/7 miles

before the trains collide.

Simple question right? Let us know if you have an even simpler solution through our comments section!

Related posts:

1. Tunnel Trouble
2. 10 Famous Microsoft Interview Puzzles
3. Chasing Dogs

Question: How many points are there on the globe where, by walking one mile south, then one mile east and then one mile north, you would reach the place where you started?

Answer: The trivial answer to this question is one point, namely, the North Pole. But if you think that answer should suffice, you might want to think again!

Let’s think this through methodically. If we consider the southern hemisphere, there is a ring near the South Pole that has a circumference of one mile. So what if we were standing at any point one mile north of this ring? If we walked one mile south, we would be on the ring. Then one mile east would bring us back to same point on the ring (since it’s circumference is one mile). One mile north from that point would bring us back to the point were we started from. If we count, there would be an infinite number of points north of this one mile ring.

So what’s our running total of possible points? We have 1 + infinite points. But we’re not done yet!

Consider a ring that is half a mile in circumference near the South Pole. Walking a mile along this ring would cause us to circle twice, but still bring us to back to the point we started from. As a result, starting from a point that is one mile north of a half mile ring would also be valid. Similarly, for any positive integer n, there is a circle with radius

r = 1 / (2 * pi * n)

centered at the South Pole. Walking one mile along these rings would cause us to circle n times and return to the same point as we started. There are infinite possible values for n. Furthermore, there are infinite ways of determining a starting point that is one mile north of these n rings, thus giving us (infinity * infinity) possible points that satisfy the required condition.

So the real answer to this question is 1 + infinity * infinity = infinite possible points!

Liked this post? Please Digg or Stumble it!

Related posts:

1. Trains and Birds
2. The Fox and The Duck
3. 10 Famous Microsoft Interview Puzzles

Question: How many times a day do the minute and hour hands of a clock overlap?

Answer: Did you think the answer was 24 times? Well if you did, it’s time you think again. Let’s do some math.

In T hours, the minute hand completes T laps. In the same amount of time, the hour hand completes T/12 laps.

The first time the minute and hour hands overlap, the minute hand would have completed 1 lap more than the hour hand. So we have T = T/12 + 1. This implies that the first overlap happens after T = 12/11 hours (~1:05 am). Similarly, the second time they overlap, the minute hand would have completed two more laps than the hour hand. So for N overlaps, we have T = T/12 + N.

Since we have 24 hours in a day, we can solve the above equation for N

24 = 24/12 + N
24 = 2 + N
N = 22

Thus, the hands of a clock overlap 22 times a day. Thus the hands of the clock overlap at 12:00, ~1:05, ~2:10, ~3:15, ~4:20, ~5:25, ~6:30, ~7:35, ~8:40, ~9:45, ~10:50. Note that there is no ~11:55. This becomes 12:00.

Have a better solution? Let us know through our comments section.

Related posts:

1. 10 Famous Microsoft Interview Puzzles
2. 9 Minutes
3. Trains and Birds