11. How much would you charge
to wash all the windows in Seattle?
The first step here is to estimate the population of Seattle.
The U.S. Census recently put it at 594,000 (city limits) or 3.26
million (metro area). In a job interview, no one would fault you
for saying Seattle has about a million people.
How many windows are there per Seattle resident? In Manhattan,
young people count themselves lucky to have one window. Seattle is
different; apartments are larger, and more people live in houses
with panoramic windows overlooking evergreen forests. Many houses
and townhouses are two story. A decent guess, favoring the
convenient round number, is ten residential windows per
There are also windows at places of work, Starbucks, department
stores, airports, concert halls, and so forth. This probably
doesn't add all that much to the per capita total. The average
cubicle has no windows. A big-box store has little surface area
(and few windows) relative to its volume. The windows in public
spaces like restaurants and airports are shared among the huge mass
of people using them.
Don't forget windows in cars. (You might ask the interviewer
whether to count them.) A car is going to have four windows at bare
minimum, often twice that. But big 4x4s are driven by big families
and don't add many windows per capita.
A reasonable guess is that windows outside the home account for
another ten per person. This comes to twenty windows per Seattle
resident. Assuming a population of a million, there are about
twenty million windows to be cleaned.
How much should you charge to wash a window? With the windows in
your home, it takes a few spritzes of Windex, a few paper towels,
and a few seconds. Some of the windows in Seattle are huge, like
those in the restaurant atop the Space Needle, and they're high up,
requiring special crews, special equipment, high workers' comp
rates, and considerable guts.
Someone knowing what he's doing could probably clean one side of a
typical window a minute, given that most are small. That means
cleaning "a window" (both sides) in two minutes. That comes to
thirty windows an hour.
Say the average window washer makes $10 an hour. Throw in
another $5 an hour for supplies and insurance. That's $15 for an
hour's work, which cleans thirty windows. Cost per window: 50
cents. Twenty million windows times 50 cents is $10 million. This
question is used at Amazon and Google. Just so you don't miss the
joke, such as it is, Windows is another company's registered
12. How much toilet paper
would it take to cover the entire state?
A square of toilet paper is about 4 X 4 inches. Nine squares, in
a 3 X 3 grid, would then make a square foot. Let's call that "about
10" squares to a square foot. A roll of toilet paper has maybe 300
squares. Then a roll is about 30 square feet.
A mile is about 5,000 feet. A square mile is therefore 5,000 X
5,000 or 25 million square feet. The number of rolls of toilet
paper needed to cover a square mile would be 25 million divided by
30. For Fermi question purposes, 25 is practically the same as 30.
Call it a million rolls of toilet paper to the square mile.
Greater London is more or less the area contained by the M25
motorway, which is almost circular. It takes about two hours to go
round it at 50mph. This makes its circumference 100 miles. As a
circle's diameter is its circumference divided by pi (roughly 3),
the M25's diameter is 100 ÷ 3, which is about 30 miles. So, its
radius is 15 miles. A circle's area is given by πr2, which means
the area contained is approximately 3 X 15² = 675 square miles. To
cover it, you'd need 675 X 1 million rolls. That's 675 million
13. How do you find the
closest pair of stars in the sky?
This is the "closest pair" problem, well
known to computer scientists. The human eye can often spot the
closest pair of stars (or points in a plane) at a glance, just as
the eye can tell whether a face is male or female or solve a
Captcha. Microprocessors can't readily do any of these things.
Algorithms for solving the closest-pair problem were intensively
studied in the 1970s and are now a building block of the digital
world. Even your smartphone has apps that use them, for purposes
ranging from mapping to games to cameras. It's part of how our
clever devices are starting to "see."
This means that the interviewer is really asking a technically
trained candidate, "Were you paying attention in algorithm class?"
More specifically: given the co-ordinates of a large number of
random points in a plane, how can a computer, with no visual
cortex, tell which pair is closest by pure computation?
One inefficient approach is to compute the distance between
every pair of stars. That's a lot of calculations when N is a large
number. But it's not actually necessary to check the distance
between every pair of stars, only those that are "reasonably
close." Unfortunately, computers are stupid. They can't tell which
pairs are "reasonably close" unless they do the maths.
The optimal closest-pair algorithm goes like this. Mentally split
the sky in two. There's a right half and a left half, each with N/2
stars. Keep partitioning the sky into quarters, eighths,
sixteenths, thirty-seconds, and so forth. The cuts are all to be
made vertically (or from celestial north to south).
A suburbanite will see maybe a thousand stars in his hazy,
light-polluted sky. It therefore takes about ten halvings to end up
with strips of sky so thin that they contain about two naked-eye
stars each (210 is 1,024).
The diagram on page 250 gives you the basic idea. Compute the
distance between each strip's star pair. That's vastly less work
than computing distances between all the stars.
A complete doofus might think that you're almost done. Find the
strip with the closest pair of all, and that's it! Hardly -- look
at the diagram. Because the strips are so long and narrow, the
closest pair within a strip may not be so close at all. The closest
pair in the whole sky is likely to be two stars straddling two
strips. If you look below, I've circled a straddling pair in the
It's necessary to have an algorithm for knitting together two
adjacent slices. You give the algorithm the closest pair in the
left slice and the closest pair in the right slice, and then it
deduces the closest pair in the combined left- plus-right slice.
This algorithm would then be applied, over and over, to create
slices twice as wide, four times as wide, eight times, and so
forth. After ten stages of knitting together, we'd be back to a
"slice" consisting of the whole sky.
We'd also know the closest pair in the whole sky. The
knitting-together algorithm works like this. Given two adjacent
slices, inspect a zone centered on the dividing line to see whether
it's got a pair closer than any in either half. If it does, then
that will be the closest pair in the combined slice.
Take the closest pair wholly within the right or left slice and
call the distance between its stars d. Think of d as the distance
to beat. We need to search within distance d of the dividing line
for possible straddling pairs.
The zone is a 2d- wide strip. This can be efficiently done. You
might be thinking, "Sure, whatever." Computer scientists have a way
of worrying about worst-case scenarios (which the user experiences
as bugs). The stars in the zone can be readily sorted by their
vertical coordinates. For each such star, it's necessary to check
distances to stars within d of it, up or down. A simple diagram
(facing page) proves that there can be only six stars to check at
most. That's nicely manageable.
Here we want to make sure that Betelgeuse, just to the left of
the dividing line, doesn't form a close line-straddling pair with a
star on the right. This defines a d X 2d box to check. Since we
already know that no two stars on the right are within d of each
other, there can be only six stars, at the very most, that fit
within the box.
If you haven't studied computer science, your head is probably
spinning. For coders, this question should be easier than the
brainteasers -- it simply asks them to recite what they learned at
There is an offbeat answer that rates mention. Astronomy buffs
may correctly point out that there are two kinds of close star
pairs. They are binary stars (two stars orbiting around each other,
the way the earth orbits the sun) and optical doubles (unrelated
stars that just happen to look close in the sky, as seen from the
earth). Given the profound emptiness of space, it's all but a
certainty that the closest pair of stars in the earth's sky will be
Not only that, but there are eclipsing binaries, where the
orbital plane is so close to our line of sight that the two stars
actually pass behind and in front of each other. The most famous
example is Algol, a visible star in the constellation Perseus.
Algol looks like a single star to the eye and to the most powerful
telescopes. Every three days, its brightness varies. Astronomers
have determined that Algol is really two stars whose orbits look
like this, to scale:
When one star partly blocks the other, Algol looks dimmer, even
to the unaided eye. During an eclipse, there is no distance between
the two stars' disks. They actually touch and overlap in the sky.
That's as close as a pair of stars can get.
How do you find the closest pair? The astronomer's answer is that
eclipsing binaries are identified by their regularly varying
brightness and spectroscopic signatures.
14. Can you swim faster
through water or syrup?
Isaac Newton and Christiaan Huygens debated this question in the
1600s, without resolving it. Three centuries later, two University
of Minnesota chemists, Brian Gettelfinger and Edward Cussler, did a
syrup-versus-water experiment. Maybe it's not so surprising that it
took so long. Cussler said he had to obtain twenty-two approvals,
including permission to pour massive quantities of syrup down a
drain. He had to say no thanks to enough free corn-syrup to fill
twenty lorries because it was judged hazardous to the Minneapolis
sewer system. Instead he used guar gum, an edible thickener used in
ice cream, shampoo, and salad dressing. About six hundred pounds of
the stuff transformed a swimming pool into something that "looked
Gettelfinger, an Olympic- hopeful swimmer, had the unique
experience of diving in. As to the outcome, I will leave you in
suspense for a bit longer. The findings were published in a 2004
article in the American Institute of Chemical Engineers Journal.
The next year, Gettelfinger and Cussler won the 2005 Ig Nobel Prize
in Chemistry. The Ig Nobels are the silly counterpart to the
better-known prizes awarded in Stockholm, and they automatically
get news-of- the- weird coverage. The media attention was
apparently responsible for the syrup riddle's revival as a uniquely
sadistic interview question.
In the great syrup swim-off, the guargum glop's viscosity was
about twice that of water. Its density was virtually the same as
that of plain water. That was important because, as swimmers have
long known, people swim faster in denser saltwater. Like a ship, a
swimmer's body rides higher in saltwater, encountering less drag.
Gettelfinger and other Minnesota students did laps through both
water and "syrup." They tried the standard strokes: backstroke,
breaststroke, butterfly, and freestyle. In no case did the speeds
vary between fluids by more than a few percentage points. There was
no overall pattern favoring the glop or the water.
This meant that Newton was wrong: he thought syrup's viscosity
would slow swimmers. Huygens correctly predicted there would be no
difference in speed. Gettelfinger and Cussler's paper supplies the
reason. Think of the way smoke rises from a cigarette. For a few
inches, the smoke rises in a sleek vertical column.
Above that, it breaks up into complicated swirls and eddies. The
swirls are turbulence. Turbulence is bad for jet planes,
speedboats, and anything that wants to cut quickly through a fluid.
Because the human body is not optimized for swimming, we create a
ridiculous amount of turbulence, which we then fight in our
struggle to pull ourselves through the water. The turbulence
produces much more drag than the viscosity does. Relatively
speaking, the viscosity hardly matters. As the turbulence is
similar in water and syrup, the swimming speed is about the same,
The flow of water is much less turbulent for a fish, and even
less so for a bacterium -- which would swim slower in syrup.
Is this a fair interview question? Cussler told me that a
background in computer science "is probably of no use" in answering
the syrup question. But he added, "Anyone with sophomore physics
should be able to answer it." As a physics graduate, I'm willing to
bet that's optimistic. At any rate, most of those confronting this
question on a job interview won't know much about the physics. Good
responses invoke simple, intuitive analogies to explain why the
answer needs to be determined by experiment. Here are four
1. You can't swim in the La Brea Tar Pits. Some fluids are too
thick to swim in. Ask the mastodons in the tar pits. Imagine trying
to swim in liquid cement or quicksand. Clearly, swimming is slower
in very thick fluids than in water. Even though there's more to
push against, you swim slower, or not at all.
2. "Syrup" covers a lot of territory. The question doesn't ask
about pitch or quicksand but rather "syrup." There is maple syrup,
cough syrup, chocolate syrup, high-fructose corn syrup, and the
kind they sip in nightclubs, with consistencies ranging from watery
thin to the crud left in the bottom of an old tin of golden syrup.
The question is unanswerable unless you know the exact type of
syrup -- or can prove that swimming is slower in every
3. Cite Darwin. Suppose there's an optimum level of viscosity in
which swimming speed is at a maximum. Is there any reason to
believe that H20 just happens to be at that optimum level for
swimming? You might say yes, were you an insightful fish. Evolution
has streamlined fish to "fit" the way water flows over their sleek
bodies. Humans are not very fishlike, and the way we swim is not
much like the way a fish swims. Neither people nor our immediate
ancestors have spent much gene-pool quality time in the pool -- or
in rivers, lakes, and oceans. Swimming is something we do, like
hang gliding, but we're not built for it. A creature built for
doing the Australian crawl would look very different from a human.
Edward Cussler noted, "The best swimmer should have the body of a
snake and the arms of a gorilla." It might not be surprising to
find that people could swim faster in something with a different
viscosity than water. Nor would it be surprising to find that the
speed was the same over a wide range of viscosities.
4. Swimming is chaos. The dynamics of liquids and gases is a
textbook example of chaos. It is so dependent on the granular
details as to defy prediction. That's why aircraft designers need
wind tunnels to test their designs. The unstreamlined human body,
with its relatively awkward movements in water, only complicates
things further. This is a question that needs to be tested with an
experiment, using the exact type of "syrup" in question.
Cussler's Ig Nobel Prize acceptance speech boiled all this down
to six words: "The reasons for this are complicated."
15. It is difficult to
remember what you read, especially after many years. How would you
In a few years, practically all reading will be on digital
screens of some kind. It's possible to envision a personal reading
agent keeping track of everything you've read, on any device --
from e-mails and tweets to electronic books and magazines. This
agent or its data would migrate from hardware device to device and
follow you throughout life.
• The agent would index all that text so that you'd be able to
do a keyword search.
• The agent would let you annotate things you read anywhere (as
you can with e-book readers). The simplest annotation would be a
highlight, essentially meaning "I may want to remember this later!"
The highlighted passages should get extra weight in searches. You
should be able to search the text of annotations, too.
• This agent could become a built-in function of Google search
or its future counterparts. While Google "remembers" that newspaper
article you read last October, and (via Google Books) everything in
many books, the profusion of hits in a given search can be
overwhelming. If Google (via this agent) kept track of what you
read, on any and all devices, you could filter searches by "stuff
• You can search for something you remember you've forgotten,
but not for something you've completely forgotten or aren't
thinking about. Maybe you read the complete short stories of
Nikolay Gogol at school and loved them but hardly remember a
character, plot, or phrase now. The agent might address that by
periodically reminding you of highlighted passages, those you've
identified as worth the attention of your future self. Perhaps the
agent would have a Twitter account and tweet random snippets of
material you want to remember but don't otherwise have time to go
• The agent would also "remember" podcasts, movies, and TV shows
-- provided transcripts or subtitles exist or could be
16. You're in a car with a
helium balloon tied to the floor. The windows are closed. When you
step on the gas pedal, what happens to the balloon? Does it move
forward, backwards, or stay put? (generic the company question,
The near-universal intuition is that the balloon leans backward
as you accelerate. Well, the intuition is wrong. Your job is to
deduce how the balloon does move and to explain it to the
One good response is to draw an analogy to a spirit level. For
the not so handy, a spirit level is the little gizmo carpenters use
to make sure a surface is horizontal. It contains a narrow glass
tube of colored liquid with a bubble in it. Whenever the spirit
level rests on a perfectly horizontal surface, the bubble hovers in
the middle of the tube. When the surface isn't so level, the bubble
migrates to the higher end of the tube. The takeaway here is that
the bubble is simply a "hole" in the liquid. When the surface isn't
level, gravity pulls the liquid toward the lower end. This pushes
the bubble wherever the liquid isn't -- toward the opposite
Untie the helium balloon and let it hit the sunroof. It becomes
a spirit level. The balloon is a "bubble" of lower-density helium
in higher-density air, all sealed in a container (the car). Gravity
pulls the heavy air downward, forcing the light balloon against the
When the car accelerates, the air is pushed backward, just as
your body is. This sends a lighter-than-air balloon forward. When
the car brakes suddenly, the air piles up in front of the
windshield. This sends the balloon backward. Centrifugal force
pushes the air away from the turn and sends the balloon toward the
center of the turn. Of course, the same applies when the balloon is
tied to something; it's just less free to move. The short answer to
this question is that the balloon nods in the direction of any
Don't believe it? Put the book down right now. Go to the
supermarket, buy a helium balloon, and tie the string to the gear
stick or hand brake. Drive back home (no lead-footing necessary).
You'll be astonished. The balloon does exactly the opposite of what
you'd expect. When you step on the accelerator, it bobs forward,
like it's trying to race the car to the next light. Brake hard
enough to throw the kids' toys out of the backseat, and the balloon
pulls backward. In a high-speed turn, as your body leans outward,
the crazy balloon veers inward. It's so freaky that there are
videos of this on YouTube.
Why are our intuitions right about spirit levels and wrong about
helium balloons? In a spirit level, the heavy liquid is dyed a
fluorescent sports-drink hue, while the bubble is a ghostly void.
We associate color with density, and transparency with nothingness.
That instinct is completely wrong with balloons. Air is invisible,
and we ignore it 99+ per cent of the time. The balloon, on the
other hand, is dressed up in pretty colors or Mylar and screams,
"Look at me!" We forget that, masswise, it's a partial vacuum
within the surrounding air. A helium balloon does the opposite of
what a mass does because it's a deficit of mass. The real mass --
the air -- is invisible.
Interviewers who ask this question don't expect you to know much
physics. But there is an alternate response that makes use of the
theory of relativity. Seriously.
It relates to Albert Einstein's famous thought experiment about
the lift. Imagine you're in a lift going to your tax accountant's
office, and a mischievous extraterrestrial decides it would be fun
to teleport you and the lift into intergalactic space. The lift is
sealed, so there's enough air inside to keep you alive long enough
to amuse the alien for a few minutes. There are no windows, so you
can't look out and see where you are. The alien puts the lift in a
tractor beam and tows it at a constant acceleration exactly
matching that of Earth's gravity. Is there anything you could do in
the sealed lift to determine whether you're experiencing real Earth
gravity or "fake" gravity, mimicked by acceleration?
Einstein said no. Should you take your keys out of your pocket
and drop them, they would accelerate toward the lift floor exactly
as they would on Earth. Let go of a helium balloon's string, and it
would float upward, just as on Earth. Things would appear perfectly
normal. The Einstein equivalence principle says that there is no
(simple) physics experiment that can distinguish between gravity
and acceleration. This assumption is the foundation of Einstein's
theory of gravity, known as general relativity. Physicists have
been trying to punch holes in the equivalence principle for nearly
a century now. They haven't been able to. It's safe to assume that
Einstein's premise is right, at least for any experiments you can
do in a car with a fifty-pee balloon.
All right, here's a physics experiment. Tie the string of a
plumb bob (carpenter's weight) to your right index finger. Tie a
helium balloon to the same finger. Note the angle between the two
In a lift, a parked car, or a cruising jetliner, the outcome
will be the same. The plumb bob points straight down. The balloon
points straight up. The two strings, joined at your finger, form a
straight line. This is the outcome whenever you are subjected to
gravity. Now picture what happens when you start driving. As you
accelerate, your body sinks back in the seat. Fallible intuition
may tell you that the plumb bob and the balloon will each lean
backward a bit from your finger. During acceleration, there will be
an angle between the two strings (if this intuition is right). This
would provide a way of distinguishing between gravity and
acceleration. When the car is subject to gravity alone, the two
strings form a straight line. But when it's subject to centrifugal
force or other forms of acceleration, the strings form an angle
with your finger as the vertex. That's all you need to prove that
general relativity is wrong. Forget about getting a job at Google
-- this would be worthy of a Nobel Prize.
But since the equivalence principle has been rigorously tested
and shown to be true, this doesn't happen, and you can use it to
answer this question. Physics must be the same in an accelerating
car as in a car subject to gravity alone. In both cases, the
balloon, your finger, and the plumb bob form a straight line. In
answer to the question, then, the helium balloon does the exact
opposite of what you'd expect of an object with mass. It goes
forward rather than backward… left rather than right… and, of
course, up rather than down.
17. You have a choice of two
wagers: One, you're given a basketball and have one chance to sink
it for £1,000. Two, you have to make two out of three shots, for
the same £1,000. Which do you prefer?
Call the probability of making a basket p. With the first bet,
you have a p chance of winning £1,000. Otherwise, you get nothing.
On the average, you can expect to win £1,000 X p.
With the second wager, you shoot three times and have to make
the basket twice to be in the money. The chance of making the
basket on any given attempt is still p. Your chance of missing on
any attempt is 1 - p.
There are 23, or 8, scenarios for the second wager. Let's list
them. A check mark means you make the shot; a blank means you
The first scenario is the one where you're really off your game.
You miss all three shots. The chance of that is 1 - p, multiplied
by itself three times. You don't get the money.
In four of the eight scenarios, you win the money. In three of
them you miss once. These scenarios have the probability of p2(1 -
p). In the case where you make all three shots, the probability is
p3. Add all of them up. Three times p2(1 - p) comes to 3p2 - 3p3.
Add p3 to that, to get 3p2 - 2p3. The expectation is £1,00 x (3p2 -
So which wager is best?
First wager's expectation: £1,000 × p
Second wager's expectation: £1,000x (3p2 - 2p3)
You may be a complete klutz (p is roughly 0) or an NBA baller (p
approaches 1). For reference, I've done what you can't do in the
interview: plugged the formulas into a worksheet and made a chart.
The chart shows how expected winnings vary with p.
The straight diagonal line represents the first bet, and the
more S-shaped curve is the second. The first bet is better if your
chance of making the shot is less than 50 percent. Otherwise,
you're better off picking the second wager.
This makes sense. A poor player cannot expect to win either
wager. He must pin his hopes on a freak lucky shot, which is
obviously more likely to happen once than twice ("lightning never
strikes twice"). The bad player is better off with wager 1.
The very good player ought to win either wager, though there is a
small chance he'll miss the money shot. Two out of three is a
better gauge of his talents, and that's what he wants. It's like
the legal maxim: if you're guilty, you want a jury trial (because
anything can happen); if you're innocent, you want a judge.
Assuming you get this far, the interviewer's follow-up question
is, "What value of p makes you switch bets?" To answer that, set
the probability of winning the two bets equal. This represents the
skill level where it's a toss-up which you pick.
p = 3p2 - 2p3
Divide by p:
1 = 3p - 2p2
and then get
2p2 - 3p + 1 = 0
From there you can use the quadratic formula, warming the heart
of your old algebra teacher. The interviewer will be looking for
brio as much as book learning. You know p, a probability, has to be
between 0 and 1. It's better style to experimentally try a
rea-sonable value. "Okay, I need a number between 0 and 1. Let's
try 0.5." Works like a charm.
18. You have N companies and
want to merge them into one big company. How many different ways
are there to do it?
In the proper sense of "merger," two companies surrender their
identities and fuse into a brand-new entity. The pharmaceutical
giants Glaxo Wellcome and SmithKline Beecham merged in 2000 to form
the pharma colossus GlaxoSmithKline. (You guessed it -- both parent
companies were themselves merger spawn.)
CEO egos being what they are, true mergers are fairly uncommon.
Mergers require a near-exact match of bargaining power. More
typically, one company's management has the stronger hand, and it's
not about to let the weaker company's leaders forget it. The deal
is likely to be an acquisition, in which company A gulps up company
B, and B ceases to exist as a separate entity (though it often
survives as a brand). An example is Google's 2006 acquisition of
Mergers are symmetrical. There is only one way for two companies
to merge as equals. Acquisitions are asymmetrical. There are two
ways for two companies to acquire or be acquired -- Google buying
YouTube is not the same as YouTube buying Google. Most people
outside investment banking gloss over the distinction between
mergers and acquisitions. Any melding of corporations is loosely
called a "merger." The point is, you need to ask the interviewer
what is meant by "merge." Fortunately, most of the reasoning
applies whatever the interviewer's answer.
Start with acquisitions because they're more common (and a
little easier to work with). You can visualize the companies as
draughts, and the acquisitions as the moves in the game. Start with
N pieces. A move consists of putting one piece on top of another to
signify that the top piece is "acquiring" the bottom piece. After
an acquisition, you manipulate the pieces involved as if they were
glued together (like a "kinged" piece in the regular game).
Every move diminishes the number of pieces (or stacks) by one.
Eventually, you will be placing stacks of pieces on top of other
stacks to create yet- taller stacks. It will take exactly N - 1
moves to achieve the game's goal, a single tall stack consisting of
all N pieces combined into one. How many different scenarios can
lead to that outcome?
The simplest case involves two companies. Company A can gulp up
B, or B can gulp up A. That's two possible scenarios. With three
companies, you have to decide which company first acquires what
other company. There are six possibilities for that first
acquisition, corresponding to the six possible ordered pairs of
three items (AB, AC, BA, BC, CA, and CB). After the initial
acquisition, you're left with two companies. The situation is then
exactly as in the paragraph above. The number of possible
acquisition histories for three companies is therefore 6 x 2 =
With four companies, there are twelve possibilities for the
first acquisition: AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, and
DC. That decided, you have three companies and, as we already know,
twelve histories. There must be 12 x 6 x 2, or 144, acquisition
histories for four companies. Let's generalize. With N companies,
the number of possible initial acquisitions is
N(N - 1) This just means that any of the N companies can be the
first acquirer, and any of the remaining N - 1 companies can be the
first acquiree. After the first acquisition, there will remain N -
1 distinct companies, and there will be (N - 1)(N - 2)
possibilities for the second acquisition. Then there will be (N -
2) companies and (N - 2)(N - 3) possible acquisitions. We're going
to be multiplying the ever- decreasing numbers of possible
acquisitions until we're left with 2 x 1 possibilities for the
It's easy to see that, using factorial notation, the product
will come to N! x (N - 1)! acquisition histories. What if you want
true mergers instead of acquisitions? The above analysis overcounts
the possibilities by a factor of two -- for each of the N - 1
mergers. That means the number of proper merger histories is N! x
(N - 1)! divided by 2N - 1.Finally, if "merger" can mean merger or
acquisition, you simply add the two answers.
19. You've got an analogue
watch with a second hand. How many times a day do all three of the
watch's hands overlap?
This is an update to a classic Microsoft interview question that
asks how many times a day a clock's hour and minute hands overlap.
Because that one's become pretty well known, interviewers have
started using this variant.
The Microsoft answer: First, figure when the hour and minute
hands overlap. Everyone knows the minute and hour hands overlap at
12:00 midnight and at approximately 1:05, 2:10, 3:15, and so forth.
There's an overlap in every hour except 11:00 to 12:00. At 11:00,
the faster minute hand is at 12 and the slower hour hand is on 11.
They won't meet until 12:00 noon -- ergo, there is no overlap in
the 11:00 hour.
There are thus eleven overlaps in each 12-hour period. They are
evenly spaced in time (since both hands travel at constant speeds).
That means that the interval between overlaps of hour and minute
hands is 12/11 of an hour. This comes to 1 hour, 5 minutes, and 27
3/11 seconds. The eleven alignments of minute and hour hands in
each 12-hour cycle take place at:
3 :16:21 9/11
7: 38:10 10/11
How can we determine if any of these times is a three-way
overlap? Though the question is about an analog clock, think of a
digital clock that gives time in hours, minutes, and seconds:
There is an overlap between minute and second hands only when
the minutes figure (00 here) equals the seconds figure (00). There
is a precise three-way overlap at 12:00:00. In general, the minute-
and second-hand overlap will occur at a fractional second. For
the second hand would be at 37 past the minute, while the minute
hand would be between 37 and 38 past the hour. The instant of
overlap would come a split- second later. But the hour hand
wouldn't be near the others, so this isn't a three-way overlap.
None of the hour- and minute-hand overlaps in the list above
passes this test except for 12:00:00. That means all three hands
align just twice every day, at midnight and noon.
The Google answer: The second hand is intended for timing short
intervals, not for telling time with split-second accuracy. It's
normally not in sync with the other two hands. "In sync" would mean
that all three hands point to 12 at the stroke of midnight and
noon. Most analog watches and clocks do not let you set the second
hand from the stem. (I've never seen one that does.) A workaround
would be to take the battery out (or let a windup watch run down),
set the minute and hour hands in sync with where the second hand
stopped, and wait until it becomes the time shown to replace the
battery or wind up the watch. It would take a maniacal analogue
watch fetishist to do that. But unless you do this, the second hand
will not show the "real" time. It will be offset from the accurate
seconds by a random interval of up to 60 seconds. Given a random
offset, the odds are overwhelming that the three hands would never
20. You work in a 100-storey
building and are given two identical eggs. You have to determine
the highest floor from which an egg can be dropped without
breaking. You are allowed to break both eggs in the process. How
many drops would it take you to do it?
Lest there be any confusion, the building and eggs are strictly
imaginary. This is an algorithm question. It's a test of your
ability to craft a smart, practical way of doing something. That's
important in engineering, in management, and in everything else.
Every cook knows that a raw egg dropped from counter height onto
tile is history. But if Google's 100-story building is surrounded
with something softer than concrete and harder than grass, the
answer is not obvious.
To answer in the spirit intended, you have to assume that it is
possible that the maximum egg-safe floor could be any floor at all,
from 1 to 100. In fact, you should allow for the possibility that
no floor is egg-safe (seconding the wisdom of cooks). You are
permitted to ignore the strong element of chance in egg
defenestration (demonstrated in the 1970 experiments). Pretend that
the outcome of dropping an egg from a given floor will always be
the same. Either it breaks or it doesn't. The interviewer is not
expecting you to name the egg-safe floor. There are no eggs and
there is no 100-story building: it's all a fictional situation,
okay? You are asked only to devise an efficient method for
determining the floor, while explaining your thought process.
The one question you are expected to answer with an actual
number is, how many drops would you need? Scoring is like golf: the
fewer, the better.
Bits and Eggs Dropping an egg is a simple experiment that yields
one bit of information. To get the most bang for the bit, you'd
start in the middle of the building. That would be floor 50 or 51,
as there's no "middle" floor in a building with an even number of
Try dropping an egg from the 50th floor. Let's say it breaks.
This would mean that the desired egg-safe floor must be below the
50th floor. Split the difference again by dropping the next egg
from the 25th floor. Oops! It broke again. Now you're out of eggs.
You can now conclude that the highest egg-safe floor is below the
25th. You don't know which floor, and that means that the method
has failed. It's possible to keep reusing an egg so long as it
Start on the bottom floor and drop the first egg. If it
survives, go to the 2nd floor and try that. Then the 3rd, the 4th,
the 5th, and so on until the egg breaks. That will tell the highest
floor the egg can be dropped from without breaking. You will have
determined it with just one egg. Call this the "slow algorithm."
It's a miser of eggs and a spendthrift of egg drops. Every single
floor might have to be tested, but it gets the job done.
The challenge is to create a solution that makes good use of
both eggs. Suppose that Google's optimal algorithm for the egg-drop
experiment was written in a book somewhere. You don't even have to
suppose -- it is written in a book, namely this one. The algorithm
reads something like this:
1. Go to floor N and drop the first egg.
How do I know the algorithm begins this way? Well, I'm not going
out on much of a limb. An algorithm is a list of idiotproof
instructions, starting with instruction 1. It tells you to drop an
egg, naturally, because that's the modus operandi here. There's
nothing else to do but drop eggs. The only interesting part (floor
N) is currently concealed under an algebraic veil. The real
algorithm gives a specific floor, like 43, in place of the N.
Further deduction: because the experiment in instruction 1 has
two outcomes, it has to have follow-up instructions for both
eventualities. Call them 2a (what to do if the egg breaks) and 2b
(what to do if it survives). Once you break the first egg, you will
have to play it safe with the second. You can't take the risk of
skipping any floor, lest you break the second egg and not be able
to deduce the correct floor.
Instruction 2a of Google's algorithm has to say this, in so many
2a. (To be used if the egg breaks in 1.) Go down to floor 1.
Adopt the "slow algorithm" with the remaining egg. Test it from
every floor, working your way up the building until the egg breaks.
The maximum egg-safe floor is the one below that. For instance,
imagine the first drop is from the 50th floor, and the egg breaks.
You can't risk trying the second egg from floor 25 because it might
break, too. Instead, you have to try floors 1, 2, 3 . . .
potentially all the way up to 49. And since we started with the
50th, that could mean making fifty drops in all. It doesn't take
much coder's intuition to see that a search needing fifty tests to
find one thing out of a hundred is not optimal. It's lousy. It's
better to count on making the first drop from a lower floor. If we
start from floor 10, and the egg breaks, we might need as many as
ten drops. This is the key aha! moment of the puzzle. In general,
when the egg breaks on a first drop from floor N, it will take as
many as N drops total to identify the right floor. This strongly
suggests that the first drop should be from a floor much lower than
50. This choice has the appealing feature that we use the first egg
to deduce the tens digit of the egg-safe floor, and the second egg
to find the ones digit. For example, test the egg from floors 10,
20, 30, 40, and 50. Say it breaks when dropped from floor 60. This
tells us the maximum egg-safe floor is 50-something. Move down to
floor 51 and work upward floor-by-floor with the other egg. If the
second egg breaks at floor 58, that means the egg-safe floor is
57.How efficient is this procedure? The worst-case scenario would
be to try 10, 20, 30, all the way up to 100, where the egg finally
breaks. Then you'd backtrack to 91 and work up. You could end up
needing nineteen drops in all to determine that 99 is the correct
floor. This isn't a bad approach. But it's not the best.
Crash Test Remember, the question asks, "How many drops would it
take you to do it?" That's a strong hint that you're being graded
on how few drops you need. (More exactly, you're to minimize the
number of drops required in a worst- case scenario. Sometimes
you'll get lucky and arrive at the answer in just a few drops.)
Because the first egg's role is as crash-test dummy, you want to
put it in high-risk situations; that's how you learn as much as
possible as quickly as possible. The second egg is a backup. Once
it's the sole remaining egg, you have to play safe with it. It's
the crash-test-dummy egg that's crucial to achieving a good
solution. It's the egg that can eliminate many floors in a single
drop. The question is, how many? A bit of mental gymnastics is
required to answer that. It throws many smart people.
I'll begin with an analogy. You're a professional golfer on the
eighteenth hole, vying for a big prize. To win, you've got to make
the hole within three strokes. That necessity dictates which clubs
you choose and whether you risk a bunker rather than playing it
safe. It will require you to aim for the hole on the third stroke
(rather than being satisfied with making the green). The
three-stroke limit constrains your strategy throughout. Google's
perfect algorithm also has a limit: a maximum number of drops
needed to determine the correct floor. Call this number D. The
D-drop limit constrains your strategy. For the sake of
concreteness, imagine the limit is ten drops. Then you might as
well drop the first egg from the 10th floor. See why? You want to
choose a floor as high as possible, to rule out as many floors as
possible. The 10th floor is the highest option, for this reason:
should the first egg break, you could end up needing all ten
permitted drops to determine the correct floor. (The above
paragraph is the hardest thing to understand, I promise.)
Everything else follows from this insight. After the initial
drop, you've got nine drops left. Assuming the egg survives, you
will again want to move up as many floors as possible for the
second drop. You might think you'd move up another 10 floors. Not
quite. Since you've only got nine drops left, you can move up 9
floors at most. That's because the egg could break on the second
drop, forc-ing you to use a floor-by-floor search thereafter. You
might have to test every floor between 10 and the one you just
tried, 19, using up all your allotted drops. Had you gone up even a
floor higher, you could get caught short and not be able to single
out the correct floor.Or say the egg survives the first two drops.
That leaves eight drops. You would go up 8 floors for the next
drop.The floors you test, assuming a series of unbroken eggs, form
a simple series.
10 + 9 =19
10 + 9 + 8 = 27
10+ 9 +8 +7 = 34
Wait a minute. The highest floor you can possibly reach is 10 +
9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1. That comes to 55. This scheme
would work perfectly for a 55-story building. But the question says
it's a 100- story building.
That's easily fixed. Remember, I just picked 10 out of the air.
Replace 10 with D, the required number of drops in the best
algorithm. The highest floor an optimal method can reach is
D + (D - 1) + (D - 2) + (D - 3)+ . . . + 3 + 2 + 1
This must equal or exceed 100.
From here on it's just algebra. The sum above is D plus every
whole number smaller than it. This is a triangular number. Picture
a rack of billiard balls. It's 5 + 4 + 3 + 2 + 1 balls. You may
recall from school that the total can be computed by multiplying 5
by 5 + 1 and dividing by 2. So you've got 5 x 6/2 = 15, and that's
the number of balls in a rack.
In this case, the sum of D and every smaller whole number is equal
to D times (D + 1) divided by 2. So:
D x (D + 1)/2 ≥ 100
Multiply both sides by 2, and you get
D2 + D ≥ 200
Focus on D2 and ignore the much smaller D. This equation says
that D2 is at least as big as 200 or so. The square root of 200 is
just over 14. Try that for D.
142 + 14 = 196 + 14 = 210 ≥ 200
Bingo. It fits. Just to be sure, try 13.
132 + 13 = 169 +13 =182
Nope, that's not greater than or equal to 200. Fourteen it is.
You drop the first egg from floor 14, and you're guaranteed to find
the answer in fourteen drops or less. The recap: First, drop the
egg from floor 14. If it breaks, go down to floor 1 and work your
way upward floor-by-floor. This will get the answer in no more than
fourteen drops total.
Should the first drop not break the egg, go up to floor 27 (14 -
1 floors above floor 14) and try again. Should it break this time,
you'll have to go down to 15 and work up. This will also yield the
answer in fourteen drops total or less.
Given a string of unbroken eggs, you'd test floors 39, 50, 60,
69, 77, 84, 90, 95, 99, and then 100 (actually, were the building
higher, the next floor would be 102). This means it would take
twelve drops, and no broken eggs, to deduce that the egg can
survive every floor of the building. Should the egg break at any
point in the process, you'd be shunted into the slow algorithm and
might need all fourteen permitted drops.
21. Add any standard
arithmetic signs to this equation to make it true: 3 1 3 6 =
Starting from the left, you see 3 and 1. The first maths sign
you learned was probably a plus sign. 3 = 1 gives 4. Conveniently,
4 is half of 8, the number that's the goal. Moving righr, there's a
3 and a 6. Well, 3 is half of 6. Put a division sign between them
and you've got 3/6 or 1 / 2. Dividing by 1/2 is the same as
multiplying by 2. This gives the answer: (3 + 1) / (3 / 6) = 8.
That wasn't so hard, was it?