Job Interview Brain Teasers

by Curtis Krauskopf

When an interviewer tests you with a brain-teaser, 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 snap-answer 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 eight-quart 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 state-machine 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 state-machine 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.

800 -> 350 (1)


800 -> 503 (2)

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.

800 -> 350 (1) -> 053 (2)
               -> 800 (3)  X   
               -> 323 (4)
800 -> 503 (2) -> 053 (1)  X
               -> 800 (5)  X
               -> 530 (6)

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 state-machine 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 real-life

Why is a manhole cover round?

Geometry in Real-Life 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 state-machine 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.

ABCD|_ 	-> CD|AB (1) (time: 2)
       	-> BD|AC (2) (time: 5)
       	-> BC|AD (3) (time: 10)
       	-> AD|BC (4) (time: 5)
        -> AC|BD (5) (time: 10)   
        -> AB|CD (6) (time: 10)

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.

ABCD|_ -> CD|AB (1) (time: 2)
                    -> ACD|B (7)  (elapsed time: 3)
                    -> BCD|A (8)  (elapsed time: 4)
       -> BD|AC (2) (time: 5)
                    -> ABD|C (7)  (elapsed time: 6)
                    -> BCD|A (9)  (elapsed time: 10)
       -> BC|AD (3) (time: 10)
                    -> ABC|D (7)  (elapsed time: 11)
                    -> BCD|A (10) (elapsed time: 20)  X   
       -> AD|BC (4) (time: 5)
                    -> ABD|C (8)  (elapsed time: 7)
                    -> ACD|B (9)  (elapsed time: 10)
       -> AC|BD (5) (time: 10)
                    -> ABC|D (8)  (elapsed time: 12)
                    -> ACD|B (10) (elapsed time: 20)  X
       -> AB|CD (6) (time: 10)
                    -> ABC|D (9)  (elapsed time: 15)
                    -> ABD|C (10) (elapsed time: 20)  X

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.

Previous Answers

More C++ Answers