Google - Microsoft - amzon, yahoo interview puzzles

1.
Title: Blind Man and Cards

ID: blind
Puzzle:
A blind man was handed a deck of 52 cards with exactly 10
cards facing up. How could he divide it into two piles, each
of which having the same number of cards facing up?
Hint:
Yet to write.
Solution:
He divides the cards into two piles with 10 and 42 cards each. He
then flips all cards in the smaller pile.

2.
Title: Rope
ID: rope
Puzzle:
Rajeev is trapped atop a building 200m high. He has with him
a rope 150m long. There is a hook at the top where he
stands. Looking down, he notices that midway between him and
the ground, at a height of 100m, there is a ledge with
another hook. In his pocket lies a Swiss knife. Hmm... how
might he be able to come down using the rope, the two hooks
and the Swiss knife?
Hint:
Yet to write.
Solution:
Cut rope into 50m and 100m pieces. Tie one end of the 50m piece to
the top hook and make a noose at the other end. Pass the 100m piece
through the noose and tie its two ends.

3.
Title: Three boxes and a Ruby
ID: ruby
Puzzle:
Alice places three identical boxes on a table. She has
concealed a precious ruby in one of them. The other two
boxes are empty. Bob is allowed to pick one of the boxes.
Among the two boxes remaining on the table, at least one is
empty. Alice then removes one empty box from the table. Bob
is now allowed to open either the box he picked, or the box
lying on the table. If he opens the box with the ruby, he
gets a kiss from Alice (which he values more than the ruby,
of course). What should Bob do?
Hint:
Yet to write.
Solution:
If Bob switches his choice, he wins with probability 2/3.

Title: Choice of Three
ID: three
Puzzle:
In the previous problem, Bob had to pick one of the three
boxes lying on the table. If he wished to select them with
equal probability, how could he do it by using a penny in
his pocket? What if the penny was biased?
Hint:
Yet to write.
Solution:
Toss the coin twice. Let TH, HT and TT correspond to the three
boxes. If HH, repeat.

Title: Treasure Island
ID: island
Puzzle:
An old parchment contains directions to a treasure chest
buried in an island:

"There is an old unmarked grave
and two tall oak trees. Walk from the grave to the left tree,
counting the number of steps. Upon reaching the left tree, turn
left and walk the same number of steps. Mark the point with a
flag. Return to the grave. Now, walk towards the right tree,
counting the number of steps. Upon reaching the right tree, turn
right and walk the same number of steps. Mark this point with
another flag. The treasure lies at the midpoint of the two
flags"

A party of sailors reached the island. They find a pair of
tall oak trees merrily swaying in the wind. However, the
unmarked grave is nowhere to be found. They are planning to
dig up the entire island. It'll take a month. Can they do any
better?
Hint:
Yet to write.
Solution:
Yet to write.

Title: 30 Coins
ID: coins
Puzzle:
30 coins of arbitrary denominations are laid out in a row.
Ram and Maya alternately pick one of the two coins at the
ends of the row. Could Maya ever collect more money than Ram?
Hint:
Yet to write.
Solution:
The first player could pick all coins in odd-numbered positions or
all coins in even-numbered positions, whichever set is larger in
value.

Title: Cake Cutting
ID: cake
Puzzle:
Mary baked a rectangular cake. Merlin secretly carved out a
small rectangular piece, ate it and vanished! The remaining
cake has to be split evenly between Mary's two kids. How could
this be done with only one cut through the cake?
Hint:
Yet to write.
Solution:
Cut along the line joining the centers of the two rectangles.

Title: Cube Problems
ID: cube
Puzzle:
Imagine a cube on a flat table, tantalizingly balanced on one of
its vertices such that the vertex most distant from it is
vertically above it. (a) What is the length of the shortest path an
ant could take to go from the topmost vertex to the bottommost
vertex? (b) What will be the projection on the table
if there is a light source right above the cube? (c) What would be
the cross-section obtained if we slice the cube along a plane
parallel to the table, passing through the midpoint of the
topmost and the bottommost points of the cube?
Hint:
Yet to write.
Solution:
(a) Square-root of five times the side of the cube, (b) Regular
hexagon, (c) Regular hexagon.

Title: Tiling a Chessboard
ID: chessboard
Puzzle:
An 8x8 chessboard has had two of its diagonally opposite squares
removed, leaving it with sixty-two squares. Is it possible to
tile it with non-overlapping 2x1 rectangles such that all
squares are covered?
Hint:
Yet to write.
Solution:
Both squares have the same color.

Title: Cubes in Cube
ID: cubeslice
Puzzle:
Imagine a 3x3x3 solid cube. How many cuts do we need to break it
into twenty-seven 1x1x1 cubes? How about an n x n x n cube? What
if we are not allowed to stack pieces and cut them together?


Is there a way to repeatedly hop from a small cube to an
adjacent small cube (sharing a surface) within the large 3x3x3
cube such that there is a closed path covering all small cubes,
without ever passing through a small cube twice?
Hint:
Yet to write.
Solution:

