Technical Interview Puzzles

(followings are frequently asked in Infosys interview)

[1]. 100 Doors in a Row

Problem:

There are N doors in a row numbered from 1 to N. Initially all are closed. Then you make N passes by the N doors. In pass 1 you toggle the all the doors (1,2,3,4....)starting from the first door. In the second pass you toggle every second door(2,4,6,8,...). In the third pass you toggle all third doors(3,6,9...). Similarly you make N passes. Question is what is the state of all the doors after N passes. Normally asked version has N=100.

Solution:

The answer is that after N passes, if a number is a perfect square the corresponding door is open, because only perfect squares have an odd number of factors. All else numbered doors would remain closed.

________________________________________________________

[2]. Bumble Bee

Problem:

Two trains enter a tunnel 200 miles long (yeah, its a big tunnel) travelling at 100 mph at the same time from opposite directions. As soon as they enter the tunnel a supersonic bee flying at 1000 mph starts from one train and heads toward the other one. As soon as it reaches the other one it turns around and heads back toward the first, going back and forth between the trains until the trains collide in a fiery explosion in the middle of the tunnel (the bee survives). How far did the bee travel?

Solution:

The tunnel is 200 miles long. The trains meet in the middle travelling at 100 mph, so it takes them an hour to reach the middle. The bee is travelling 1000 mph for an hour (since its flying the whole time the trains are racing toward one another) - so basically the bee goes 1000 miles. Yup, it's a stupid interview question!:)

__________________________________________________________

[3]. 3 Light Switches

Problem:

Outside a room there are three light switches. Each switch is connected to a different light bulb inside the room. Each of the three switches can be either ON or OFF. You are allowed to set each switch the way you want it, once, and then enter the room. Determine which switch controls which bulb. How can you do it?

Solution:

Set the first two switches on, and the third one off. Wait a few minutes.

Now turn the middle switch off, and enter the room.

1. The bulb that is on must be connected to the first switch, which was left on.
2. The bulb which is off, but warm, must be connected to the middle switch.
3. The bulb that is off and cold must be connected to the third switch.

__________________________________________________________

[4]. Contaminated Pills in a Jar

Problem:
You have 5 jars of pills. Each pill weighs 10 gram, except for contaminated pills contained in one jar, where each pill weighs 9 gm. Given a scale, how could you tell which jar had the contaminated pills in just one measurement?
Solution:

1. Mark the jars with numbers 1, 2, 3, 4, and 5.
2. Take 1 pill from jar 1, take 2 pills from jar 2, take 3 pills from jar 3, take 4 pills from jar 4 and take 5 pills from jar 5.
3. Put all of them on the scale at once and take the measurement.
4. Now, subtract the measurement from 150 ( 1*10 + 2*10 + 3*10 + 4*10 + 5*10)
5. The result will give you the jar number which has contaminated pill.

________________________________________________

[5]. Cutting the Cube

Problem:

A carpenter, working with a buzz saw, wishes to cut a wooden cube 3-inches on a side (3x3x3) into 27 smaller cubes 1-inch on a side (1x1x1). He can do this easily by making 6 cuts through the cube, keeping the pieces together in the cube shape. Can he reduce the number of necessary cuts by rearranging the pieces after each cut?

Solution:
The answer is "No". The center cube has 6 faces. Separating each of those faces from its surrounding wood will require a separate cut. Thus we can't get away with fewer than 6 cuts. (No matter how clever we're at stacking the cut wood!) Some better explanation can be given from graphical point of view too, but this one is the simplest logic.. anyone can comprehend!

______________________________________________

[6]. Scrambled Box-Tops

Problem:

You have 3 boxes. 1 containing 2 black marbles, 1 containing 2 white marbles, 1 containing 1 white marble & 1 black marble. The boxes are labeled for their contents - BB, WW, BW. But someone has switched the labels so that every box is now incorrectly labeled. You are allowed to take 1 marble at a time out of any box, without looking inside. By this process of sampling you've to determine the contents of all 3 boxes. What's the smallest number of drawings needed to do this?

Solution:
Only 1 drawing is required.
Since each box is wrongly labeled. So..
                'BB' box has either WW or BW
                'WW' box has either BB or BW
                'BW' box has either BB or WW
So, if I draw 1 marble from 'BW' labeled box and
- get W marble, then it has WW, 'BB' has BW, 'WW' has BB.
- (else if) I get B marble, then it has BB, 'WW' has BW, 'BB' has WW.

______________________________________________

[7]. Asked in Microsoft Interview: Interesting Polar Bear Question

Problem: If a bear walks one mile south, turns left and walks one mile to the east and then turns left again and walks one mile north and arrives at its original position, what is the color of the bear? (Well,from the very framing of the question it is evident that we are talking about the poles, and all polar bears are white. You can also very well argue that any bear or man walking the same path will reach the same starting position if he is at north pole! The question can also be extended and that's what we are interested in. The question is how many such points exists on the surface of the globe. Well, what's your answer, is it one or infinity?)

Solution: Infinity.

There is indeed the one point exactly on the north pole where walking 1 mile south, 1 mile east then 1 mile north returns you to the starting position but there is also a circle of infinity points in the southern hemisphere.
Let us call this circle 'A'. It is formed by the points 1 mile north of another circle 'B' of circumference 1, parallel to the equator and between the equator and the south pole.
Suppose you are on 'A'. Then going 1 mile south puts you on 'B'. Travelling 1 mile east lands you up exactly where you just were on the circle (because the circumference of 'B' is 1). Then travelling north puts you back where you started.
However, 'A' is not the only circle of such points. In the same way that we constructed 'A' by taking the points 1 mile north of the circle 'B' of circumference 1, parallel to the equator, between the equator and the south pole we may take any circle 'A_n' of points 1 mile north of the circle 'B_n' of circumference 1/n (for any n in the natural numbers), parallel to the equator, between the equator and the south pole.

__________________________________________________________

[8]. Asked in Microsoft Interview: Coins on a Table

Problem: There is a table on which a number of coins are placed. You also know that there are as many coins with Head up as many coins with Tail up. Now you have to divide the coins (number of coins is even) into two equal piles such that number of coins with Heads up and Tails up in either piles be the same. The catch is you are blind folded and you cannot determine the sides (for sure).

Solution: Assume you have N heads and N tails coins initially. Youu make two piles out of them by taking m Tails and s Heads. The second pile will have N-m Tails + N-s Heads. Since the two piles are equal :

m+s = N-m + N-s
i.e. m+s = N
So we have as many heads in pile one as we have tails in pile two. So just flip.

__________________________________________________________

[9]. Asked in Google Interview: 2 Eggs Problem

Problem: Using a 100 storey building and only the two eggs, how would you find out which is the highest floor of the building you can drop the eggs from, before they break?

Solution: Use binary search with one egg till it breaks. Use linear search with the second egg till it breaks. And you have the solution. If that's not clear enough, here's the explanation..

First drop one egg from 50th (midway).
> If it breaks (no more binary search) then drop the second egg from first floor. Move up one floor at a time till it breaks.

> If it doesn't break then drop it from 75th floor.

• If it breaks then drop the second egg from 51th floor. Move up one floor at a time till it breaks.
• If it doesn't break then drop it from the 76th floor...

And thus the process continues. So best case solution = log (100), worst case solution = 50.