1. There is a village of wizards and a village of dwarves. Once a year, the wizards go over to the village of dwarves and line all the dwarves up in increasing height order, such that each dwarf can only see the dwarves smaller than himself. The wizards have an infinite supply of white and black hats. They place either a white or black hat on the head of each dwarf. Then, starting with the tallest dwarf (in the back of the line), they ask each what color hat he is wearing. If the dwarf answers incorrectly, the wizards kill him (the other dwarves can hear his answer, but can't tell if he was killed or not). What strategy can the dwarves use to minimize the number of dwarves that are killed? What is the most number of dwarves that will be killed using this optimal strategy?
  2. Consider a two-player game played on a circular table of unspecified diameter. Each player has an infinite supply of quarters, and take turns placing a quarter on the table such that it is completely on the table and does not overlap with any other quarters already played. A player wins if he makes the last legal move. Which player (if any) has a strategy that will guarantee a win, and what is that strategy?
  3. How do you reverse the order of the words (not the characters) in a string of length n in with constant extra space in linear time?
  4. How do you rotate a string of length n by m characters with constant extra space in linear time (wrt n)?
  5. Consider a rectangular cake with a rectangular section (of any size or orientation) removed from it. How do you divide the cake exactly in half with only one cut? (solution)
  6. You have a bar of chocolate that consists of n x m square blocks. If you can only break one piece at a time, how many breaks are necessary to break the original n x m piece into n*m 1 x 1 pieces? How many are sufficient?
  7. How do you quickly count the number of set bits in a 32-bit integer in linear time (with respect to the number of set bits)? In constant time?
  8. Given an array of size N that contains values between 1 and N-1, find the duplicate element (assuming there is only one). If it contains values between 1 and N+1, how would you find the missing element (again assuming there is only one missing)? Do each in O(N).
  9. Give a one-line C expression to test whether an unsigned int is a power of two.
  10. How many points are there on the globe where by walking one mile south, one mile east and one mile north you reach the place where you started?
  11. Given a singly linked list, determine whether it contains a loop or not.
  12. Every day, Joe arrives at the train station from work at 6pm. His wife leaves home in her car to meet him there at exactly 6pm, and drives him home. One day, Joe gets to the station an hour early, and starts walking home, until his wife meets him on the road. They get home 20 minutes earlier than usual. How long was he walking? Distances are unspecified. Speeds are unspecified, but constant.
  13. How do you divide a cake among n people, maximizing fairness?
  14. In your cellar there are three light switches in the OFF position. Each switch controls one of three light bulbs on floor above. You may move any of the switches but you may only go upstairs to inspect the bulbs one time. How can you determine the switch for each bulb with one inspection?
  15. Alice and Bob are on separate islands. Bob is sick, and Alice has the medicine. Eve has a boat and a chest that can be locked. She is willing to transport objects between Alice and Bob, but only in the chest, and if the chest is unlocked, she will steal whatever is inside. If both Alice and Bob have a padlock and a key such that their own key only opens their own lock, how can Alice send Bob the medicine so that Eve won't steal it?
  16. Write some code to convert a positive integer into base minus 2. That is, whereas base 2 has a 1's place, a 2's place, a 4's place, etc., base minus 2 has a 1's place, a minus 2's place, a 4's place, a minus 8's place, ... (-2)^n.
  17. A couple invites n-1 other couples to dinner. Once everyone arrives, each person shakes hands with everyone he doesn't know. Then, the host asks everyone how many hands they shook, and each person replies with a different number. Assuming that everyone knows his or her own spouse, how many hands did the hostess shake?
  18. Two robots start at different places on the same linear track. What one program can you give to both robots to guarantee that they meet? The the program may consist only of the instructions move_left n, move_right n (where n is the number of spaces to move), if statements while loops, and the boolean values at_own_start and at_other_robots_start (note that you can't use other variables or counters).
  19. Which offer is better and why?
    1. You are to make a statement. If the statement is true, you get exactly $10. If the statement is false, you get either less than or more than $10 but not exactly $10.
    2. You are to make a statement. Regardless of whether the statement is true or false, you get more than $10.
  20. You have two ropes and a box of matches. Each rope takes exactly one hour to burn, but they may not necessarily burn evenly -- i.e., the first half might burn in the first 10 minutes and the second in the remaining 50). How can you measure out 45 minutes by just using these two ropes?
  21. Consider three identical airplanes starting at the same airport. Each plane has a fuel tank that holds just enough fuel to allow the plane to travel half the distance around the world. These airplanes possess the special ability to transfer fuel between their tanks in mid-flight. Devise a scheme that will allow one airplane to travel all the way around the world, landing only at the original airport.
  22. You are at the bottom of the elevator shaft of a 100 story building. You see 21 wires labelled 1...21. The wires go up to the 100th floor where the ends are labelled A...U, but you don't know how they correspond to the ends at the bottom. You have a battery, a light bulb, and many small wires. How can you determine the pairing between the numbers and letters by only making one trip to the 100th floor and back down?
  23. A woman starts paddling upstream in a canoe, and after one mile, encounters a log floating with the current. She continues to paddle upstream for onehour, then turns around and paddles downstream, until she returns to the dock where she started. If the woman and the log reach the dock at exactly the same time, how fast was the current flowing? Assume all speeds are constant.
  24. Consider a centrifuge with 12 slots for test tubes. When you use a centrifuge, the tubes must be placed in the slots so that they are radially balanced (we can assume all tubes have the same mass). For example, for 3 tubes, you would place them in slots 4, 8 and 12. How can you place exactly 5 tubes in the centrifuge so that they are radially balanced?
  25. You are on a strict medical regimen that requires you to take two types of pills each day. You must take exactly one A pill and exactly one B pill at the same time. The pills are very expensive, and you don't want to waste any. So you open the bottle of A pills, and tap one out into your hand. Then you open the bottle of B pills and do the same thing -- but you make a mistake, and two B pills come out into your hand with the A pill. But the pills are all exactly identical. There is no way to tell A pills apart from B pills. How can you satisfy your regimen and take exactly one of each pill at the same time, without wasting any pills?
  26. Write an algorithm to find a given element in an n by n matrix where the rows and columns are monotonically increasing.
  27. General Alice and General Bob, commanders of the allied armies A and B, respectively, are camped in the mountains on either side of a valley. Alice and Bob would like to attack enemy army C, camped in the valley below. Army A by itself is unable to defeat army C, as is army B, but a coordinated attack by A and B at the same time will secure a victory for Alice and Bob. However, the only way Alice and Bob can communicate is by sending messengers through the valley, who may or may not get captured en route by the enemy army C. Is there an algorithm by which Alice and Bob can coordinate an attack on army C so as to secure their victory?
  28. Consider a circular race track with n gas stations spaced along it, each containing a fixed amount of gas. You are given an array containing the distances between consecutive gas stations and an array containing the amount of gas at each. Suppose the total amount of gas at all the gas stations is the same as the number of miles around the race track. Your car gets one mile to the gallon, but its gas tank has an unlimited capacity. Where do you start your car along the race track to guarantee that you get all the way around without running out of gas? Do this in O(n) time.
  29. Given an array of n integers, find all Pythagorean triples in the array, that is, three elements such that a2 + b2 = c2. Do this in O(n2) time.
  30. You are on a spaceship that has a computer with n processors. Suddenly, the spaceship gets hit with an alien laser beam, and some of the processors are damaged. However, you know that more than half of the processors are still good. You can ask one processor whether it thinks another processor is good or bad. A good processor will always tell the truth, but a bad one will always lie. A 'step' consists of asking one processor if it thinks another processor is good or bad. Find one good processor, only using n-2 steps.
  31. Given an array of n integers, where one element appears more than n/2 times, find that element in linear time and constant extra space.
  32. A spinning disc is painted black on one half and white on the other (i.e., the line forming the border between the black and white regions of the disc is a diameter of the disc). The disk is spinning on a turntable in an unknown direction at an unknown speed. You have special video cameras that can observe the color of a single point on the disc. How many cameras do you need to determine the direction the disc is spinning?
  33. Create an equilateral triangle using three toothpicks. Now add three more equilateral triangles of the same size as the original using only three more toothpicks.