The central 1x1x1 cube in a 3x3x3 cube has six faces, no two of
which can be revealed in a single cut. For the general a x b x c
cuboid, we need f(a) + f(b) + f(c) cuts, where f(y) = ⌈ log y
/ log 2 ⌉. This can be proved by induction. Note that at any point,
the "largest" cuboid requires the most steps; others can be sliced
in parallel with this cuboid. When the "largest" cuboid has
dimensions a x b x c, there are exactly 3 choices: to slice along
one of the three sides. For a lying in the range (2^i, 2^(i+1)], any
cut that results in the new "largest cuboid" being z x b x c, where
z lies in the range (2^(i-1), 2^i], is optimal. This is because f(z)
for all these z's is identical. For example, for 10 x 34 x 98
cuboid, any of the following could be the maximal cuboid for the
remaining steps:




5 x 34 x 100

6 x 34 x 100

7 x 34 x 100

8 x 34 x 100


10 x 17 x 100

10 x 18 x 100

10 x 19 x 100

... and so on till

10 x 32 x 100

10 x 34 x 49

10 x 34 x 50

10 x 34 x 51

10 x 34 x 52

.. and so on till

10 x 34 x 64.




If a slice can pass through exactly one existing cuboid, then the
number of slices is n3 - 1 because a slice increases the
total number of cuboids by exactly 1.

Title: Forty-five Minutes
ID: fortyfive
Puzzle:
How do we measure forty-five minutes using two identical
wires, each of which takes an hour to burn. We have
matchsticks with us. And yeah, the wires burn non-uniformly.
Hint:
Yet to write.
Solution:
Light three out of four ends. When two ends meet, light the fourth.


Section: Easy


Title: Bigger or Smaller
ID: biggersmaller
Puzzle:

Alice writes two distinct real numbers between 0 and 1 on
two chits of paper. Bob selects one of the chits randomly to
inspect it. He then has to declare whether the number he
sees is the bigger or smaller of the two. Is there any way
he can expect to be correct more than half the times Alice
plays this game with him?

Hint:
Yet to write.
Solution:
Let the number revealed to Bob be x. Then Bob should say "bigger"
with probability x, "smaller" otherwise.

Title: Thousand Jars
ID: thousandjars
Puzzle:
Imagine an array of one thousand jars, labeled one thru
thousand. Jars can be colored red or black. Initially, all jars
are red. The color of a jar changes on successive days as
follows: On the i-th day, jars whose labels are divisible
exactly by i, switch their color. How many jars are red at
the end of the thousandth day?
Hint:
Yet to write.
Solution:
A number has an odd number of divisors iff it is square.

Title: Working Computer
ID: workingcomputer
Puzzle:
A room has n computers, less than half of which are
damaged. It is possible to query a computer about the status of
any computer. A damaged computer could give wrong answers. The
goal is to discover an undamaged computer in as few queries as
possible.
Hint:
Yet to write.
Solution:
(a) Pick a computer at random. Ask other computer whether it is
damaged or not.

(b) Yet to write a second solution.

Title: Average Salary
ID: averagesalary
Puzzle:
Four honest and hard-working computer engineers are sipping
coffee at Starbucks. They wish to compute their average
salary. However, nobody is willing to reveal an iota of
information about his/her own salary to anybody else. How do
they do it?
Hint:
Yet to write.
Solution:
The first engineer picks a random k-digit integer for some large k,
adds his salary to it and writes the sum on a chit. The chit is
passed around. When it returns to the first engineer, he subtracts
the k-digit integer.

Title: Number Guessing Game I
ID: numberguessingi
Puzzle:
Shankar chooses a number between 1 and 1000. Geeta has to guess the
chosen number as quickly as possible. Shankar will let Geeta know
whether her guess is smaller than, larger than or equal to the
number. (a) What should Geeta's strategy be? (B) In a modified
version of the game, Geeta loses if her guess is "larger than the
number" two or more times. (c) What if Shankar is allowed to choose
an arbitrarily large number?
Hint:
Yet to write.
Solution:
(a) Binary search. (b) and (c) Guess 1, 4, 9, 16, 25, and so on, to
discover k such that Shankar's number lies between k2 and
(k+1)2. Then guess k+1, k+2, k+3 and so on. On the
whole, this requires O(√n) steps.

Title: Number Guessing Game II
ID: numberguessingii
Puzzle:
Shankar chooses a number uniformly at random between 1 and
1000. Geeta has to guess the chosen number as quickly as
possible. Shankar will let Geeta know whether her guess is smaller
than, larger than or equal to the number. If Geeta's guess is larger
than the number, Shankar replaces the number with another number
chosen uniformly at random [1, 1000]. (a) What should Geeta's strategy
be? (b) In a modified version of the game, Shankar gets to choose a
number arbitrarily / adversarially. (c) And finally, what if Shankar
just says "equal to" or "not equal to" when Geeta guesses (the rest
of the setup remains the same)?
Hint:
Yet to write.
Solution:
(a) Repeatedly guess g = n - n/k until Shankar says "greater
than". Then guess g+1, g+2, g+3 and so on. The expected number of
steps is ≈ k + n/2k, which is minimized for k ≈
√(n/2). (b) and (c) Yet to write.

