Puzzles

If you get stuck, look at the hints page.
Email me to post your own puzzles, and/or suggest better solutions and hints.

Other CS puzzle sites:

• Tech Interview
• IBM Research Labs

1. The Dangers of Drinking New
   A mad scientist has 1000 bottles of wine, one of which is poisoned, and he also has 10 laboratory mice. Any amount of the poisoned wine kills a mouse within 10 days.
   Can you help the mad scientist throw a lab party on the 11th day, having identified the poisoned bottle? Note: killing laboratory animals is allowed for this problem, even for vegetarians, like myself :-)

2. Pirates On the High Seas New
   500 pirates have just ransacked a ship that they thought would be full of treasure. Unfortunately, there were only 100 pieces of gold on the ship, definitely not enough to satisfy all the pirates. The pirates then devised the following strategy for dividing the gold:
   1. The most fierce pirate proposes some way to share the gold
   2. The pirates, being a democratic bunch, vote whether to accept the plan or not. Each pirate, including the one proposing the division, gets exactly one vote.
   3. If the pirates vote to reject the proposal, the pirate is thrown down to the sharks, and the process repeats from step 1 among the remaining pirates.
   4. If the pirates vote to accept the proposal, the gold is divided, and the remaining pirates go on to live happily ever after. In case of a tie the proposal is accepted.
   Let me also note the pirates' motivation, in case it differs from yours: each pirate wants to remain alive foremost, but given that he is alive, he wants to get as much gold as possible. Finally, all else being equal, he'd rather watch more of his comrades being fed to the sharks.

   The question: how many pirates will remain alive after the division is complete?

3. Going Around In Circles New
   A car travels around a circle one mile long. It must complete 2 rounds with an average speed of 60 miles/hour. If it traveled the first round with a speed of 30 miles/hour, what should its speed be on the second round?
   Bowery Capital, UBS Warburg

4. Chained New
   You have 5 chains, each consisting of 3 links. You can cut a link to unchain it from the rest of the chain, and you can also close the link after it has been cut. What is the minimum number of link-cuts that you will need to make in order to be able to chain all 5 chains into one?

5. Small Potatoes New
   You have 100lb of potatoes, which consists of 99% water. If, after being left in the sun, some water has evaporated, so that the potatoes are only 98% water, what is the mass of the potatoes now?
   ZS Associates

6. Card Expectations New
   What is the expected number of cards that need to be turned over in a regular 52 card deck to see the first ace?

7. Knights of the Round Table
   Two knights are playing the following game: they place identical round coins on to a round table. Whoever cannot place a coin, loses. Who wins and what is the winning strategy?

8. Registered Math
   There are three registers A, B, R, and three operations A->R, B->R, A-R->A. Program sequence B->A.

9. Open, Sesami
   You are stuck in a dark cave. There is a barrel in front of the door, with 4 holes around the perimeter (see diagram below). There is one coin in each of the holes, and if all four coins are placed the same way (either all heads, or all tails), then the cave opens. You can reach into two holes with your hands, feel which way the coin is placed, and turn over neither, either or both coins. However, once you pull your hands out, the barrel starts spinning, and you can no longer tell which coins you just touched. Can you guarantee that you will get out of the cave in less than 10 tries?

    _____
   /  x  \
   |x   x|
   \__x__/
   

10. World Series
    The World Series final consists of two teams playing each other until one of the teams wins 4 times. There are no ties, so there can be at most 7 games. You can bet on the outcome of any game, but not the series as a whole. Suggest a betting strategy that will guarantee that you win exactly $100 if your favorite team wins, and you lose exactly $100 if it loses.
    Goldman Sacks

11. Sums
    Given a sorted array of N positive integers, find in O(N) time and O(1) space the smallest integer that cannot be represented as the sum of some number of the elements of the array using each element no more than once.

12. Save the trolls The evil empire captured the good trolls. They put red or blue hats on each troll and lined them up so that they faced each other's backs. The first troll could see the colors of the hats of all the trolls in front of him (2-10), the second -- the hats of all the trolls in front of him (3-10), etc. The evils are going to ask each troll what color he thinks his hat is, and if he answers incorrectly, they execute him. The other trolls can hear what color he said, but do know whether or not he was killed. The trolls are allowed to get together and devise a strategy. They are totally not selfish, and are willing to sacrifice themselves for the benefit of the group. How many trolls can you guarantee to save?

13. Another odd ball problem 12 balls, balance scale, 3 weighings, 1 odd ball, unknown whether it's lighter or heavier than the rest. You know the story (see the the "Odd ball" problem below).

14. The crystal balls Simalar to the "How do you want your eggs?" problem below, only this time the ladder has exactly 100 steps and you have 2 balls. Devise a strategy that would minimize the number of times you'll need to drop either egg in the worst case.

