Technical interviews and the Towers of Hanoi | Hacker News Reader

Technical interviews and the Towers of Hanoi

blog.tjd.phlegethon.org

35 pointsmrry52 comments

So... you (the writer) have noticed that the more experienced a candidate is, the less likely they are to get your interview question "right" (i.e., done the way you want). And...you haven't questioned this process?

Sometimes, I think half the reason developers stay in unsatisfactory jobs is that they don't want to go through interviews led by interviewers like this guy. Who I think is probably similar to the majority of interviewers, based on my experience.

Agree. I also note without surprise that there's no qualification as to why the recursive solution is "better".

Indeed I think the author does a great job explaining why the recursive solution is usually worse, namely: harder to maintain, less intuitive, and only marginally faster.

Also, depending on the language you work in, a function call may be quite expensive, compared to a straight loop.

> Sometimes, I think half the reason developers stay in unsatisfactory jobs is that they don't want to go through interviews led by interviewers like this guy.

There's really no doubt about it. I myself have refrained to apply or turned down a number of recruiters at various places that I'd otherwise be interested in because I know what the interview process is going to be like and whatever respectable pay raise they might offer isn't worth the trouble. Interviewing really takes a chunk out of you sometimes.

That said, I'd gladly take a booming industry with incredibly annoying interviews over a dead or dying industry.

>That said, I'd gladly take a booming industry with incredibly annoying interviews over a dead or dying industry.

Absolutely. Other than the interviews and the occasional death march, it's a great profession (I mean that seriously).

"I used to take that as an indicator of how good a coder the candidate was, but more recently I’ve realised that it’s a much better indicator of how long it is since they went to college"

I would take this as evidence that he is questioning the process.

>I would take this as evidence that he is questioning the process.

So I thought, but then he goes on to talk about how "sadly" no one uses the recursive solution these days.

I take that as evidence that his questioning is feeble at best.

Yeah without meaning to I think the author wrote the most effective condemnation of white-board-coding interviews I've ever seen.

And for whatever it is worth, I've been hacking code since 6510 assembler on the C64 and I'm (still) enamored with recursion as a concept but would virtually always avoid using it both in real code and as an interview answer (unless requested) because it is firmly in the bucket of programming concepts that are Cool and sometimes (though VERY rarely) The Right Thing, but are usually just unnecessary abstract complexity when trying to reason about a system during debug/maintenance. Of course, this is something you have to internalize after being bitten by doing the Cool thing multiple times in the past, which is likely why the interviewer is seeing people with more real world experience avoiding the overly clever solution. Counting this against them is insanity.

And, yeah, the whole interviewing developers thing is a complete mess from start to finish, with dozens and dozens of different "best-practice" systems, none of which even come close to approximating actual work conditions (and all fraught with deficiencies allowing for all sorts of false positive and false negative results). I don't think there's a single job I've eventually left due to unhappiness where I didn't stay quite a bit longer than I should have just because dealing with interviews is such a terrible chore, almost completely divorced from the work it is supposed to test proficiency for.

I'm somewhat the opposite. I try to go on interviews on a regular basis, even when I have no interest in switching jobs. I figure that the more I do something, the better I'll be at it. I also like problem solving, so the majority of questions I get asked are fun to work through.

One of the things you get with practice is the presence of mind to not get flustered and to always remember to ask the necessary questions. In the case of this interviewer, once he's asked the question, the first step is not to write either a recursive or iterative solution. The first step is to ask, "How big is my stack?" and/or "What are my bounds (max number of disks)?" Interviewers often ask questions that are deliberately vague to judge the candidate not only based off the answers they give, but also the questions they ask. I've had interviews where I missed answers and still got an offer because I took the time to fully understand the problems they were giving me.

I can't recommend practice interviewing highly enough. It may seem like a waste of time, and it will eat entire days of vacation time, but the experience is very valuable and I think I'm a better interviewee and interviewer because of it.

This guy is looking to employ himself, not someone who'll write good software. This comes up again and again in developer recruiting.