Title: Four Ships
ID: fourships
Puzzle:
Four ships are sailing on a 2D planet. Each ships traverses
a straight line at constant speed. Their journeys started at
some time in the distant past. Sometimes, a pair of ships
collides. A ship continues its journey even after a collision.
However, it is strong enough only to survive two collisions; it
dies when it collides a third time. The situation is grim.
Five of six possible collisions have already taken place and two
ships are out of commission. What fate awaits the remaining two?
Hint:
Yet to write.
Solution:
Let z-axis denote time. Then the four trajectories are straight
lines. Three of the lines are known to be coplanar. The fourth line
intersects two of these three. Still, the sixth collision may or may
not happen!

Title: f(f(x))
ID: ffx
Puzzle:
Is it possible to write a function int f(int x) in
C that satisfies f(f(x)) == -x? Without globals and static
variables? Is it possible to construct a function f mapping
rationals to rationals such that f(f(x)) = 1/x?
Hint:
Yet to write.
Solution:
Function f can be defined iff we can divide non-zero integers into
quadruples of the form (a, b, -a, -b). This is because f(0) must be
0. For any other integer "a", let f(a) = b. Then f(b) = -a, f(-a) =
-b and f(-b) = a. Now, C integers are either 32-bit or 64-bit. So
it is impossible to create such quadruples because the number of
positive and the number of negative integers are not the same!

Title: Measuring Weights
ID: measuringweights
Puzzle:
(a) Customers at a grocer's shop always want an integral
number pounds of wheat, between 1 pound and 40 pounds. The
grocer prefers to measure wheat in
exactly one weighing with a beam balance. What is the least
number of weights he
needs? (b) Customers come to a pawn shop with antiques. An
antique always weighs an integral number of pounds,
somewhere between 1 pound and 80 pounds. The owner of the
pawn shop is free to do as many weighings as necessary to
ascertain the unknown integral weight by using a beam
balance. What is the least number of weights he needs?
Hint:
Yet to write.
Solution:
(a) Four weights: 1, 3, 9 and 27. (b) Four weights: 2, 6, 18 and 54.

Title: Counting with a Magical Bird
ID: magicalbird
Puzzle:

An evil goblin assembles 100 gnomes together. He tells them
that they will be locked up into individual cells. Each
cell will have a window and a large supply of
grains. Thereafter, a magical bird will hop from window to
window, ad infinitum. Initially, the bird is white in
color, and it will switch its color from white to black and
vice versa if a grain is fed to it. The bird will be fair
in the sense that it will visit every cell infinitely often.
As soon as some gnome is sure that the bird has visited
every cell, he should say "abracadabra" aloud. If the bird
has indeed visited every cell, all gnomes will be
released. Otherwise, all of them will be killed. The gnomes
have ten minutes to arrive at a strategy. How can they save
themselves?

Hint:
Yet to write.
Solution:
Yet to write.

Title: Troll n Gnomes
ID: trollgnomes
Puzzle:
An evil troll once captured a bunch of gnomes and told them,

"Tomorrow, I will make you stand
in a file, ordered by height such that the tallest gnome can
see everybody in front of him. I will place either a white
cap or a black cap on each head. Then, starting from the
tallest, each gnome has to declare aloud what he thinks the
color of his own cap is. In the end, those who were correct
will be spared; others will be eaten, silently."

The gnomes set thinking and came up with a strategy. How many
of them survived? What if hats come in 10 different colors?
Hint:
Yet to write.
Solution:
The tallest gnome should declare the "parity". For example, he could
say "white" iff the number of white caps he sees is odd.


Section: Moderate


Title: Red-black Squares
ID: redblacksquares
Puzzle:
Given k arbitrary points in a grid of size m by n, is it
always possible to color them either red or black such that
each row and each column is balanced? A row or column is
said to be balanced if the difference in the number of red
and black points in it is at most one.
Hint:
Yet to write.
Solution:
Thanks to Iman
Hajirasouliha
for this elegant solution!
Model the grid with a bipartite graph G[X, Y], a vertex in
part X for each row and a vertex in part Y for each
column. Add edges between xi and yj
iff there is a point in the corresponding place. If G has a
cycle (it must be an even cycle), we color the edges
alternatively and remove those edges, continuing this
procedure we can assume that G is a tree. When G is a tree,
we can solve the problem by induction on the number of edges
as follows: remove e a leaf edge, color the remaining edges
balanced, now look at the parent of that leaf and choose the
right color for e to maintain the induction hypothesis.

Title: Four Cards
ID: fourcards
Puzzle:

Four cards are placed on a square table, one card at each
corner. A blind gnome and an evil goblin take turns to play
the following game. The blind gnome gets to choose a subset
of the four cards and flip them simultaneously. If all four
cards are face up, he wins the game. Otherwise, the evil
goblin get to rotate the table by an amount of his choice.
Show that for any initial configuration of cards chosen by
the evil goblin, the blind gnome can win the game in a
finite number of steps with a deterministic
strategy.

Hint:
Solution: Yet to write.

Title: And-Or Gates
ID: andorgates
Puzzle:
Alice and Bob were working in the hardware design lab one
morning giving final touches to their 4-bit microprocessor,
when suddenly they discovered that three of their NOT gates
were malfunctioning! They opened the inventory cupboard and
received another shock: only two NOT gates were available.



"Look. All we have is hundreds of AND
and OR gates but just two NOT's! Damn! Just six hours before
the deadline. We're out of luck. Any ideas?
", asked
Alice.


