What should I do if I'm asked a famous question in a technical interview which I've previously solved?

Question

In preparation for a technical job interview, it is fairly common for candidates to practice using example problems, with plenty of resources available for providing questions and answers for the candidate to use for reference.

A well-known example from computer science is the use of the Tower of Hanoi problem in order to understand recursion. So, my question is, what if I go into an interview, and the interviewer asks me to solve the Tower of Hanoi problem when I've already solved it in preparation for this interview? Ideally, I would like to take advantage of the situation and show the interviewer my problem-solving skills without having to pretend like I've never seen the same problem before.

Answer 1

You simply tell them you have a solution to the problem, and you demonstrate it. If an interviewer is going to pull out an extremely common problem, he or she should not be surprised when candidates have already seen it before.

Answer 2

First off, if this subject interests you, I have a number of articles in my blog queue coming up in the next couple of weeks about how I deal with technical interview questions as an interviewer.

To address your specific question: this is not a problem I ask, but suppose it were. Why would I do so? To find out:

• Does the candidate recognize this famous, standard, old problem? If not, that's an interesting data point that I can explore further.

• If they are not familiar with the problem, can they devise a solution? This is actually the bit I care about the least. A candidate who cannot solve this problem right out of the gate is not going to succeed on my team, so I presume that they can devise a solution quickly regardless as to whether the problem is known or not.

• I will under-specify the problem and see what choices the candidate makes. The problem is to produce a "sequence of moves". OK, does the candidate dump the moves to the console, like it was 1970? Do they produce a list? Do they produce a lazily-evaluated sequence? What structure is used to represent the move? I can tell a lot about the candidate just from the signature of the method they choose to write. Do they ask a clarifying question or just jump right in and code up the first thing that comes to mind?

• When writing code to solve a problem recursively, is the code well organized? Are the base case and recursive steps clearly identified? A candidate who does not have thoroughly internalized the structure of recursive algorithms is, again, not going to succeed on my team.

• Can the candidate clearly justify why the code is or is not correct? If the code is correct then they should be able to explain in words why it is. If it is not correct, they should not be able to explain why it is correct, they should be able to find the bug.

• Can the candidate suggest test cases that demonstrate the correctness of the algorithm?

• Now that we have a correct solution, I can start really probing their knowledge. What is the time complexity of this algorithm given the input is the height of the stack of disks? If the candidate has chosen to recursively produce a lazy sequence of moves, this question is harder than you might think. What is the space complexity in both heap and stack space?

• Now we can start making the problem harder. What if we were in an environment where the stack space was severely constrained but heap space was not; can the candidate use an explicit stack to turn the algorithm into an iterative, non-recursive algorithm?

• Suppose I asked the candidate to use continuation passing style to implement a stackless version; do they know what I am talking about? and if so, can they do it?

The specific algorithm is totally unimportant. It's a jumping-off point for the real task of the interview, which is determining if the candidate can reason about code using the tools in their toolbox. I have never once had to solve the tower of hanoi problem in my job. I have many, many times had to rewrite a recursive algorithm into an iterative algorithm with an explicit stack in a stack-constrained environment. A candidate who cannot do so is unlikely to succeed on my team.

So, the answer to your question is: solve the problem in good faith. If the problem is really a "fizzbuzz" -- just a test to see if you can write code at all -- then you will pass it quickly and the interviewer will move on. But I would use a simple, standard problem as an opportunity to probe the candidate's skills more deeply.

Answer 3

I've been asked several of these standard questions in different interviews. I think all interviewers knew/assumed that I've heard about the problem and possible solutions. The important thing when answering such questions is that many interviewers are primarily interested in:

• How good are you in explaining things? I've seen some really bad explanations from students who understood the problem and the solution well but were not able to explain them to anybody.
• How good are you at actually implementing a solution (if implementation is part of the test)? Are you aware of potential problems (e.g. the run time) and alternative solutions?

So you can't just state:

This is a common problem, the solution uses recursion.

but you have to try to explain it to the interviewer, providing some context if available (run time, generalization ...). If possible, make some drawings to support your explanations. Show the context of the problem and state alternative solutions. In short: prove that you are able to explain a solution to a colleague.

In programming exams, I always try to create production code. Do not type some minimal pseudo-codish solution, but add comments, tests (if appropriate) and the like.

Answer 4

If you're worried about being dishonest, it's easy enough to say, "Oh, yes, I've seen this problem before. The solution I came up with was ..."

When interviewing for my current job, they gave me a quiz that included what amounted to the classic fizz-buzz problem, but using different words and with some slight differences. So I just said, "Oh, this is a lot like fizz-buzz", and proceeded to give a solution.

If you were warned that this question would come up in the interview (maybe the recruiter tells you or a friend interviewed there recently) and you looked up an answer on the Internet and memorized it, and then you trot this answer out as if you just figured it out, okay, that could be cheating. But if you frankly say, "oh yeah, I read a solution to this problem not long ago", and can explain why and how the solution works, even if you didn't think of it yourself, you're demonstrating a level of understanding. I've occasionally interviewed people who were able to give a solution to a problem but it quickly became clear they had no idea where this solution came from or how it worked. Obviously they just copied it from somewhere.

As someone else on here said, if an interviewer is going to use commonly-known problems -- fizz-buzz or square roots or whatever -- it would be absurd for them to then accuse someone of cheating because he's heard of the problem before. (I've never been asked about the Towers of Hanoi on an interview, and I don't remember the details of the problem so besides a vague, "yeah, I'm pretty sure the solution was repetitive or recursive or something", I'd have to figure it out again anyway. But whatever.)

Answer 5

This has happened to me -- not Tower of Hanoi in particular, but a problem I recognize and already know the solution to.

What has worked for me (and a few others I know who've been in this situation) is to say something like this:

I've seen this recently; in fact I just solved this last week. Would you like me to proceed or do you want to ask me a different question?

This does a few things:

• It demonstrates your knowledge without being misleading.
• It gives them the option. Some places are firm about asking everybody the same questions to make their interviews as uniform as possible.
• It gives them the option to test you differently. They might skip this one or they might decide that if you can toss it off quickly, they can ask you a second question.
• It subtly reminds them that this is probably not the only place you're interviewing.

An interview is a microcosm of your eventual working relationship (if you go there). Are you honest? Are you flexible? Are you focused on the problem at hand, which isn't solving Tower of Hanoi but demonstrating your skills? Are you a team player, working with the interviewer to get what you both want? All of that will reflect well on you in the evaluation of "soft skills".

Answer 6

As far as I'm concerned, these problems are often ridiculous and only really exist to allow the interviewers to feel smug about themselves. Yes you can get a grasp on how some people might go about solving a problem, but it's not like anyone is ever going to pluck a number out of thin air or just randomly guess at an algorithm.

I'm going to assume this was a development interview as that's where these kinds of problems abound. I personally think it's far more instructive to show a candidate some bad code, ask them what it does and how it can be improved. It's amazing how effective this can be.

Frankly if I got a question on a problem and it had a solution like Hanoi I'd just give them my best answer. Knowing something from experience isn't cheating in any way; it's how working actually works.