"Gasp! I CANNOT believe you call yourself a developer when you haven't mastered hoogleflatz! ANY REAL software engineer (like me) has a total grasp of hoogleflatz. Hoogleflatz is ESSENTIAL to all software development. When you go to work you must arrive at 9:00AM and leave at the end of the day with zero result because you don't know Hoogleflatz.

Why are we having so much trouble recruiting awesome engineers? There must be a skills shortage."

>This guy is looking to employ himself

This is the key shortfall in interviews across all skills, not just tech. Most people tend to gravitate towards the familiar and naturally nothing is more familiar than yourself.

This also affects bias towards gender, race, etc.

Agreed

>This is the key shortfall in interviews across all skills,

Sorry, but as someone who changed professions after 10 years in another profession (which was pretty universally viewed as a "brainy" type of work), I strongly disagree. My interviews (of which I had several over 10 years) were always done respectfully, and first and foremost were interested in teamwork skills, personality, and work habits. But when subject matter expertise was examined, my interviewers probed exclusively for knowledge we used in our everyday work.

My former colleagues are uniformly appalled to hear what tech interviews are like. Likewise my wife, who works in yet another profession.

Edit: Downvote away. I love working in software development, but until software developers face up to the fact that their interview process is actively discouraging more people from entering the profession, there will continue to be a "skill shortage" (a term that is also bandied about for political reasons, but that's another story). It's not management that conducts these kinds of interviews, it's fellow devs.

Edit 2: And just to clarify, I'm not talking about knowing time/space complexity and common data structures and algorithms, all of which are important. I'm talking about asking puzzle problems like Tower of Hanoi and then marking people down for using an iterative instead of recursive solution.

Very few of us will ever know what it's like to be hired as a mid-level programmer and lawyer, physician, or dentist.

But my impression is that programming interviews are roughly analogous to quizzing a mid-career physician on end of chapter exercises from a second year college organic chemistry textbook.

Of course, it could be that towers of hanoi is more relevant to the day to day practice of programming than ochem is to radiology. Or it could be that the process of becoming a physician is sufficiently regulated that you just don't need to worry about whether people have the required background, so physicians only have to pass their exit exams once, whereas programmers have to pass a randomly chosen subset of it every time they interview.

>my impression is that programming interviews are roughly analogous to quizzing a mid-career physician on end of chapter exercises from a second year college organic chemistry textbook.

That is a strikingly accurate analogy.

And regarding exams/licensing/certification, I'd gladly study to pass an extremely hard software engineering exam in order to not have to go through insipid interviews every 2-3 years.

I've read about the california state bar and how difficult and brutal it is to pass. It's a three day exam, and I'm sure it's tough.

But I like to remind people of what I experienced last time I interviewed. It was for three different jobs, and interviews took about four and a half days. Topics covered were:

Add a node to binary tree

Print it recessively

Print it iteratively

Prove that the dual of the primal is the primal of the dual, using matrix notation.

Find the long term state probabilities in a Markov chain.

Write various sql statements (showing that you know outer joins, among other things)

Denormalize a set of sql tables

Swap two integers without creating a third variable

Print all permutations of a string

Formulate a linear program, then demonstrate that it can be done with a greedy algorithm that doesn't require an optimization formulation

Write a good hashing function

Answer questions about what actual data structures back the different container classes in Java

Sort a bunch of things

Show how to find the most common character in an n-length string with a minimum number of storage variables (i.e., no using a hash and picking it at the end, you have to keep a counter that swaps around)

Design a database for a restaurant reservation system…

That wasn't even all they asked. That's just what I remember. It was days of exhausting, 8-hour interviews. As programmers, we go through this over and over. I didn't get an offer, probably because I hadn't really done markov chains or data structures in a while and seemed fuzzy on my answers. I usually study a lot prior to an interview, but I was very busy around that time with programming work.

Yeah, one reason I don't interview much anymore is that I feel I've loaded those topics into my short-term exam ready memory for the last time.

It doesn't seem that the author actually asks candidates to code up the Tower of Hanoi in an interview.

> I usually start with a fairly easy warm-up question — some sort of a toy problem like an operation on lists or trees, often the kind of thing that has a neat recursive solution.

Binary tree problems and some linked list problems often have fairly obvious recursive solutions -- perhaps that's what he's referring to. I doubt anyone would consider the Tower of Hanoi problem "easy". It's definitely an interesting one to investigate in a blog post say, or for one's own enrichment -- it seems like that's what the author is doing.

Of course there's no way of knowing the author's intentions unless he himself clarifies it, but this is what I think.

> I always ask people to write code in a technical interview, and I usually start with a fairly easy warm-up question — some sort of a toy problem like an operation on lists or trees, often the kind of thing that has a neat recursive solution.

Interview questions that have a "neat" solution are usually bad interview questions and more a reflection on the fact that the interviewer is trying to feel smarter than the interviewee.

On top of that, if the interviewee writes the neat solution right away, what have you learned exactly? Either she's very good or she already knew the neat solution, so you're going to have to ask additional questions to clarify. Why not skip the gimmick question and get to the real interview part?

One big thing that this does is mentioned in the problem: warming up.

When you're under pressure, you don't want to just step off the street and start talking about some super-hard problem. But if you don't warm up at all, this is exactly what happens. And that's just the candidate! This also lets the interviewer get into interviewing mode.

An interview is basically a type of performance. And what performer steps on stage without warming up?

Usually you have just one hour, there is literally no time for warm ups.

I never understood how interviewers let these kinds of arbitrary details influence their consideration of the candidate. If the interviewer had explicitly requested an iterative function, they probably would have gotten one. You can't fault someone for doing what they feel like doing within the [lack of] parameters you assign.

That said, holy shit is it scary when you open up a framework or library and see a mess of recursive functions. Pity the poor soul who has to troubleshoot their app when it ends up a long trail of performance issues in someone else's library.

> There’s a particular sinking feeling that comes when the candidate starts on one of these problems and immediately writes a for loop.

> in most embedded/real-time/kernel work, ... When there are strict bounds on stack sizes, recursive algorithms can be downright dangerous, especially when operating on user-supplied data.

Seems like an excellent interview question. Certainly from the first three paragraphs, I can tell that this is a company that recruits mediocre graduates because they don't pay attention to real-world constraints. A company I definitely shouldn't be working for.

There's a bias that interviewers need to watch for when they interview candidates. People who write interview questions often find the answers easy, and for the obvious reason that they are the ones that have spent the most time with it.

From a candidate's point of view, the question is new and every solution must be thought through, lest the interviewer thinks that the candidate isn't very smart.

This is a way to optimize hiring towards those who are good at whiteboarding code under pressure. In other words, a task that is not at all related to the vast majority--if not any--software development roles.

Instead we should give them boring tedious problems in a code base with no documentation and an incomplete buggy spec, and grade their solution in a couple weeks?

Funny. I'm always leery of the developer that instinctively reaches for the recursive solution. Unless your data or algorithm is recursive in nature (e.g. trees, nested data, QuickSort, etc.), than a recursive solution is going to be less intuitive and more difficult for the next guy to maintain.

Ideally, you match your implementation with the data structure and/or algorithm you'll be dealing with.

I never go for the recursive solution rightaway, if I'm the interviewer and the developer goes for the iterative solution then it means that he/she didn't memorized(or googled) a few lines of code, instead he/she is actually trying to solve the problem, even if the developer doesn't succeed it's more valuable than the developer that got the recursive solution at the first attempt, sadly most interviewers think that if you can solve puzzles with the "right" solution in the minimum time, then you are the best candidate for the job.

It's certainly possible to learn to "think recursively," and thus be able to work out recursive solutions to new problems in the same way that other people work out iterative solutions to new problems.

The book The Little Schemer is a great way to learn to think recursively. It has been 5 years since I read it, and I haven't kept the skill fresh, so I've probably lost most of it.

http://www.amazon.com/The-Little-Schemer-4th-Edition/dp/0262...

I'm not sure how you can call any specific data structure or algorithm "recursive in nature." Trees can be defined and operated on iteratively. Likewise, lists can be define and operated on recursively.

I don't agree with the author that iterative code is bad (within a certain context). In fact, I tend to write iterative solutions first when I am just testing something out and develop more elegant, recursive solutions when I have a better understanding of the problem (which might not be possible when you are dealing with interview anxiety and an interviewer breathing down your neck).

I didn't get the impression he was saying that. Quote:

"The truth is that in most embedded/real-time/kernel work, we almost never see actual recursion. When there are strict bounds on stack sizes, recursive algorithms can be downright dangerous, especially when operating on user-supplied data."

He set the tone at the beginning of the article with the following:

"There’s a particular sinking feeling that comes when the candidate starts on one of these problems and immediately writes a for loop"

The tail call optimization IS a conversion to an iterative format. I'm leery of speedup claims without seeing the code that produced them.

Yeah, that read like hand waving by someone who doesn't understand what tco actually does.

And on top of that, recursive solutions aren't always easy to reason about later on when someone has to maintain it.

HN, you really need to stop dismissing out-of-hand anything you read that doesn't match your expectations. It's embarrassing.

1. The author is Tim Deegan, who's a former Xen maintainer and currently does low-level work in a data storage startup. He holds a PhD from a reputable university (Cambridge...) and has published several papers (http://www.tjd.phlegethon.org/). This doesn't immediately make him right of course, but it does mean he's probably not an idiot and his statements merit a little consideration.

2. The bottom paragraph of the article explains his reasoning behind hoping for a recursive version in interviews: "When I actually implemented this in C, the iterative version was not only messier, but also nearly four times slower than the recursive one. ... a modern CPU will predict all the return addresses correctly. And the work of figuring out which of the two candidate disks to move next and where to is quite a bit more than just finding the spare peg. Since any Towers of Hanoi problem that will complete in less than a day should fit entirely in L1 cache, the extra instructions and (potentially mispredicted) branches to find the next move are worse than the extra memory operations for the recursion." It's not clear from some of the comments in this thread that many people read all the way down to that paragraph.

3. His test case is here: http://tjd.phlegethon.org/blog/hanoi.c ... if he has done something wrong, this would be the place to go looking for it. I don't see anything obviously wrong with his iterative version, although I'm getting a double-free error after compiling and running his code.

I've believed for years that iterative approaches gave better performance than recursive versions. This probably goes all the way back to working in 68k assembly. I'm pretty sure there's a chapter in Beautiful Code that suggests iterative is better than recursive, performance-wise. But if Tim's right, then I've learned something valuable today.

edit: I'm busy today and my C is suuuuper rusty; I think there might be something in that for loop in finish() that's screwing up the pegs[2] that's being passed to free() a couple of lines later, but I don't really have the time to debug it. Hopefully someone else is willing to try, I'd like to see what the actual results turn out to be in different environments.

Thank you. It seems that people read the title of the post, skimmed through half of it, then rushed to post their opinion. Reminds me of an Ars Technica experiment I read about in Jeff Atwood's blog [1]:

"Ars Technica ran a little experiment in 2011. When they posted Guns at home more likely to be used stupidly than in self defense, embedded in the last sentence of the seventh paragraph of the article was this text:

If you have read this far, please mention Bananas in your comment below. We're pretty sure 90% of the respondants to this story won't even read it first.

The first person to do this is on page 3 of the resulting discussion, comment number 93."

[1] http://blog.codinghorror.com/because-reading-is-fundamental-...

Nice try discounting our opinions about interviewing by citing a completely unrelated forum and article. I'm sure you know the name of that particular logical fallacy.

Despite my frustration with the attitude displayed toward interviewers, I actually did read to the end because I'm in the middle of reading Concrete Mathematics[1], which starts with the Tower of Hanoi. So I was interested in his solution.

1. Concrete Mathematics: A Foundation for Computer Science. Graham, Knuth, Patashnik.

I'm not sure how citing the article discounts your opinion about interviewing. All it does is say that it's common for people to make comments without reading through entire articles. I'm sure there are plenty of people who do read through articles, but I'm also sure there are plenty of others who don't, and the experiment proves it.

It's not the blog post content that people are reacting to (which I agree was edifying), it's the attitude toward interviews.

No one is complaining about or criticising his code or his discussion of the Towers of Hanoi solution (although some skepticism has been expressed about the exact speedup he's getting). I'm quite sure the man has forgotten more about embedded programming than I know.

Let's agree that the tone of his article could use a little work. What about the substance of it?

I read his article as, "too many candidates don't realize that recursive solutions are better than iterative ones now."

If that's true, it seems like a big deal. He's not really arguing for knowledge of some arcane language feature or framework widget; this would be a fundamental aspect of programming methodology, something that might be broadly applicable.

edit: sorry, I just realized we're talking at cross-purposes. Yeah, his approach to interviews could maybe use some work. I just didn't read that as what the article was about, so I was ignoring that as a conversational topic.

No, I agree with you 100% that the blog is very interesting. I'll probably check out his code in greater detail.

But developers are really getting tired of these types of interviews and interviewers. I can just feel the anger and frustration in others I know rising. It's morally and ethically wrong to make formal complaints to Congress about developer shortages and then turn around and exclude well-qualified candidates because hiring devs are clinging to some deprecated model of interviewing that has a mediocre true positive rate but an awfully, awfully high false negative rate.

1. I learned years ago that just because someone has a PhD, does not mean they're not also an idiot. Work with enough PhDs and you'd agree.

2. The comments are a reaction to the story, not a reflection on the character of the author. Most comments are about interviewers that make the same mistake the author did before the author realized their erroneous assumption. They're engaging in group validation of an immediate opinion or feeling without thorough analysis, or what is also known as "commenting on the internet".

3. Remember one of the cardinal rules of HN about meta-commenting? Yeah, it doesn't really help.

Here's an iterative solution which is shorter and 3 times as fast:

  void iterative(int n)
  {
      int from[2][3] = {{0,1,2},{0,2,1}};
      int   to[2][3] = {{1,2,0},{2,1,0}};
      for(int i=1; i<1<<n; i++)
      {
          int disk = __builtin_ctz(i);
          int count = (i>>(1+disk))%3;
          int parity = (disk^n)&1;
          move(from[parity][count], to[parity][count]);
      }
  }

Neat. Were you able to get his code to run? What did you change / what compiler flags did you use?

I removed the free() call because it was crashing. I also added a cast to the malloc() because I was compiling in C++. Compiled with

  g++ -o hanoi hanoi.cpp -O2 -lrt

Thanks. I had also cast malloc() but didn't think to just comment out free().

So I'm seeing similar results as you. Your iterative implementation is about 3x faster than the author's, but still not as fast as the recursive version. I'm surprised!

And the funny part of it all is that most times the job being interviewed for is simply maintaining/building a web or mobile app for which the candidate will never in the history of their entire career need to think about solving any problem even remotely close to this one. Just end up hiring lots of "experts" capable of creating complex solutions for simple problems.

Funny, about 13 years ago, someone told me about this exact problem / solution. His professor said that it was impossible to solve the problem without recursion. He solved it with the exact solution given, and basically got an A in his class for it (a bet with the professor).

Oh well. moving on.

This is one of the worst articles I've ever read.

It's disappointing to see someone talk so smugly about a bad opinion.

I was asked this question in an interview and the only reason I was able to come up with a solution was that I had taken Spivak's calculus previous semester and the proof was one the exercise questions for a chapter on induction.

Is this a racist question to be asking in an interview?

I seem to remember some back story about people being imprisoned and forced to solve this problem during the Vietnam war (possibly in a tower -- for extra meta level punishment).

Reply on news.ycombinator.com