"Well, we obviously cannot hope to
get three NOTs out of two NOTs
", replied Bob.


"I guess you're right ...", said Alice
with a frown on her face and her shoulders dropping. Then
suddenly she jumped and said, "No, wait!
It can be done! Here it it!
" And pulling out a pen
from her pocket, she sketched a circuit of a piece of paper.



"Wow! You're a genius, Alice!",
cried Bob.
Are you as smart as Alice? In general, how
many signals can we invert using n NOT gates and any number
of AND and OR gates? No other gates may be used.
Hint:
Yet to write.
Solution:
Yet to write.

Title: Dijkstra's Problem
ID: dijkstra
Puzzle:
There are n+1 processors named 0, 1, ..., n. Processor i has
a counter C(i) that takes values in the range [0, n]. Its
initial value is arbitrarily chosen from [0, n]. Processor 0
is said to be privileged if C(0) = C(n). Processor
i, where i > 0, is said to be privileged if C(i) is not equal
to C(i-1).
At successive clock ticks, exactly one out of
possibly several privileged processors is arbitrarily chosen
and its counter is updated as follows:

If processor 0 is chosen, we set C(0) =
(C(0) + 1) mod (n+1).
Otherwise, we set
C(i) = C(i+1).
Prove that after a bounded number of clock
ticks, exactly one processor will be privileged. And that
this will continue to hold forever.
Hint:
Yet to write.
Solution:
Yet to write.

Title: Tiling Problem
ID: tiling
Puzzle:
A big rectangle is composed of smaller rectangles, each having an
integral width or integral height or both. Does the big
rectangle enjoy the same property?
Hint:
Yet to write.
Solution:
Yet to write.

Title: Marked Squares
ID: markedsquares
Puzzle:
Consider an n by n grid of squares. A square is said to be a
neighbour of another one if it lies directly above/below or
to its right/left. Thus, each square has at most four
neighbours. Initially, some squares are marked. At
successive clock ticks, an unmarked square marks itself if
at least two of its neighbours are marked. What is the
minimum number of squares we need to mark initially so that
all squares eventually get marked?
Hint:
Yet to write.
Solution:
Yet to write.

Title: Horses on Auction
ID: horsesauction
Puzzle:
You are the chief guest at an auction, where an unknown
number of horses will be revealed and auctioned, one after
the other, in no particular order. You are a connoiseur of
horses, and can judge whether one horse is 'better' than
another. Being the chief guest, you have a one-time
privilege of selecting a horse, after it is revealed, but
before it gets auctioned off. You get to keep this horse
for yourself. Your objective is to maximize the probability
of selecting the best horse. What do you do?
Hint:
Yet to write.
Solution:
Strategy: Pick the first horse that is superior to all horses that
have been revealed so far. Analysis: If the very first horse is the
k-th best horse, then the probability of picking the best horse with
this strategy is 1 / (k - 1). The overall probability of picking
the best horse is approximately [c + log (n - 1)] / n where c is
Euler's constant. One could extend this idea to wait even more,
i.e., pick the s-th horse that beats all horses that went
by. Identifying the optimal value of s is an interesting
exercise. Is s = 1 optimal?

Title: Red Card
ID: redcard
Puzzle:
Alice repeatedly draws a card randomly, without replacement,
from a pack of fifty-two cards. Bob has a one-time privilege to
raise his hand just before a card is about to be drawn. If the
card drawn is Red just after Bob raises his hand, Bob wins;
otherwise he loses. Is there any way for Bob to be correct more
than half the times he plays this game with Alice?

Hint:
Yet to write.
Solution:
No, Bob cannot be right more than half the times. Yet to write proof.

Title: Geometry without a Ruler
ID: noruler
Puzzle:
Using only a compass (and without a straight edge or a ruler),
is it possible to identify (a) the midpoint of two points? (b)
the center of a circle? (c) all four corners of a square, given
two of them?
Hint:
Yet to write.
Solution:
Using only a compass, all those points can be constructed which can
be constructed using a compass and a ruler. Surprising, isn't it!
The constructions are far more complicated though.

Title: Chessboard with Signs
ID: chessboardsigns
Puzzle:
An 8x8 chessboard has either a plus or a minus written in each
of its sixty-four squares. You are allowed to repeatedly choose
a 3x3 or a 4x4 block of squares and invert all signs within
it. How would you go about getting rid of all the minuses?
Hint:
Yet to write.
Solution:
There are 36 3x3 blocks and 25 4x4 blocks. An arbitrarily long
sequence of inversions is equivalent to inverting some subset of
these 36 + 25 = 61 blocks in any order. Thus at most 2^61 distinct
chessboard positions can be derived if we start with all minuses.

Title: Five Card Trick
ID: fivecardtrick
Puzzle:
A mathemagician asks a volunteer to give him five cards drawn
from a pack of fifty-two. He hands one card back to the
volunteer and arranges the remaining four in some sequence he
chooses. He then hands the sequence to a second volunteer and
leaves the room. His assistant enters. The assistant asks the
second volunteer to read out aloud the sequence handed to
him. The assistant ponders a little and correctly announces the
identity of the card held by the first volunteer. How could
this be done? In general, how large a deck of cards can be
handled if n cards are drawn initially?
Hint:
Yet to write.
Solution:
Yet to write.

