33

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.

  • 16
    Why do you need to pretend anything? You are given a problem and you are asked to solve it. So solve it! Are you going to tell an interviewer that you can't do Fizz Buzz because you solved Fizz Buzz at an interview with another company? – Vietnhi Phuvan May 25 '15 at 10:12
  • 6
    @VietnhiPhuvan That's not the point of the question. The reason why I initially asked the question is because the interviewer might be looking to see how I can solve a problem which I haven't encountered before, in order to observe my problem-solving skills. If I already know the solution, I would be deceiving them by pretending that I thought of it on the spot. So I do not want to do that; what I am seeking advice on is showing my problem-solving skills, despite knowing the solution to the specific problem beforehand – AwesomeSauce May 25 '15 at 12:57
  • 1
    @concerned_user - most of the interviewers are looking to see if you can solve a particular puzzle they happen to like. I'm not condoning that in any way, but that is the reality of things. Just do it (TM)! – Davor May 25 '15 at 13:29
  • 3
    Interviewers ask candidates to solve problems, and interviewers couldn't care less whether you have solved the problem before. Where does the requirement that you must not have ever seen the problem before come from? You are making this kind of requirement up. And I am saying that you are making this kid of requirement up because I have NEVER run into an interviewer who'd concoct something like this. Not in 25 years. – Vietnhi Phuvan May 25 '15 at 14:16
  • 1
    Tower of Hanoi? What are you, a C64 programmer? where's your Delorean? Sorry, we never got the hoverboards... – The Wandering Dev Manager Nov 3 '16 at 18:52
76

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.

  • 6
    This. If they want to avoid a prepared answer they should come up with more creative answers. Usually it's not about the answer but about the thought process though. Why do you think your implementation is the way to go? If they hand you their own implementation, can you tell the advantages of both? – Mast May 25 '15 at 7:58
  • 10
    I have easily enough killed candidates with questions that should be no surprise to them if they knew the stuff they claimed they knew. I don't need to concoct exotic problems. I am not wasting any time with those who can't aplly their fundamentals. – Vietnhi Phuvan May 25 '15 at 14:57
  • 6
    And I think sometimes it’s not only about the thought process, but also about your ability to communicate both your thought process, and technical decision-making. You can certainly demonstrate those skills just as well with a problem you’re familiar with. – Paul D. Waite May 25 '15 at 17:58
19

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.

  • 2
    Interesting insights on the various possible intentions of the interviewer. It is entirely possible that what they are looking for is beyond the obvious "What is the algorithm needed to solve this question?" – AwesomeSauce May 25 '15 at 8:27
  • 3
    " bit I care about the least" - this seems confusing, did you mean care about the most? – user2813274 May 25 '15 at 21:03
  • 2
    @user2813274: What I mean is that the bit "they can solve the problem / they cannot solve the problem" is very uninteresting except insofar as "cannot solve the problem" means "should not have made it past the phone screen". I am interested in how they solve the problem, and I am even more interested in using the problem as a stepping-off point for a deeper exploration of the candidate's skills. – Eric Lippert May 26 '15 at 14:05
  • Actually, I found this "problem" to be rather boring and pointless 30 years ago. With more than three towers it gets a bit more interesting. – gnasher729 Nov 3 '16 at 22:01
  • Wish I could star this answer. – cst1992 Jun 19 '17 at 12:59
10

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.

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.)

4

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".

3

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.

  • 5
    Your suggestion to show bad code and ask for suggestions of improvements is a good one, which I use frequently. (And will be writing about in a couple of weeks.) However, when I ask standard algorithm problems in interviews it is not ridiculous, and I don't do it to feel good about myself; I do it to find out just how deep the candidate's toolbox is. – Eric Lippert May 25 '15 at 4:24
  • 1
    Hmm, seems to me that it makes a lot of sense to ask questions that have, or should have, easy answers, because that allows us to eliminate unqualified candidates. If you ask a candidate to solve some very difficult problem that has baffled the greatest minds in history for thousands of years, and the candidate can't solve it in ten minutes, what does that prove? When I go on a job interview, I expect any quiz to start out with easy questions, because those are the easiest to judge and they eliminate a large number of unqualified candidates quickly. – Jay May 25 '15 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.