15. The guards and the lions A prisoner is in a room with 2 doors. One of them leads to freedom, and another -- to a hungry lion. Each one is guarded by a guard. One of the guards is truthful, and the other is a lier, but the prisoner does not know who is who. Help the prisoner go free by asking only one question of only one of the 2 guards.

16. The burning rope You are given two ropes. If lit up, each of them burns completely in exactly one hour; however, different parts of the ropes burn at different rates, so the burning time is not proportional to the length of the rope. Your task is to measure 45 minutes using only these two ropes and an unlimited supply of matches.
    D.E.Shaw

17. The three Musketeers D'Artagnian and the three Musketeers need to cross the river. There is a bridge across the river, but only two people at a time can cross it. They have only one torch for the four of them, and they cannot cross the bridge without a light. D'Artagnian can sprint across the bridge in 1 minute, Aramis can run in 2, Atos can walk across in 5 minutes, and Porthos will take 10. How much time will D'Artagnian and the Musketeers need to cross the river?
    Microsoft

18. Infinite Corridor There are 100 doors in the MIT Infinite Corridor; initially, all of them are closed. The first student walks through the corridor and opens every door. Then, the second student walks and closes every second door; the third -- changes the state of every 3rd door, (opens the closed doors, and closes the opened ones), etc. How many doors are left open after 100 students walk through the corridor?
    i-Cube

19. The Dutch Flag Problem The Dutch flag has three horizontal stripes: Red, White and Blue. Sort an array with R's, W's and B's in place in O(n) time and O(1) space. The number of R's, W's and B's is unknown, and you are only allowed to compare and swap (possibly non-adjacent) elements.
    Interestingly, the Russian, French, and Yugoslavian flags have exactly the same colors but in different order or Orientation (RUS=WBR, FRA=BWR(vert), YUG=BWR).
    Sun Microsystems

20. Matching Bulbs There are 3 bulbs in one room and 3 switches for these bulbs in the other room. Starting in the room with the switches, match each bulb with its switch by going into the room with the bulbs only once.
    Intel

21. Looping Given a linked list, find out if it has loops (pointers into the middle of the list) in O(n) time and O(1) space, without modifying the list.
    Microsoft

22. Odd Ball You are given 8 balls, one of which is lighter than the others (all the others have the same weight). Determine which one is light one in 2 weighings using a wingscale (you put the balls on the two sides of the scales, and it tells you which side is lighter).
    Extra credit: How many weightings are needed to find a light ball out of n given balls? What if we do not know whether the odd ball is lighter or heavier?
    Decision Architects

23. Count your money There are 10 bags with thousands of identical coins in them. In all bags but one, each coin weighs 10 gram; in one bag, however, all the coins are counterfeit and weigh only 9 gram. Find the defective bag in only one weighing, using a platform scale (the one that tells the exact weight).
    Decision Architects

24. Calendar A calendar, showing the day of the month (1-31), is made out of two cubes, each with 6 faces. One digit is printed on each face, and the date is made by putting the two cubes together, showing the right numbers. Place the digits so that all dates could be shown using only the 12 faces available. All dates are 2-digit (put 01 for the 1st, etc.). The cubes can be turned in any way, and they can switch places.
    Microsoft

25. How do you want your eggs? The "softness" of the surface is measured as the highest step of the ladder from which an egg can be dropped without breaking. Give an efficient algorithm for determining the softness of the surface, given an infinite ladder and as many eggs.
    Microsoft Israel

26. RoboCops Two robots are dropped from an airplane at discrete points along a single line. Each robot has a parachute, and leaves it at the landing point after landing. Program the two robots using the language defined below, so that they meet each other. The programs are performed synchronously by both robots.

    Move_right	move one number right
    Move_left	--"-- left
    check_parachute command	execute command if and only if a parachute is under the robot
    goto LABEL	goto label in program
    :LABEL	label
    check_robot command	execute command if and only if the other robot is in the same place
    stop	stop movement, shut the lights, exit program

    
    Israeli Defense Forces, computer unit

27. Comparing apples and oranges There are 3 identcal boxes with apples, oranges and apples mixed with oranges, respectively. On each box there is a WRONG label telling about its contents. Place all labels correctly by opening just one box.
    Microsoft Israel

28. Save the duck A duck is swimming in a round pond. The wolf is running around the pond. The duck's speed is V, and the wolf's is 4V. If the duck swims to shore, and the wolf is not there to catch it, the duck is saved. Can you save the duck? For the purposes of this problem assume the duck cannot fly.
    Compugen Israel

29. The game Two players are playing a game on an NxN board. On his turn, a player puts a disc on any square S of the board. This makes only those squares that are either to the left or lower than square S "playable." The game ends when no squares are playable. The player who put down the last disc loses. Give a winning strategy.
    Compugen Israel