Heavy Marble Puzzle- What is the minimum number of weighings needed to be certain of identifying the heavy marble?


You have eight marbles and a two-pan balance. All the marbles weigh the same, except for one, which is heavier than all the others. The marbles are otherwise indistinguishable. You may make no assumptions about how much heavier the heavy marble is. What is the minimum number of weighings needed to be certain of identifying the heavy marble?

The first step in solving this problem is to realize that you can put more than one marble in each pan of the balance. If you have equal numbers of marbles in each pan, then the heavy marble must be in the group on the heavy side of the balance. This saves you from having to weigh each marble individually, and it enables you to eliminate many marbles in a single weighing.

Once you realize this, you are likely to devise a binary search-based strategy for finding the heavy marble. In this method, you begin by putting half of the marbles on each side of the balance. Then you eliminate the marbles from the light side of the balance and divide the marbles from the heavy side of the balance between the two pans. As shown in Figure 1, you continue this process until each pan holds only one marble, at which point the heavy marble is the only marble on the heavy side of the balance. Using this process you can always identify the heavy marble in three weighings.



This may seem to be the correct answer. The solution wasn’t completely obvious, and it’s an improvement over weighing the marbles one by one. If you’re telling yourself that this seemed too easy, you’re right. The method described so far is a good start, but it’s not the best you can do.

How can you find the heavy marble in fewer than three weighings? Obviously, you’ll have to eliminate more than half the marbles at each weighing, but how can you do that?

Try looking at this problem from an information flow perspective. Information about the marbles comes from the balance, and you use this information to identify the heavy marble. The more information you derive from each weighing, the more efficient your search for the marble will be. Think about how you get information from the balance: You place marbles on it and then look at the result. What are all the possible results? The left pan side could be heavier, the right side could be heavier, or both sides could weigh exactly the same. So there are three possible results, but so far you’ve been using only two of them. In effect, you’re only using 2/3 of the information that each weighing provides. Perhaps if you alter your method so that you use all of the information from each weighing you will be able to find the heavy marble in fewer weighings.

Using the binary search strategy, the heavy marble is always in one of the two pans, so there will always be a heavy side of the balance. In other words, you can’t take advantage of all the information the balance can provide if the heavy marble is always on the balance. What if you divided the marbles into three equal-sized groups, and weighed two of the groups on the balance? Just as before, if either side of the balance is heavier, you know that the heavy marble is in the group on that side. But now it’s also possible that the two groups of marbles on the balance will weigh the same - in this case, the heavy marble must be in the third group that’s not on the balance. Because you divided the marbles into three groups, keeping just the group with the heavy marble eliminates 2/3 of the marbles instead of half of them. This seems promising.

There’s still a minor wrinkle to work out before you can apply this process to the problem at hand. Eight isn’t evenly divisible by three, so you can’t divide the eight marbles into three equal groups. Why do you need the same number of marbles in each group? You need the same number of marbles so that when you put the groups on the balance the result doesn’t have anything to do with differing numbers of marbles on each side. Really, you need only two of the groups to be the same size. You’ll still want all three groups to be approximately the same size so you can eliminate approximately of the marbles after each weighing no matter which pile has the heavy marble.

Now you can apply the three-group technique to the problem you were given. Begin by dividing the marbles into two groups of three, which you put on the balance, and one group of two, which you leave off. If the two sides weigh the same, the heavy marble is in the group of two, and you can find it with one more weighing, for a total of two weighings. On the other hand, if either side of the balance is heavier, the heavy marble must be in that group of three. You can eliminate all the other marbles, and place one marble from this group on either side of the balance, leaving the third marble aside. If one side is heavier, it contains the heavy marble; if neither side is heavier, the heavy marble is the one you didn’t place on the balance. This is also a total of two weighings, so you can always find the heavy marble in a group of eight using two weighings. An example of this process is illustrated in Figure 2




Important

Generalize your solution. What is the minimum number of weighings to find a heavy marble among n marbles?

This is the part where the interviewer determines whether you hit on the preceding solution by luck or because you really understand it. Think about what happens after each weighing. You eliminate 2/3 of the marbles and keep 1/3. After each weighing you have 1/3 as many marbles as you did before. When you get down to one marble, you’ve found the heavy marble.

Based on this reasoning, you can reformulate the question as, “How many times do you have to divide the number of marbles by 3 before you end up with 1?” If you start with 3 marbles, you divide by 3 once to get 1, so it takes one weighing. If you start with 9 marbles you divide by 3 twice, so it takes two weighings. Similarly, 27 marbles require three weighings. What mathematical operation can you use to represent this “How many times do you divide by 3 to get to 1” process?

Because multiplication and division are inverse operations, the number of times you have to divide the number of marbles by 3 before you end up with 1 is the same as the number of times you have to multiply by 3 (starting at 1) before you get to the number of marbles. Repeated multiplication is expressed using exponents. If you want to express multiplying by 3 twice, you can write 32, which is equal to 9. When you multiply twice by 3 you get 9 - it takes two weighings to find the heavy marble among 9 marbles. In more general terms, it takes i weighings to find the heavy marble from among n marbles, where 3i = n. You know the value of n and want to calculate i, so you need to solve this for i. You can solve for i using logarithms, the inverse operation of exponentiation. If you take log3 of both sides of the preceding equation you get i = log3 n.

