1- COLOR THE HOUSES (hard):
There are N houses in a row. Each house can be painted in either Red, Green or Blue. The cost of coloring each house in each of the colors is different. Figure out how to color each house such that no two adjacent houses have the same color and the total cost of coloring all the houses is as low as possible ?
....(Click here for the answer)
2- PICK-THE-COINS GAME (hard):
There are N coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.Would you rather go first or second? Does it matter? Assume that you go first, describe an algorithm to compute the maximum amount of money you can win ?
....(Click here for the answer)
3- 1000 BULBS AND 1000 PERSONS PROBLEM (medium):
In a room, there are 1000 bulbs numbered from B1 to B1000, initially all are off. There are 1000 persons present in that room, numbered from P1 to P1000. The first person (P1) comes and switches on all the bulbs, then the second guy (P2) comes and switches off every second bulb (ie. bulbs B2, B4, B6....). Then P3 comes and he alters the state of every third bulb (B3, B6, B9....). This process goes on till P1000, when finally P1000 comes and he operates on only B1000. After everybody is done, how many bulbs will remain switched on ?
....(Click here for the answer)
4- PROBABILITY OF HAVING PARKING SPOT EMPTY (easy):
A parking spot is generally unoccupied for 1/3 of the day as per probability. But, in a fine month, you saw it to be empty for 9 consecutive days, what is the probability of the parking spot being empty in the 10th day also ?
....(Click here for the answer)
5- PROBABILITY OF APPLE DROPPING ON NEWTON'S HEAD (easy):
The probability of an apple dropping on Sir Issac Newton's head in 0.30 if he sits underneath the apple tree for 30 minutes. What is the probability of an apple dropping on his head if he sits there for just 10 minutes ?
....(Click here for the answer)
6- PICK A RANDOM NUMBER FROM NUMBER STREAM (hard):
You have a stream of numbers coming in to you, from which you have to pick a random number and store it. You don't know how long the stream would be, and also you can read only one number at a time and you have the storage to store only one number. how would you choose the 'random' number from the stream ?
....(Click here for the answer)
7- GENERATE RANDOM NUMBER WITH EQUAL PROBABILITY (hard):
You have a method that generates random numbers between 1 to 5 with same probability. Using this method, how would you define another method to generate a random number between 1 to 7 with equal probability ?
....(Click here for the answer)
8- TIME MEASUREMENT WITH SAND CLOCKS (medium):
You have 2 sand clocks that can measure 7 minutes and 4 minutes respectively. How would you measure exactly 9 minutes ? exactly 10 minutes ?
....(Click here for the answer)
9- TIME MEASUREMENT WITH CANDLES (easy):
You have 2 candles that can burn for 30 minutes each. How would you measure exactly 45 minutes ?
....(Click here for the answer)
10- RATIO OF BOY AND GIRL CHILD (easy):
In a country (like ours), everybody wants a boy and not a girl child. So, a family would keep on having girl children until a boy is born, and they would stop reproducing after the desired boy is born (they don't abort girl children like we do). The probability of having boys and girls are equal for each pregnant woman. Then, at any given moment what would be ratio of boys and girls in that country ?
....(Click here for the answer)
11- FIND THE TREASURE (easy):
At the last phase of a treasure hunt, you finally reach up to a place where you see two closed doors. You know that one of the doors have the treasure behind, the other has painful death. Each door has a security guard in front of it. You also know that one of the guards always tell the truth, and the other always lies-- but they look identical and you don't know who is the truthful guy. You are allowed to ask only one of them only one question. Then, how would you determine which door has the treasure ?
....(Click here for the answer)
12- MERGE N COMPANIES (hard):
How many ways are there to merge N small companies to create a big company ?
....(Click here for the answer)
13- TELL THE COLOR OF THE CAP (hard):
100 Jews are caught by deadly Nazis. The Jews are asked to stand in a queue and they are marked with numbers from J1 to J100. And then the Nazis put on a cap on each of the Jews head. The caps are either red or blue and these are randomly chosen, ie. all the caps could be reds, or all could be blues, or 99 reds and 1 blue, or any combination is possible. In this scenario, the last person (J100) can see all the caps of the persons in front of him (J99 to J1), again J99 can see J98 to J1, ie. any Jew can see only the caps of the Jews standing in front of him. Obviously nobody can see his own cap and thus, the first person (J1) could not see any cap. Now, Hitler comes and asks each of the Jews, starting from J100, to tell the color of his own cap-- if he says it correct he will be freed, else killed. The intelligent Jews used a strategy such that at least 99 out of 100 could be saved surely. What was the strategy ?
....(Click here for the answer)
14- CLASSIC DOUBLE EGG PROBLEM (hard):
Suppose you have 2 eggs, both are identical. There is a 100 storied building with floors F1 to F100. You have to find out the particular floor which the egg would start breaking if dropped on the ground from. That is, if you drop the egg from one floor below, it will not break, but if you drop the egg from this floor or any floor above the egg will definitely break. How would you find the answer efficiently ?
....(Click here for the answer)
15- CROSS THE DANGEROUS BRIDGE (medium):
4 people need to cross a 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 ?
....(Click here for the answer)
16- DEAL WITH MIXED PILLS (easy):
The doctor has ordered you to have two pills (together) everyday. He has given you two jars labeled J1 and J2, full with those pills. The pills look identical. You are suppose to take one pill from each of the jars everyday. But, one day, by mistake you take 2 pills from J1 and 1 pill from J2 and mix them together, and then you realize that now it is impossible to detect which two are from J1 and which one is from J2. And hence you can't even return them back to the jars also. Also you don't want to throw them away and again take out two fresh pills. Then, how would you follow the doctor's order without wasting the pills ?
....(Click here for the answer)
17- FIND OUT SWITCH-BULB CONNECTION (easy):
There are two rooms in a house. In the first room there are three switches (S1, S2, S3) and in the second room there are three bulbs (B1, B2, B3). But you do not know which switch is connected to which bulb. Initially all the bulbs are off. In each room, you are allowed to enter only once. How would you determine which switch is connected to which bulb ?
....(Click here for the answer)
18- THE LAST REMAINING NUMBER IS EVEN OR ODD (medium) :
There are 50 cards in a box, each having a distinct integer (from 1 to 50) written on it, i.e. all the cards initially have different numbers-- the smallest being 1 and the biggest is 50. Now, we randomly select two cards from the box, read the numbers on them, calculate the absolute value of the difference of the two numbers, replace the number written on the first card with this absolute value, and place the first card (which is over-written just now) back into the box again, and discard the second card. Thus the process not only changes the number written on a card, but also reduces the total number of cards by 1 in the box. We keep on doing this untill only 1 card is left in the box. Can you find out if the integer written on the last card is odd or even ? Will the answer differ if we started the problem with 55 cards ?
....(Click here for the answer)
19- MAXIMIZE CHANCE OF GETTING RED BALL (medium):
You have two boxes, and 100 balls-- 50 of them are red and 50 are blue. You have to distribute those balls into those two boxes in such a manner that, if you select a box randomly, and then select a ball randomly from that box, the chance of that ball being red would be maximum. (There is no restriction over the distribution process, you can even put all the 100 balls in a single box leaving the other box empty !!)
....(Click here for the answer)
20- FIND THE TOP 3 FASTEST HORSES (hard):
There are 25 horses each with a different speed, and you have to find the top 3 fastest horses. You can organize races with taking at most 5 horses at a time. At least how many races you would have to organize to find the top 3 fastest horses ?
....(Click here for the answer)
21- FIND THE TRUTH TELLER, THE LIAR AND THE RANDOM TELLER (hard):
There are 3 people standing side by side. One of them always tells the truth (T), another always tells the lie (L), and the other tells randomly (R). You do not know who is what. You have to ask them at most 3 YES/NO type questions to find out who is what. You can ask one question to each, or all to one, or in any other possible combination-- only condition is that the total number of questions should not be more than 3, and each of these questions should be only YES/NO type questions. What questions would you ask ?
....(Click here for the answer)
22- FIND THE TRUTH TELLER, THE LIAR AND THE RANDOM TELLER AGAIN (hard):
Let us add more complications to the previous question. Suppose, those people do not speak english (though understands), and they always in their mother tongue (a language that you don't know). For any YES/NO type question the men would answer either KA or JA (instead of YES/NO)-- but you don't exactly know which word means YES and which one means NO. Now, what questions would you ask ?
....(Click here for the answer)
23- FIND THE BOX CONTAINING GOLD (easy):
There are 3 boxes. Two of the boxes are empty and one box has gold inside it. Each box has a label on top of it. Two of the labels are true, the other is false. The label on the first box says "I don't have gold", the label on the second box says "I don't have gold" , and the label on the third box says "Gold is in the second box". Which box really has the gold ?
....(Click here for the answer)
24- FIND THE PERSISTENCE OF THE NUMBER (hard)(this puzzle was coined by the legend Martin Gardner):
A number's persistence is the number of steps required to reduce it to a single digit by multiplying all its digits to obtain a second number, then multiplying all the digits of that number to obtain a third number, and so on until a one-digit number is obtained. For example, 77 has a persistence of four because it requires four steps to reduce it to one digit:
77 -----[step 1 : 7x7]-----------> 49 ------[step 2 : 4x9]----------> 36 ------[step 3 : 3x6]----------> 18 ------[step 4 : 1x8]----------> 8
The smallest number of persistence one is 10, the smallest of persistence two is 25, the smallest of persistence three is 39, and the smaller of persistence four is 77.
What is the smallest number of persistence five ?
....(Click here for the answer)
25- COLOR OF THE REMAINING MARBLE (hard):
You initially have a box that contains some red marbles and some blue marbles, and a large bag of extra blue marbles.You are asked to repeat the following process until there is a single marble left in the box:
--Randomly select two marbles from the box.
--If the marbles are of the same color, throw them both away, and insert an extra blue marble in the box, taking it from the large bag.
--If the marbles are of different colors, then return the red marble to the box and throw away the blue one.
Prove that the process definitely terminates. Is it possible to say about the color of the final remaining marble as a function of the numbers of blue and red marbles initially in the box ?
....(Click here for the answer)
26- 5 PIRATES DISTRIBUTE 100 GOLD COINS (hard):
There are 5 very intelligent pirates P1, P2...P5 (in their decreasing order of seniority, P1 is the most senior and P5 is the most junior) . The most senior pirate is by default the captain of the group. They have 100 gold coins. The captain has to propose a way to distribute those coins among the members of the group. If alt least half of the group members (including the captain himself) support that proposal , then the coins are distributed in that manner. Otherwise, the captain is killed, and the next most senior member becomes the new captain, and he proposes a new distribution. The process of distribution may go on until there is a solution. How can the captain (P1) find out a way go get the most of the gold coins ?
....(Click here for the answer)