Technical interviews and the Towers of Hanoi

http://blog.tjd.phlegethon.org/post/107154349862/technical-interviews-and-the-towers-of-hanoi

by mrry • 12 years ago

35 52 12 years ago

blog.tjd.phlegethon.org

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

ch4s3• 12 years ago

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.

typicalrunt• 12 years ago

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.

peterwwillis2• 12 years ago

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.

dreaminvm2• 12 years ago

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

ojbyrne• 12 years ago

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

dreaminvm2• 12 years ago

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"

andrewstuart• 12 years ago

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

Peroni• 12 years ago

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.

mattxxx2• 12 years ago

Agreed

jnbiche8• 12 years ago

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.

Justsignedup• 12 years ago

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.

nbevans• 12 years ago

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

mattxxx2• 12 years ago

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

jnbiche8• 12 years ago

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.

na85• 12 years ago

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.

troels• 12 years ago

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

nilkn• 12 years ago

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.

jnbiche8• 12 years ago

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

RogerL• 12 years ago

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

jnbiche8• 12 years ago

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.

georgemcbay• 12 years ago

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.

curun1r• 12 years ago

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.

bkeroack• 12 years ago

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.

onezeno• 12 years ago

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?

ryandvm• 12 years ago

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.

pacofvf• 12 years ago

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.

baddox2• 12 years ago

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

baddox2• 12 years ago

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.

tbrock• 12 years ago

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

sago• 12 years ago

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.

dominotw• 12 years ago

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.

zak_mc_kracken• 12 years ago

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?

zck• 12 years ago

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?

sigsergv• 12 years ago

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

nwyouth• 12 years ago

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.

thaumaturgy4• 12 years ago

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.

anindyabd3• 12 years ago

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

jnbiche8• 12 years ago

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.

jnbiche8• 12 years ago

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.

thaumaturgy4• 12 years ago

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.

peterwwillis2• 12 years ago

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.

pieguy2• 12 years ago

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]);
      }
  }

thaumaturgy4• 12 years ago

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

pieguy2• 12 years ago

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

Technical interviews and the Towers of Hanoi

Related Stories