Home > Problem of the Week > Archive List > Detail

 << Prev 2/1/2009 Next >>

## Interview "Thinks"

Consider this Question: Imagine a road that joins three cities (at the vertices of an equilateral triangle). Each town is exactly the same distance from each other, plus the roads are identical in their ability to be negotiated via a car. Mr. Jones decided to travel to all three cities, traveling at the same rate between each town. It takes him one and one-half hours to travel from the first city to the second, and one and one-half hours to travel from the second city to the third. However, it takes him only 90 minutes to travel back to the first city. How can this be?

The above "poser" is similar to others asked as part of "actual" Microsoft interviews. How would you do on the following other examples:

• Why is a manhole cover round?
• How many cars are there in the USA? (Or, How many gas stations are there in the USA?)
• How many manhole covers are there in the USA?
• You've got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker?
• One train leaves Los Angeles at 15mph heading for New York. Another train leaves from New York at 20mph heading for Los Angeles on the same track. If a bird, flying at 25mph, leaves from Los Angeles at the same time as the train and flies back and forth between the two trains until they collide, how far will the bird have traveled?
• Imagine a disk spinning like a record player turn table. Half of the disk is black and the other is white. Assume you have an unlimited number of color sensors. How many sensors would you have to place around the disk to determine the direction the disk is spinning? Where would they be placed?
• Imagine an analog clock set to 12 o'clock. Note that the hour and minute hands overlap. How many times each day do both the hour and minute hands overlap? How would you determine the exact times of the day that this occurs?
• You have two jars, 50 red marbles and 50 blue marbles. A jar will be picked at random, and then a marble will be picked from the jar. Placing all of the marbles in the jars, how can you maximize the chances of picking a red marble? What are the chances of getting a red marble using your scheme?
• Pairs of primes separated by a single number are called prime pairs. Examples are 17 and 19. Prove that the number between a prime pair is always divisible by 6 (assuming both numbers in the pair are greater than 6). Now prove that there are no "prime triples."
• There is a room with a door (closed) and three light bulbs. Outside the room there are three switches, connected to the bulbs. You may manipulate the switches as you wish, but once you open the door you can't change them. Identify each switch with its bulb.
• Suppose you had 8 billiard balls, and one of them was slightly heavier, but the only way to tell was by putting it on a scale against another. What's the fewest number of times you'd have to use the scale to find the heavier ball?
• Imagine you are standing in front of a mirror, facing it. Raise your left hand. Raise your right hand. Look at your reflection. When you raise your left hand your reflection raises what appears to be his right hand. But when you tilt your head up, your reflection does too, and does not appear to tilt his/her head down. Why is it that the mirror appears to reverse left and right, but not up and down?
• You have 4 jars of pills. Each pill is a certain weight, except for contaminated pills contained in one jar, where each pill is weight + 1. How could you tell which jar had the contaminated pills in just one measurement?
• The SF Chronicle has a word game where all the letters are scrambled up and you have to figure out what the word is. Imagine that a scrambled word is 5 characters long: How many possible solutions are there? What if we know which 5 letters are being used? Develop an algorithm to solve the word.
• There are 4 women who want to cross a bridge, but begin on the same side. You have 17 minutes to get all of them across to the other side. It is night and there is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each woman walks at a different speed. A pair must walk together at the rate of the slower woman's pace.
Woman 1: 1 minute to cross
Woman 2: 2 minutes to cross
Woman 3: 5 minutes to cross
Woman 4: 10 minutes to cross
For example if Woman 1 and Woman 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Woman 4 then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission. What is the order required to get all women across in 17 minutes? Now, what's the other way?
• Given an infinite supply of water and a 5 quart and 3 quart pail, how to measure exactly 4 quarts?
• You have a bucket of jelly beans. Some are red, some are blue, and some green. With your eyes closed, pick out 2 of a like color. How many do you have to grab to be sure you have 2 of the same?
• If you have two buckets, one with red paint and the other with blue paint, and you take one cup from the blue bucket and poor it into the red bucket. Then you take one cup from the red bucket and poor it into the blue bucket. Which bucket has the highest ratio between red and blue? Prove it mathematically.

Source: http://www.sellsbrothers.com/fun/msiview/default.aspx?content=question.htm#algs

Hint: The best advice: Read the problem carefully...stop and think...be creative if necessary...and have fun!

Solution Commentary: Sorry...you're the one being interviewed for the job, so you need to determine your own creative responses.