What was the best Puzzle/Brainteaser you've ever been asked at an interview? And Why?

Question

There have been many questions related to what one should ask interviewees, what you should ask a company you're interviewing at, etc. I searched and I don't think this one is a duplicate. Also, community wiki from the start.

So here goes: What is the most interesting (challenging, fun, original, useful) brainteaser or puzzle question you've been asked at an interview and why?

For me, it was this one that I was asked recently (I found a similar one online and copy-pasted it here to avoid retyping the whole thing):

There are ten gnomes. They are in the dungeon. Their captor has given the gnomes a chance of survival. Here is the offer:

He lines the gnomes up in a single-file row. This means that the tenth gnome sees the back of the person in front of him, and there is no gnome behind the tenth gnome. The ninth gnome has the tenth gnome behind him and the eighth gnome directly in front of him, and so on. Finally, the first gnome has the second gnome directly behind him, but there is no one in front of the first gnome.

The captor has a bag full of many black hats and many white hats. There is not necessarily the same number of black hats as white hats. (important) He randomly reaches into his bag and places a hat on each of the gnomes. This means that the tenth gnome can see everyone's hat except his own, the ninth gnome can see everyone's hat except his own and the tenth gnome's hat, and so on. The first gnome can see no one's hat.

The captor then takes out his gun and puts it to the temple of the tenth gnome. He asks the gnome, "What color is your hat?" If the gnome answers correctly, he lives and gets freed from the dungeon. If he does not, he dies. He continues up the line in this progression.

However, before placing the hats on the gnomes, he allows the gnomes to meet as a group and discuss a strategy to save as many of the gnomes as possible. How many gnomes can you guarantee to save, and with what strategy?

REMEMBER: When it is your turn to say the color of your hat you must ONLY say "white" or "black." If you say anything else, the king will shoot you and all of the remaining gnomes.

Once I figured out the solution to this one, the interviewer then posed another question:

What if the number of colors were switched to 4? How many gnomes can you save then?

The answer is here for those who don't like spoilers: http://tinypaste.com/b578c

Answer 1

Why are manholes round?

Answer 2

One of my favorites:

If I gave you a full grown elephant, what would you do with it?

In my opinion, there's no right answer to the question, but it really gets you, as the interviewee, thinking about all sorts of things:

• Why are they asking me this question?
• Is this a trick question?
• Is this a joke?
• What can they deduce about my technical skills from this question?
• What can they understand of my personality from this question?

Good luck answering this question quickly and confidently.

Answer 3

How do you find a needle in a haystack?

And if you come up with a duke nukem type answer... 'How do you find it without destroying the haystack or the needle'?

Answer 4

I was asked a question where the answer revolved around figuring out that some math functions rounded up and some rounded towards zero -- it was basically "why does this shape disintegrate when the model flips over?"

I gave the answer "I've been doing network programming, systems programming and compiler writing for over 20 years. I've never written a program that uses floating point numbers, so I have no idea!"

It was really funny because it was working with some computer graphics guys and these kinds of questions were their bread and butter, and the interviewer had to try so hard to think of a question that I would be able to answer using integer arithmetic.

Answer 5

"I need an elevator system designed for (some weird problem). How do you solve it?

Okay, I'm so impressed with your work, that when I build my uber-skyscraper, I'm going to pay you 5 billion dollars to design an elevator system for it. I want a revolutionary system that changes the way people think about elevators. What do you do?"

Not a traditional brain-teaser, admittedly, but I still thought it was a great question as it touches on not only areas of strict problem solving, but creative thinking, project management, and even leadership.

Answer 6

You have a extremely large array of integers on disk. All but one of the occur a even amount of times. How would you find the number that occurs a odd number of times on a system with limited memory resources?

Answer 7

One I heard secondhand was the laptop puzzle: - you have two identical laptops and a 100-storey building, and you are told that they both break when dropped from some (b'th) storey or higher, which you are trying to determine. - let us say b is an integer and uniform randomly distributed between 1..100 (you can argue that that's a Benford distribution, but anyway that's offtopic) - at each step you can choose which storey to drop one laptop off. (You can reuse that laptop till it breaks, then you use the second till it breaks.) - what strategy do you use to minimize the number of steps S needed to determine b? And what is that minimum number of steps S?

• obviously the only viable strategy that uses only ONE laptop is to drop it from every single storey 1,2,...,99,100 in ascending order. This will on average take S = 50.5 steps.

• so how do you exploit the fact that you have a second laptop, to minimize worst-case S?

• this is actually severely not as trivial as it sounds, since a single false assumption or wrong approach will prevent you from solving it, as well as generate way too much work. Hint: almost all textbook analytical approaches you have ever seen will lead you down the wrong path.

Answer 8

There is a bulb inside the room and three switches outside. The door is closed and you can't see the state of the bulb without entering the room. You can only enter the room once. How would you determine which switch control the bulb?

One possible answer is (may be there are others, I don't know): On the first switch for some time(say 10 - 15 mins), switch it off and switch on the second. Get in the room. If the bulb is glowing you know which one is the switch, else touch the bulb. If it is hot the first switch is the right one else the third one is the answer.

Answer 9

I think using brainteasers in interviews is a rubbish approach, especially as most of them are stupid questions with only one answer, or academic maths questions that great statisticians will find easy but which great programmers may not. If you're going to ask this sort of question, ask something where there are many possible solutions, where the interviewee can "show their working" and explain their ideas, so you can get a feel for their thought processes.

So if you ask "why are manhole covers round?", then don't expect the answer to be "because round covers can't fall through round holes". This usually indicates that the interviewee has seen the question before, so you learn nothing. What I would want to see are answers like:

• Pipes are often round, so a round cap makes sense
• Drills are circular
• Circles are stronger, so perhaps a circular hole is less likely to break up at the edges
• A circular hole gives the same access using less material for the cover, so is cheaper
• They're not. Loads of manhole covers are rectangular.
• Round covers can be rolled, saving the workmen's backs as they are usually very heavy.
• Round looks prettier than square, and architects are fussy
• Belt-mounted equipment is less likely to become snagged if there are no corners
• Most sewage workers are round :-)
• etc.

So I think most of the answers you'll get will be "cool questions" that are probably really bad interview questions.

Having said all that, the best question I've ever been asked was "so, would you like a job then?" ... which was the point at which I realised I was in a job interview. Up till that point I thought I was just chatting to the owner of a company I was visiting :-)

Answer 10

How would you solve the n-queens problem on a cubical "board"?

Interesting because it lead to discussions of how to represent the six faces of the cube in code, whether there were any interesting shortcuts to that, a description of how to solve a constraint problem using backtracking, etc.