This works fine as long as n is a power of 3. However, if n isn’t a power of 3, then this equation calculates a noninteger value for i, which doesn’t make much sense, given that it’s extremely difficult to perform a fractional weighing. For example, if n = 8, as in the previous part of the problem, log3 8 is some number between 1 and 2 (1.893 to be a little more precise). From your previous experience, you know it actually takes two weighings when you have eight marbles. This seems to indicate that if you calculate a fractional number of weighings you should round it up to the nearest integer.

Does this make sense? Try applying it to n = 10 and see whether you can justify always rounding up. log3 9 is 2, so log3 10 will be a little more than two, or three if you round up to the nearest integer. Is that the correct number of weighings for 10 marbles? For 10 marbles, you would start out with two groups of 3 and one group of 4. If the heavy marble were in either of the groups of 3, you could find it with just one more weighing, but if it turned out to be in the group of 4 you might need as many as two more weighings for a total of 3, just as you calculated. In this case the fractional weighing seems to represent a weighing that you might need to make under some circumstances (if the heavy marble happens to be in the larger group) but not others. Because you’re trying to calculate the number of weighings needed to guarantee you’ll find the heavy marble, you have to count that fractional weighing as a full weighing even though you won’t always perform it, so it makes sense to always round up to the nearest integer. In programming, the function that rounds up to the nearest integer is often called ceiling, so you might express the minimum number of weighings needed to guarantee you’ll find the heavy marble among n marbles as ceiling(log3(n)).


Tip

For the group of 4 (out of the total of 10 marbles), you would divide the 4 marbles into two groups of 1 and one group of 2. If the heavy marble happened to be in the group of 2, you would need one more weighing (the third weighing) to determine which was the heavy marble. A fractional weighing may also represent a weighing that will always be performed but won’t eliminate a full 2 2/3 of the remaining marbles. For example, when n = 8, the fractional weighing represents the weighing needed to determine which marble is heavier in the case where the heavy marble is known to be in the group of two after the first weighing. In any case, it must be counted as a full weighing, so rounding up is appropriate.

This is another example of a problem designed such that the wrong solution occurs first to most intelligent, logically thinking people. Most people find it quite difficult to come up with the idea of using three groups, but relatively easy to solve the problem after that leap. It’s not an accident that this problem begins by asking you to solve the case of eight marbles. As a power of 2, it works very cleanly for the incorrect solution, but because it’s not a power (or multiple, for that matter) of 3 it’s a little messy for the correct solution. People generally get the correct answer more quickly when asked to solve the problem for nine marbles. Look out for details like this that may steer your thinking in a particular (and often incorrect) direction.

This problem is a relatively easy example of a whole class of tricky problems involving weighing items with a two-pan balance. For more practice with these, you might want to try working out the solution to the preceding problem for a group of marbles in which one marble has a different weight, but you don’t know whether it’s heavier or lighter.

Bridge Crossing Puzzle: What is the least amount of time in which all the travelers can cross from one side of the bridge to the other?

A party of four travelers comes to a rickety bridge at night. The bridge can hold the weight of at most two of the travelers at a time, and it cannot be crossed without using a flashlight. The travelers have one flashlight among them. Each traveler walks at a different speed: The first can cross the bridge in 1 minute, the second in 2 minutes, the third in 5 minutes, and the fourth takes 10 minutes to cross the bridge. If two travelers cross together, they walk at the speed of the slower traveler.

What is the least amount of time in which all the travelers can cross from one side of the bridge to the other?

Because there is only one flashlight, each trip to the far side of the bridge (except the last trip) must be followed by a trip coming back. Each of these trips consists of either one or two travelers crossing the bridge. To get a net movement of travelers to the far side of the bridge, you probably want to have two travelers on each outbound trip and one on each inbound trip. This strategy gives you a total of five trips, three outbound and two inbound. Your task is to assign travelers to the trips so that you minimize the total time for the five trips. For clarity, you can refer to each traveler by the number of minutes it takes him to cross the bridge.

Number 1 can cross the bridge at least twice as fast as any of the other travelers, so you can minimize the time of the return trips by always having 1 bring the flashlight back. This suggests a strategy whereby 1 escorts each of the other travelers across the bridge one by one.

One possible arrangement of trips using this strategy is illustrated in Figure . The order in which 1 escorts the other travelers doesn’t change the total time: The three outbound trips have times of 2, 5, and 10 minutes, and the two inbound trips are 1 minute each, for a total of 19 minutes.


This solution is logical, obvious, and doesn’t take long to discover. In short, it can’t possibly be the best solution to an interview problem. Your interviewer would tell you that you can do better than 19 minutes, but even without that hint you should guess you arrived at the preceding solution too easily.

This puts you in an uncomfortable, but unfortunately not unusual, position. You know your answer is wrong, yet based on the assumptions you made, it’s the only reasonable answer. It’s easy to get frustrated at this point. You may wonder if this is a trick question: Perhaps you’re supposed to throw the flashlight back or have the second pair use a lantern. No such tricks are necessary here. A more-efficient arrangement of trips exists. Because the only solution that seems logical is wrong, you must have made a false assumption.

