Job Interview Brain Teasers
by Curtis Krauskopf
When an interviewer tests you with a brainteaser,
just remain calm. The worst answers are confrontational
in which you ask, "How does putting water in a jar relate
to the job I'm interviewing for?". Be careful about
giving a snapanswer to a question, even if you think
you've heard it before. The interviewer is expecting
you to think about the problem and engage him with poignant
questions. Giving the wrong answer quickly is not the
impression you want to give.
Almost as bad as the confrontational answers are flippant
answers, such as "I would go to the store and buy a
measuring cup". However, you could start your answer
that way with a qualification: "Assuming I can't go
to the store...". The latter answer shows that you can
think outside of the box whereas the first one dismisses
the question sarcastically.
The interviewer is also testing to see how you react
when you are told you had a wrong answer or when you
can't find the answer. Certainly, getting hostile and
attacking the question or complaining about how the
interviewer didn't explain it well enough does not earn
you points even though it might feel good for your damaged
ego. Instead, sincerely ask what the answer is and how
it is solved. Seem genuinely interested even if you
don't care what the answer is  the interviewer asked
the question, so it seems important to him for some
reason!
The Three Jugs Problem
Two friends who have an eightquart jug of water wish
to share it evenly. They also have two empty jars, one
holding five quarts, the other three. How can they each
measure exactly 4 quarts of water?
The Three Jugs Problem Answer
There are many variations on the three jugs problem,
with different situations (sometimes sand, sometimes
different jug volumes). The goal is generally the same:
make a container hold exactly some amount of substance
that can't be trivially measured.
Maybe you're blessed to be able to intuitively solve
these kinds of problems. If so, just give the answer
and impress the interviewer! For the rest of us, we
have to solve it using some iterative process.
All of the versions of this problem can be solved by
applying statemachine techniques. Starting with an
initial condition, what are all of the possible permutations
that lead to the next state? From that state, what are
all of the possible permutations that lead to the third
state and so on? Many of the possibilities might be
physically impossible (such as pouring water from an
empty jug) and others might undo the previous step.
If paper or a whiteboard is available, show your design
skills by plotting out the progress of your statemachine
until you reach an answer. Most often, though, an interviewer
will stop you midway through once it's clear that you're
able to solve the problem.
Table 1 shows the initial conditions
for the Three Jugs problem. Volume represents the amount
of water in the jug in each state. The jugs are arbitrarily
labeled A, B and C to easily identify them. Table
2 shows the state transitions in the problem. I've
also given each of the transitions a unique number.
For bookkeeping purposes, you'll want to find a way
to discover that you've already visited a previous state.
This prevents infinite loops. For the initial conditions
in Table 1, notice that the volume
row uniquely represents the state. Using the volumes
from jugs A, B and C, let's call 800 the initial state
(the first digit is for jug A, the second digit is for
jug B and the third digit is for jug C).
Now we know how to represent the final condition. That
occurs when there are 4 quarts of water in two jugs.
Only jugs A and B can contain four quarts of water.
So the final condition is 440.
Using your whiteboard or paper, draw the initial condition
using the code 800 and show the next state using the
permutations in Table 2. Your
diagram will look something like Figure
A.
The three jugs problem starts with all of the water
in Jug A. Figure A shows the
first legal moves from Table 2
that are applied to the initial conditions in Table
1. The transition ID number is in parenthesis.
From the initial conditions, there were only two valid
transitions. I put the transition ID in parenthesis
after the state number to help remember what happened.
The next state transition diagram will look something
like Figure B.
The next step in the three jugs problem is to apply
the transitions from Table 2
to the states recorded in Figure
A. Three of the states are duplicates of a previous
state. Those states are culled from further investigation
by putting an X next to their transition numbers.
An 'X' is placed next to any state that is previously
represented in the diagram, even if it's for another
branch in the current state. This happened with 053
in the 800>503 branch because the first transition
(A to B and A to C) was already 'discovered'.
By iteratively following this process, you'll either
impress (or bore) the interviewer and he'll stop the
question or you're arrive at an answer, whichever comes
first.
Update: March 22, 2010
A decompile.com reader, Kang Zhao, has graciously
provided his solution to the three jugs problem.
I'm providing it here in case it makes more
sense than the statemachine solution that is
provided above.
Kang Zhao writes, "The key is to get 1 quart
water. Because 8  5 = 3, 5  3 = 2, and 8 
3 = 5, we need to find another way: 6  5 =
3 + 3  5 = 1".
Initial state: 
A(8) 
B(5) 
C(3) 
8 
0 
0 
Solution: 
3 
5 
0 
3 
2 
3 
6 
2 
0 
6 
0 
2 
1 
5 
2 
1 
4 
3 
4 
4 
0 

Geometry in reallife
Why is a manhole cover round?
Geometry in RealLife Answer
Some questions test your ability to think of a solution
that doesn't involve programming and instead tests your
general knowledge of chemistry, physics, geometry, biology
and courses you took that you might have thought you
never needed.
As with all brain teaser questions, it's not vitally
important that you get the answer because you're being
tested on how you solve a problem. One solution is to
discuss the merits of a round manhole cover compared
to other shapes.
For a humorous transcript of this answer, see Brian
Groth's blog at msdn.com.
We'll cross that bridge when we get to it
There are 4 women who want to cross a bridge. They
all begin on the same side. You have 17 minutes to get
all of them across to the other side. It is night. There
is one flashlight. A maximum of two people can cross
at one time. Any party who crosses, either 1 or 2 people,
must have the flashlight with them. The flashlight must
be walked back and forth, it cannot be thrown, etc.
Each woman walks at a different speed. A pair must walk
together at the rate of the slower woman's pace.
 Woman 1: 1 minute to cross
 Woman 2: 2 minutes to cross
 Woman 3: 5 minutes to cross
 Woman 4: 10 minutes to cross
For example if Woman 1 and Woman 4 walk across first,
10 minutes have elapsed when they get to the other side
of the bridge. If Woman 4 then returns with the flashlight,
a total of 20 minutes have passed and you have failed
the mission. What is the order required to get all women
across in 17 minutes? Now, what's the other way?
Bridge Answer
The Bridge problem is similar to the Three
Jugs problem. In both cases, things need to be transferred
from one container to another (a side of a river versus
a jug). The same statemachine techniques I described
in the Three Jugs problem can be applied to the Bridge
problem.
Table 3 shows the problem's
initial conditions and Table 4
shows all of the transition states.
The last transition, ID#10, can be omitted because
the problem can not be solved in time by having woman
D travel from the right side to the left side by herself.
Starting with the initial conditions of ABCD (in which
the letters represent each of the women and the  symbol
represents the river bank) the goal is to arrive at
ABCD in 17 or fewer elapsed minutes. Figure C shows
the first set of transitions in the problem and Figure
D shows the return trips for the first two possibilities
in Figure C.
All of the women initially start on the left bank.
Figure C shows the first transition
from the initial conditions in Table
3 using the states in Table 4.
The return trips from Figure C
are extrapolated using the transitions from Table
3. Illegal moves (moving a woman who is not on the
right bank) have been ignored. Three of the subsequent
states exceeded the 17 minute time limit. Those states
are marked with an 'X'.
Using this technique, you will find both of the solutions.
Don't worry about the proliferation of states in the
first few iterations. The 17 minute time limit puts
a tight leash on the problem and you'll find the solution
pretty quickly.
