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.
> 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.
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.
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.
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.
"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.
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 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.
> 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?
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.
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."
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.
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.
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.
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."
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).
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).
[+] [-] jnbiche|11 years ago|reply
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.
[+] [-] nilkn|11 years ago|reply
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.
[+] [-] georgemcbay|11 years ago|reply
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.
[+] [-] na85|11 years ago|reply
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.
[+] [-] curun1r|11 years ago|reply
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.
[+] [-] RogerL|11 years ago|reply
I would take this as evidence that he is questioning the process.
[+] [-] andrewstuart|11 years ago|reply
"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|11 years ago|reply
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.
[+] [-] zak_mc_kracken|11 years ago|reply
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|11 years ago|reply
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?
[+] [-] peterwwillis|11 years ago|reply
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.
[+] [-] sago|11 years ago|reply
> 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.
[+] [-] typicalrunt|11 years ago|reply
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.
[+] [-] bkeroack|11 years ago|reply
[+] [-] onezeno|11 years ago|reply
[+] [-] ryandvm|11 years ago|reply
Ideally, you match your implementation with the data structure and/or algorithm you'll be dealing with.
[+] [-] pacofvf|11 years ago|reply
[+] [-] baddox|11 years ago|reply
[+] [-] dreaminvm|11 years ago|reply
[+] [-] ojbyrne|11 years ago|reply
"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."
[+] [-] analognoise|11 years ago|reply
[+] [-] ch4s3|11 years ago|reply
And on top of that, recursive solutions aren't always easy to reason about later on when someone has to maintain it.
[+] [-] thaumaturgy|11 years ago|reply
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.
[+] [-] peterwwillis|11 years ago|reply
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.
[+] [-] jnbiche|11 years ago|reply
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.
[+] [-] anindyabd|11 years ago|reply
"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-...
[+] [-] pieguy|11 years ago|reply
[+] [-] thaumaturgy|11 years ago|reply
[+] [-] nwyouth|11 years ago|reply
[+] [-] Justsignedup|11 years ago|reply
Oh well. moving on.
[+] [-] nbevans|11 years ago|reply
[+] [-] mattxxx|11 years ago|reply
[+] [-] dominotw|11 years ago|reply
[+] [-] tbrock|11 years ago|reply
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).