Consider your assumptions, checking each one to see if it might be false. First among your assumptions was that outbound and inbound trips must alternate. This seems correct - there’s no way to have an outbound trip followed by another outbound trip because the flashlight would be on the wrong side of the bridge.

Next, you assumed that there would be two travelers on each outbound trip and one on each return trip. This seems logical, but it’s harder to prove. Putting two travelers on an inbound trip seems terribly counterproductive; after all, you’re trying to get them to the far side of the bridge. An outbound trip with only one traveler is potentially more worthwhile, but coupled with the requisite return trip all it really accomplishes is exchanging the positions of two travelers. Exchanging two travelers might be useful, but it will probably waste too much time to be worth it. Because this possibility doesn’t look promising, try looking for a false assumption elsewhere and reconsider this one if necessary.

You also assumed that 1 should always bring the flashlight back. What basis do you have for this assumption? It minimizes the time for the return trips, but the goal is to minimize total time, not return trip time. Perhaps the best overall solution does not involve minimized return trip times. The assumption that 1 should always return the flashlight seems hard to support, so it probably merits further examination.

If you’re not going to have 1 make all the return trips, then how will you arrange the trips? You might try a process of elimination. You obviously can’t have 10 make a return trip, because then he’d have at least three trips, which would take 30 minutes. Even without getting the remaining travelers across, this is already worse than your previous solution. Similarly, if 5 makes a return trip then you have two trips that are at least 5 minutes, plus one that takes 10 minutes (when 10 crosses). Just those three trips total 20 minutes, so you won’t find a better solution by having 5 make a return trip.

You might also try analyzing some of the individual trips from your previous solution. Because 1 escorted everyone else, there was a trip with 1 and 10. In a sense, when you send 1 with 10, 1’s speed is wasted on that trip because the crossing still takes 10 minutes. Looking at that from a different perspective, any trip that includes 10 always takes 10 minutes, no matter which other traveler goes along. Therefore, if you’re going to have to spend 10 minutes on a trip, you might as well take advantage of it and get another slow traveler across. This reasoning indicates that 10 should cross with 5, rather than with 1.

Using this strategy, you might begin by sending 10 and 5 across. However, one of them has to bring the flashlight back, which you already know isn’t the right solution. You’ll want to already have someone faster than 5 waiting on the far side. Try starting by sending 1 and 2 across. Then have 1 bring the flash-light back. Now that there’s someone reasonably fast (2) on the far side, you can send 5 and 10 across together. Then 2 returns the flashlight. Finally, 1 and 2 cross the bridge again. This scheme is illustrated in Figure

The times for the respective trips under this strategy are 2, 1, 10, 2, and 2, for a total of 17 minutes. Identifying the false assumption improved your solution by 2 minutes.

This problem is a slightly unusual example of a class of problems involving optimizing the process of moving a group of items a few at a time from one place to another. More commonly, the goal is to minimize the total number of trips, and there are often restrictions on which items can be left together. This particular problem is difficult because it suggests a false assumption (that 1 should escort each of the other travelers) that seems so obvious you may not even realize you’re making an assumption.

Three switches puzzle: Determine which light corresponds to each switch.

You are standing in a hallway next to three light switches, all of which are off. Each switch operates a different incandescent light bulb in the room at the end of the hall. You cannot see the lights from where the switches are. Determine which light corresponds to each switch. You may go into the room with the lights only once.

The crux of this problem comes quickly to the fore: There are only two possible positions for each switch (on or off) but there are three lights to identify. You can easily identify one light, by setting one switch differently than the other two, but this leaves you no way to distinguish the two left in the same position.

When confronted with a seemingly impossible task, you should go back to basics. The two key objects in this problem seem to be the switches and the lights. What do you know about switches and light bulbs? Switches make or break an electrical connection. When a switch is on, current flows through it. A light bulb consists of a resistive filament inside an evacuated glass bulb. When current flows through the filament, it consumes power, producing light and heat.

How can these properties help you solve the problem? Which of them can you detect or measure? The properties of a switch don’t seem too useful. It’s much easier to look at the switch to see whether it’s off or on than to measure current. The light bulbs sound a little more promising. You can detect light by looking at the bulbs, and you can detect heat by touching them. Whether there is light coming from a bulb is determined entirely by its switch - when the switch is on, there is light; when it’s off, there isn’t. What about heat? It takes some time for a light to heat up after it’s been switched on, and some time for it to cool after it’s switched off, so you could use heat to determine whether a bulb had been on, even if it were off when you walked into the room.

You can determine which switch goes with each bulb by turning the first switch on and the second and third off. After ten minutes, turn the first switch off, leave the second off, and turn the third on. When you go into the room, the hot dark bulb corresponds to the first switch, the cold dark bulb to the second, and the lit bulb to the third.

Although there’s nothing truly outlandish about this question - it’s not just a stupid play on words, for instance - it is arguably a trick question. The solution involves coming up with something somewhat outside the definition of the problem. Some interviewers believe that questions like this will help them identify people who can “think outside the box” and develop nontraditional, innovative solutions to difficult problems. In the authors’ opinion, these problems are cheap shots that don’t prove much of anything. Nevertheless, these problems do appear in interviews, and you should be prepared for them.

In a hall with k lockers, how many lockers remain open after pass k?


