- 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 :-)
Hint: How would you represent this problem in a computer?
- 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:
- The most fierce pirate proposes some way to share the gold
- 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.
- 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.
- 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?
Hint #1: Try solving the problem backwards.
Hint #2: Try this problem with 5 pirates and 10 pieces of gold.
- 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?
Hint: Too easy for a hint.
- 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
Hint: Too easy for a hint.
- 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
Hint: The answer is NOT 99lb -- you'll have to do the calculations more carefully.
- 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?
Hint: Expectation = average, and the answer is NOT 13.
- 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?
Hint: What's special about the center of table?
- Registered Math
There are three registers A, B, R, and three operations A->R, B->R,
A-R->A. Program sequence B->A.
- 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__/
Hint #1: Try solving this problem from the end.
Hint #2: You can always differentiate between adjacent holes and ones that are across from each other.
- 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
Hint #1: Try solving this problem from the end.
Hint #2: You'll need to do some math.
- 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.
Hint: You'll have to prove your answer by induction.
- 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?
Hint: You should be able to save 9 out of 10 trolls.
- 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).
Hint: Consider that each weighing can have 3 different outcomes.
- 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.
Hint: The answer is 14.
- 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.
Hint: The answer to the question should not depend on who the guard is.
- 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
Hint: You can't measure 30 minutes by cutting the rope in half; but you can by lighting it from both ends.
- 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
Hint: Atos and Porthos should go together.
- 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
Hint:Only those numbers that have an odd number of divisors are left open.
- 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
Hint:You need 3 moving pointers into the array.
- 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
Hint:Bulbs have 3 states: on/off/warm.
- 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
Hint: Pointers should travel at different "speeds."
- 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
Hint: try this problem with 9 balls.
- 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
Hint: look at the problem's title
- 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
Hint: you need to use 2 different tricks.
- 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
Hint: efficient = log N, for any N.
- 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
Hint: look at the 'looping' problem above.
- 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
Hint: too easy to have a hint.
- 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
Hint: Find a way for the duck to be faster than the wolf.
- 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
Hint: try a 2x2 board.