Suppose you are in a hallway lined with 100 closed lockers. You begin by opening all 100 lockers. Next, you close every second locker. Then you go to every third locker and close it if it is open or open it if it is closed (call this toggling the locker). You continue toggling every nth locker on pass number n. After your hundredth pass of the hallway, in which you toggle only locker number 100, how many lockers are open?

In a hall with k lockers, how many lockers remain open after pass k?

This problem is designed to seem overwhelming. You don’t have time to draw a diagram of 100 lockers and count 100 passes through them. Even if you did, solving the problem that way wouldn’t illustrate any skill or intuition, so there must be some trick that can be used to determine how many doors will be open. You just have to figure out what that trick is.

It’s unlikely that you’re going to be able to intuit the solution to this problem by just staring at it. What can you do? Although it’s not practical to solve the entire problem by brute force, solving a few lockers in this manner is reasonable. Perhaps you’ll notice some patterns you can apply to the larger problem.

Start by choosing an arbitrary locker, 12, and determining whether it will end open or closed. On which passes will you toggle locker 12? Obviously on the first pass, when you toggle every locker, and on the twelfth pass when you start with 12. You don’t need to consider any pass after 12 because those will all start farther down the hall. This leaves passes 2 through 11. You can count these out: 2, 4, 6, 8, 10, 12 (you toggle on pass 2); 3, 6, 9, 12 (on 3); 4, 8, 12 (on 4); 5, 10, 15 (not on 5); 6, 12 (on 6); 7, 14 (not on 7), and so on. Somewhere in the middle of this process, you will probably notice that you toggle locker 12 only when the number of the pass you’re on is a factor of 12. If you think about this, it makes sense: When counting by n, you hit 12 only when some integer number of n’s add to 12, which is another way of saying that n is a factor of 12. Though it seems simple in retrospect, this probably wasn’t obvious before you worked out an example.

The factors of 12 are 1, 2, 3, 4, 6, and 12. Correspondingly, the operations on the locker door are open, close, open, close, open, close. So locker 12 will end closed. The solution seems to have something to do with factors. Primes are numbers with unique factor properties. Perhaps it would be instructive to investigate a prime numbered locker. You might select 17 as a representative prime. The factors are 1 and 17, so the operations are open, close. It ends closed just like 12. Apparently primes are not necessarily different from nonprimes for the purposes of this problem.

What generalizations can you make about whether a locker ends open or closed? All lockers start closed and alternate between being open and closed. So lockers are closed after the second, fourth, sixth, and so on, times they are toggled - in other words, if a locker is toggled an even number of times, then it ends closed; otherwise, it ends open. You know that a locker is toggled once for every factor of the locker number, so you can say that a locker ends open only if it has an odd number of factors.

The task has now been reduced to finding how many numbers between 1 and 100 have an odd number of factors. The two you’ve examined (and most others, if you try a few more examples) have even numbers of factors. Why is that? If a number i is a factor of n, what does that mean? It means that i times some other number j is equal to n. Of course, because multiplication is commutative (i × j = j × i), that means that j is a factor of n, too, so the number of factors is usually even because factors tend to come in pairs. If you can find the numbers that have unpaired factors, you will know which lockers will be open. Multiplication is a binary operation, so two numbers will always be involved, but what if they are both the same number (that is, i = j)? In that case, a single number would effectively form both halves of the pair and there would be an odd number of factors. When this is the case, i × i = n. Therefore, n would have to be a perfect square. Try a perfect square to check this solution. For example, for 16, the factors are 1, 2, 4, 8, 16; operations are open, close, open, close, open - as expected, it ends open.

Based on this reasoning, you can conclude that only lockers with numbers that are perfect squares end open. The perfect squares between 1 and 100 (inclusive) are 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100. So 10 lockers would remain open.

Similarly, for the general case of k lockers, the number of open lockers is the number of perfect squares between 1 and k, inclusive. How can you best count these? The perfect squares themselves are inconvenient to count because they’re unevenly spaced. However, the square roots of the perfect squares greater than zero are the positive integers. These are very easy to count: The last number in the list of square roots gives the number of items in each list. For example, the square roots of 1, 4, 9, 16, and 25 are 1, 2, 3, 4, and 5; the last number in the list of square roots is the square root of the largest perfect square and is equal to the number of perfect squares. You need to find the square root of the largest perfect square less than or equal to k.

This task is trivial when k is a perfect square, but most of the time it won’t be. In these cases, the square root of k will be a noninteger. If you round this square root down to the nearest integer, then its square is the largest perfect square less than k-just what you were looking for. The operation of rounding to the largest integer less than or equal to a given number is often called floor. Thus, in the general case of k lockers, there will be floor(sqrt(k)) lockers remaining open.

The key to solving this problem is trying strategies to solve parts of the problem even when it isn’t clear how these parts will contribute to the overall solution. Although some attempts, such as the investigation of prime numbered lockers, may not be fruitful, others are likely to lead to greater insight about how to attack the problem, such as the strategy of calculating the result for a single locker. Even in the worst case, where none of the things you try lead you closer to the final solution, you show the interviewer that you aren’t intimidated by difficult problems with no clear solution and that you are willing to keep trying different approaches until you find one that works.

Your Title

My Blog List