7 ms·

Dissecting an interview question

67 points by bratfarrar 13y ago

danesparza 13y ago
[sarcasm]Please continue to use this question. It’s a wonderful marker for candidates (like me) who don’t want to work with folks who think questions like that are useful.[/sarcasm] To be honest, I think it’s far more interesting to set aside a real world problem that you have encountered at your company and see how a candidate would think through it (out loud, of course). Many issues you’ll need to solve on a day-to-day basis have nothing to do with programming — and instead have to do with knowing related technologies (like a TCP/IP network, or a database) and how they interact. You might be shocked to discover how many developers have a deep understanding of algorithms but can’t troubleshoot/design/architect/solve their way out of a paper bag. Also: the thought of you ACTUALLY chewing your arm off is morbidly humorous. Thanks for that. :-)
- lmm 13y ago
  > I think it’s far more interesting to set aside a real world problem that you have encountered at your company and see how a candidate would think through it (out loud, of course). So how do you do that consistently? Do you just go with whatever you were working on last week? Do you keep your favourite bugs to show to candidates? > Many issues you’ll need to solve on a day-to-day basis have nothing to do with programming — and instead have to do with knowing related technologies (like a TCP/IP network, or a database) and how they interact. Both are important, but programming is easier to test. Most candidates haven't used exactly the same technologies, so unless you happen to be an expert on every database under the sun it's very hard to ask a fair question about how to use one. And my impression is that it's easier to cargo-cult how to connect to a database than how to write a binary tree (though I've certainly seen people do both).
  - alxndr 13y ago
    I was thinking about this the last time we were hiring at work, and decided to try to take notes the next time I find a bug or issue that could be repackaged as a hiring challenge. (I haven't succeeded yet, have been too distracted trying to solve the actual issue to remember to take notes...)
  - collyw 13y ago
    I am getting asked to write a job description for new person. "What is required?" Basically I would be happy with someone who didn't have any of the required skills, as long as they had a decent attitude and were willing to learn, (and had some sort of background that was relevant). But apparently we need required skills on the ad.
- alxndr 13y ago
  > You might be shocked to discover how many developers have a deep understanding of algorithms but can’t troubleshoot/design/architect/solve their way out of a paper bag. In interviews I'm curious to hear about developers' favorite debugging tools or techniques for precisely that reason.
- mcguire 13y ago
  "You might be shocked to discover how many developers have a deep understanding of algorithms but can’t troubleshoot/design/architect/solve their way out of a paper bag." I might, but I have been shocked by the number of developers in the opposite situation: can create wonderful, beautiful designs but can't actually write code better than your average bonobo. And I won't even mention troubleshooting or actually solving problems. If you can't actually write decent code, I don't actually care if you can design or architect and I doubt your other skills would actually help me if I'm looking for a programmer. This problem in no way requires a "deep understanding of algorithms". Hell, writing a balanced tree is hardly deep understanding, and I admit I'd have a bit of an uphill struggle with that myself. But this is just basic programming logic. If you have any problems with that, I don't care if you're Bob Braden or Edgar Frank "Ted" Codd.
  - bratfarrar 13y ago
    Couldn't have said it better.
- mseebach 13y ago
  As the article says, this is fizz buzz. The purpose of it is to decide if you can program, not if you're a good programmer and not if you're a good engineer. Also, it's not an algorithm question. Actually, I'm not sure why I'm writing this up, he's specifically addressing your point in the article. > I think it’s far more interesting to set aside a real world problem that you have encountered at your company I would too. But the domain space of (things that aren't dreadfully trivial) intersect (things I can explain to an outsider in <10 minutes, including the relevant domain and context) intersect (things that an outsider can make reasonable progress on in the remaining 35 minutes) intersect (things I didn't just bloody fix when I came across them) is very, very small. I'm not even sure all those circles even overlaps, ever.
  - 6d0debc071 13y ago
    Why are you requiring 'things you didn't fix when you came across them' ? It'd seem to me those'd be ideal - and they should be sitting around in source control.
  - fishtoaster 13y ago
    If this is just Fizz Buzz (ie, a very low-level filter to see if you can program at all), why is he testing for elegance? For cleanliness? For speed of writing on a whiteboard, for god sake? He may claim it's Fizz Buzz, but he gives it and treats it like a normal programming test, with all the problems associated with it.
    - sushirain 13y ago
      I agree. This is the most important point in this discussion.
  - yohanatan 13y ago
    The whole concept of fizz buzz for an in-person whiteboard interview is absurd. The type of candidate who would fail that test should have been filtered out way earlier in the process and the type of candidate who hasn't been filtered out by that point (i.e., a 'top candidate') would be extremely insulted. I think the people who ask asinine questions like this haven't done their due diligence going in. They haven't looked at the candidate's online presence (including GitHub) nor even read her resume.
- sysop073 13y ago
  So is your argument actually that it's not necessary for people to be able to do this? Or is it that it's not nearly in-depth enough. If you're arguing the latter, I'm pretty sure everyone agrees; this was described as his version of fizzbuzz, to weed out people who literally just can't program. If you're arguing the former, that seems insane. Knowing how a TCP/IP network works is great, but if you're incapable of writing code to implement your knowledge, you're not very useful
- shasta 13y ago
  [sarcasm]Please continue to use this question. It’s a wonderful marker for candidates (like me) who don’t want to work with folks who think questions like that are useful.[/sarcasm] That's a two way street. Asking this question to ward off people who are offended to be asked it sounds like a net win to me.
  - jdowner 13y ago
    Completely agree. Also, some of the replies to the original article got me thinking about my own experiences as an interviewee. I realized that those engineers who have interviewed me in the past and did not ask much technically have been amongst the weakest engineers I have worked with. Really nice people, not really good engineers.
- Too 13y ago
  C'mon, this is not about knowing some algorithm by heart. He clearly describes the specifications and gives a test case. With that information you should be able to "troubleshoot/design/architect/solve" a solution to his problem even if you've never seen it before. This is a fizzbuzz, someone posted a quite sparse C++ solution in 75 LOC above. C++ ! That would be half in python, less than one laptop screens height.
mcguire 13y ago
* One class v1 public class BST { private BST left, right; private Integer value; } "All of the above are valid answers...." Wait, wait, wait. That one can't be empty.
- JackFr 13y ago
  value==null
  - mcguire 13y ago
    Ahh. Good point. Thanks!
- deleted 13y ago
  [deleted]
shalmanese 13y ago
How many of the candidates you interview start off by writing simple test cases to make sure they've thought of all the edge cases before they dive into coding? Have you noticed any correlation between the test-first people vs develop-first people?
- trcollinson 13y ago
  I was recently in an interview where the interviewer asked me a rather convoluted and not easily explained algorithm implementation question. It took the interviewer some 10 minutes to explain it. This interviewer was the CTO of this particular, rather success, start-up and had formerly worked at other very large and success companies all over the Bay area. My very first instinct and the thing I started to do was write tests on the board to make sure I understood the requirements. The interviewer stopped me and said "Please, just get to the code, the tests are not important." I tried to explain that the tests are paramount to the success of an implementation because I need to make sure I understand the requirements. However, the interviewer disagreed. I actually told them I was no longer interested in interviewing with their company and excused myself without writing anything further on the board. The funny part is that the next day the CTO in question called and offered me a very nice position (I respectfully declined after a discussion of my concerns). So, two points. One, not all interviewers care about tests, which is sad. Two, the original post states, "you don’t get to choose how you get interviewed". This is false, you can certainly choose how you will be interviewed, as long as you are ok with the consequences of that decision.
angersock 13y ago
The thing I particularly like about this is that the problem spec is very rigid and clear: no generic solutions (ints only), don't worry about balancing, don't worry about visibility, make it work, and then they give example usage of the API. It's really easy to screw up a one-page toy problem spec: I've done that myself, and got many replies that failed to either follow the spec or failed to identify ambiguities in it. Having a simple problem as a baseline is really helpful. That said, what I don't like about this is that it doesn't really test the candidate's ability to reason about systems or architectural things--then again, as a better "fizzbuzz", this seems to fit perfectly.
lzhou 13y ago
So the old - allocate a massive array, then use 2n+1, 2n+2 for the left/right children wouldn't have flown with you huh?
- bratfarrar 13y ago
  People will occasionally try that, but my point to them is that they should be writing a general purpose BST, which should also allow degenerate trees. So no, I do try to steer people away from theoretically correct but desperately inefficient approaches.
  - lzhou 13y ago
    That's when the flustered interviewee can either fight (patch his solution) or flight (start all over using a class with refs). The most obvious patch is to use a large hashmap instead of a massive array. Still inefficient, but no longer that desperate (and actually has some added benefits).
  - dalke 13y ago
    To be fair, it's "desperately inefficient" only in the face of unbalanced trees, no? Which mostly only happens for unrealistic scenarios. As stated, the problem assumes that time lookup isn't important, even though someone who wants a BST almost certainly chose it to get faster than linear lookup along with fast insert/delete operations and ordered searches. (Otherwise, why not use a hash table?) A self-balancing tree gives that additional guarantee, and in that case an array-based data storage won't be "desperately inefficient". Indeed I suspect an array will be competitive or even better than an object based version, where each object has its own pointer overhead and associated memory fragmentation. At the very least, the early AVL work in the 1960s used a tape for storage, and I suspect they didn't waste all that much tape space. So someone's intuition from real-world use of BSTs might end up giving you a false negative.
    - detrino 13y ago
      If you need memory efficiency you can just use a B-Tree, which also has the advantage of being more cache efficient.
ollysb 13y ago
We do a quick phone call screener and then do some pair programming. We only do half a day of pairing (for which they're paid for) but I find that this is the perfect place to do a stealth interview with the candidate. They feel comfortable because they're in their daily environment (we do it remotely using floobits, so they're sitting at their usual desk with their usual apps etc.). Here you can get a really good conversation going about things that are actually relevant to the job. Anything else just seems like guessing now.
bratfarrar 13y ago
Time for BST code golf - winner does it in the fewest characters!
- raverbashing 13y ago
  Well, depends on the language It could be funny to test with a trinary or quaternary tree,(then you have 3 or 4 - or n - children) based on a different processing of the value For example, storing complex numbers and the child corresponds to the angle relative to the parent
Jemaclus 13y ago
The "haters" section leaves out one critical reason for not doing something like this that I think is quite relevant. For those of us who have never had to do a BST before (I do not have a degree in CS, though I've been coding professionally for 8 years), expecting us to solve a BST problem in the 10, 15 minutes alotted is not really great. Even if I've never seen it before, the idea that I can solve it in 15 minutes in a high pressure environment is unrealistic. In a real world scenario, if I had to solve this kind of thing, I'd rely on existing works first. I'd google the problem, and I'd see what solutions are out there. For most problems, there's something that can point me in the right direction. For solving a BST issue from scratch in 15 minutes, well.. let's just say the first guy to come up with BSTs probably didn't come up with his solution in 15 minutes. So I would give it my best shot, but if I don't succeed, you shouldn't hold it against me. I disagree with the premise that if I can't solve this, I can't solve novel problems. That's just blatantly incorrect. I solve novel problems every day -- just not on a whiteboard and not in 15 minutes. I would much much much rather see a real-world problem. Something you've actually run into. For instance, in my line of work, I deal a lot with addresses. One of the issues that I've had to solve in the past is parsing addresses. If I give you a string of "123 Main St, Boston, MA 02123", how do you break that up into street, city, state, zip? That's something I've actually had to solve. It's something that anyone with critical thinking skills can take a decent shot at in 15 minutes. A binary search algorithm? I got a question like this one time, and I floundered because I got 90% of the way there, but I couldn't figure out how to solve one of those edge cases. The guy basically ended the interview right there, but I asked for the solution. When he gave it to me, it was something straight out of an academic textbook. I said, "Oh, you guys must use binary trees a lot." And he laughed and said, "No, never. It's low-level stuff for databases." And I just sat there, dumbstruck. Why would you give me a problem that you've never had to solve yourself? I dunno. I just disagree with the premise of the article. I think there are far better questions to ask. Problem solving in general is required -- solving academic exercises much less so.
- bad_user 13y ago
  As an former interviewer, I also preferred to give algorithmic problems to candidates, though I avoid the kind of problems that involve practice, such as graph stuff or dynamic programming. The rationale being that developers need to know the basics of CS, since we were into algorithms. With the mention that I didn't want to see perfect solutions, being much more interested in how the candidate approaches the problem. But yes, I agree - my only problem with real world stuff is that it is hard to come up with a set of 15 mins problems that involve analytical thinking.
gameguy43 13y ago
I dig this problem. One thing it doesn't touch, though, is the importance of using descriptive variable names to organize your thinking (in this case the var names are kind of a given--left, right, node..."current" is the only one someone might find a useless name for). I've found the candidate's ability to choose descriptive variable names is strongly correlated with general organization and clarity of their thinking.
codr 13y ago
Indeed time to retired it - it's really not a creative question, nor will show how creative the candidate is. While I'm all for testing the bounds of a candidate's CS knowledge, try to come up with an original problem that nobody has asked before! You can get a lot of mileage out of doing stuff like reversing numbers (without using strings), etc.
detrino 13y ago
A quick C++ implementation: http://ideone.com/hGtbts http://ideone.com/hGtbts While this was easy to do in ~10 minutes using gedit/clang/valgrind, I have to wonder how well I would have done had I been forced to use a whiteboard. > Even if you haven’t studied or used BSTs in a while – even if I have to explain them to you on the spot – you should be able to complete the problem without much difficulty. I agree with this statement if you have access to a minimal development environment, but not on a whiteboard, which is entirely unforgiving to making any changes. In the end, this serves only to select candidates who know exactly how to solve this problem beforehand.
danbruc 13y ago
I put this first, because that is why I started writing this comment. I have to disagree with some of judgments made by the author. The first one is debatable but usually you don't want duplicates in your binary search tree - I consider all the example implementations broken. But he really lost me when he started talking about the coding style. The given example is not perfect but I consider it better then most of the other examples when it comes to coding style - if and else without braces, if with break but without else. Everywhere. It is a lot of religion, it is a lot of personal preferences, but all the more it seems really wrong to judge more on personal preferences of style than on correctness and other hard facts. And here what should have come first. I think this is a relative unrealistic task because writing your own data structures is quite a rare task for most programming jobs. Nonetheless it is a very basic task and every professional developer should be able to get this right within 15 to 30 minutes.
mrfusion 13y ago
I'll bet he ends up with a lot of employees who are great at writing BST's. Are they great at solving the problems his business faces? Who knows?
hackdays 13y ago
As daunting and necessary interviews and phone screens are , there is one thing that's surprisingly not used enoughto vet a candidate - Referrals. At http://referralhire.com http://referralhire.com we are adding that important data point to your hiring process. To have a person referred by an accomplished developer is extremely valuable and is something that cannot be judged in an interview. It will also help avoid a lot of false negatives! Very talented developers we have met were rejected at multiple interviews just because of the interview day performance. All companies need to start using this more in their candidate search and decision making process.
- collyw 13y ago
  I like the idea, but how does it not fail in the same way linked in does - when your mother endorses your SQL skills?
spinlock 13y ago
My problem with whiteboarding anything other than pseudo code is that I'm pretty dyslexic and I've spent years learning syntax at the keyboard. That learning does not translate to the whiteboard. To give an example of how much the presentation of problems matters to me, the first time I took the GREs I got a 340 on the verbal. The problem was that I had practiced out of a book not on a computer. The second time I to the GREs I scored a 740 on the verbal because I spent the time to learn how to take the test. Anyway, I don't have the time to learn how to program on the whiteboard. I also don't think it's a valid signal of how well I can program at a computer.
theboss 13y ago
>Top candidates If they are top candidates, why are you asking them to solve a problem that might as well be copied directly from a college text book? >my version of fizzbuzz How many times do you write a for/while loop a day when programming. A lot. How many times do you implement a full BST a day. I'd guess about 0.
agentultra 13y ago
Isn't the optimal strategy for an interviewee to game the system? There are groups like http://codingforinterviews.com http://codingforinterviews.com where you can find a set of classic and popular problems to memorize. Interview in rounds and refine your problem set. As interviewers... is this what you're looking for? What are the selection criteria after this then?
- deleted 13y ago
  [deleted]
kstenerud 13y ago
Generally, when it comes to coding, I'll ask the interviewer if we can just do it on my laptop in a real development environment. Nobody actually codes on a whiteboard, so why should it happen in an interview? I want to play with the code, reason about it, refactor it as my understanding of the problem space expands. I can't do that on a whiteboard.
- collyw 13y ago
  On the other hand, I think I write better code when I sit down and think about it first. Sketch some ideas. Sometimes implementing bit helps change your way of thinking, as you see problems that you didn't before.
namelezz 13y ago
Dude, you lost me when you consider "Switching the left and right sides" a critical mistake. It's an interview. Candidates can be very stressful and make mistakes easily. Also you are interviewing a human not a machine.
gumby 13y ago
I find the responses so far on HN quite interesting. The author of the article is pretty clear, but still, people question the appropriateness or whether it's passive aggressive. What you want to know from a programming question is: - have you actually written code and can you still do so? - do you have a "feel" for how the code works or are you a cut 'n paste person? - do you know "enough" (the last is elusive: it's like being able to calculate in your head: sure, I use a calculator, but I can tell when I see the result if I've made a key press error along the way because I have a rough idea of what the answer will look like.). And this is another reason not to sweat the small stuff. The odd lost semicolon is no big deal; not knowing the difference between recursion and iteration is. "Real" problem are rarely bite sized. Plus the interviewee won't have enough context to know which parts of the problem statement are significant and which aren't. Much better to provide something simple and abstract that only takes a couple of lines to answer. Another good starter question is "make a deck of cards however you like and shuffle it." An amazing number of people feel this is under constrained and ask for more definition. I don't care about the implementation of the deck (integers mod 13 for face and divided by 4 for suit work OK, or you could define an object). It's surprisingly common that people just make a complicated copy or inverse than an actual shuffle. One guy reversed the deck and when I gently asked if it was actually random laughed out loud, smacked himself on the forehead, rubbed out a bit of brain damage on the whiteboard and put a random() in. He turned out to be an awesome programmer. No way did I want him to feel bad about making a silly mistake. He knew how to solve that (and a couple of other problems). A little problem like this supplies plenty to talk about (what if we did this? How would you deal with this scaling up) to show the interviewee how we think about things and vice versa. As for the address problem: it is basically a huge set of special cases. That's a different kind of problem and not actually a programming question.
collyw 13y ago
Why would you implement a binary search tree in any of those languages. There are likely to be well written, tested, optimized libraries out there for that sort of thing.
- GFK_of_xmaspast 13y ago
  Thanks for reading!

67 points by bratfarrar 13y ago

[sarcasm]Please continue to use this question. It’s a wonderful marker for candidates (like me) who don’t want to work with folks who think questions like that are useful.[/sarcasm] To be honest, I think it’s far more interesting to set aside a real world problem that you have encountered at your company and see how a candidate would think through it (out loud, of course). Many issues you’ll need to solve on a day-to-day basis have nothing to do with programming — and instead have to do with knowing related technologies (like a TCP/IP network, or a database) and how they interact. You might be shocked to discover how many developers have a deep understanding of algorithms but can’t troubleshoot/design/architect/solve their way out of a paper bag. Also: the thought of you ACTUALLY chewing your arm off is morbidly humorous. Thanks for that. :-)

lmm 13y ago
> I think it’s far more interesting to set aside a real world problem that you have encountered at your company and see how a candidate would think through it (out loud, of course). So how do you do that consistently? Do you just go with whatever you were working on last week? Do you keep your favourite bugs to show to candidates? > Many issues you’ll need to solve on a day-to-day basis have nothing to do with programming — and instead have to do with knowing related technologies (like a TCP/IP network, or a database) and how they interact. Both are important, but programming is easier to test. Most candidates haven't used exactly the same technologies, so unless you happen to be an expert on every database under the sun it's very hard to ask a fair question about how to use one. And my impression is that it's easier to cargo-cult how to connect to a database than how to write a binary tree (though I've certainly seen people do both).
- alxndr 13y ago
  I was thinking about this the last time we were hiring at work, and decided to try to take notes the next time I find a bug or issue that could be repackaged as a hiring challenge. (I haven't succeeded yet, have been too distracted trying to solve the actual issue to remember to take notes...)
- collyw 13y ago
  I am getting asked to write a job description for new person. "What is required?" Basically I would be happy with someone who didn't have any of the required skills, as long as they had a decent attitude and were willing to learn, (and had some sort of background that was relevant). But apparently we need required skills on the ad.
alxndr 13y ago
> You might be shocked to discover how many developers have a deep understanding of algorithms but can’t troubleshoot/design/architect/solve their way out of a paper bag. In interviews I'm curious to hear about developers' favorite debugging tools or techniques for precisely that reason.
mcguire 13y ago
"You might be shocked to discover how many developers have a deep understanding of algorithms but can’t troubleshoot/design/architect/solve their way out of a paper bag." I might, but I have been shocked by the number of developers in the opposite situation: can create wonderful, beautiful designs but can't actually write code better than your average bonobo. And I won't even mention troubleshooting or actually solving problems. If you can't actually write decent code, I don't actually care if you can design or architect and I doubt your other skills would actually help me if I'm looking for a programmer. This problem in no way requires a "deep understanding of algorithms". Hell, writing a balanced tree is hardly deep understanding, and I admit I'd have a bit of an uphill struggle with that myself. But this is just basic programming logic. If you have any problems with that, I don't care if you're Bob Braden or Edgar Frank "Ted" Codd.
- bratfarrar 13y ago
  Couldn't have said it better.
mseebach 13y ago
As the article says, this is fizz buzz. The purpose of it is to decide if you can program, not if you're a good programmer and not if you're a good engineer. Also, it's not an algorithm question. Actually, I'm not sure why I'm writing this up, he's specifically addressing your point in the article. > I think it’s far more interesting to set aside a real world problem that you have encountered at your company I would too. But the domain space of (things that aren't dreadfully trivial) intersect (things I can explain to an outsider in <10 minutes, including the relevant domain and context) intersect (things that an outsider can make reasonable progress on in the remaining 35 minutes) intersect (things I didn't just bloody fix when I came across them) is very, very small. I'm not even sure all those circles even overlaps, ever.
- 6d0debc071 13y ago
  Why are you requiring 'things you didn't fix when you came across them' ? It'd seem to me those'd be ideal - and they should be sitting around in source control.
- fishtoaster 13y ago
  If this is just Fizz Buzz (ie, a very low-level filter to see if you can program at all), why is he testing for elegance? For cleanliness? For speed of writing on a whiteboard, for god sake? He may claim it's Fizz Buzz, but he gives it and treats it like a normal programming test, with all the problems associated with it.
  - sushirain 13y ago
    I agree. This is the most important point in this discussion.
- yohanatan 13y ago
  The whole concept of fizz buzz for an in-person whiteboard interview is absurd. The type of candidate who would fail that test should have been filtered out way earlier in the process and the type of candidate who hasn't been filtered out by that point (i.e., a 'top candidate') would be extremely insulted. I think the people who ask asinine questions like this haven't done their due diligence going in. They haven't looked at the candidate's online presence (including GitHub) nor even read her resume.
sysop073 13y ago
So is your argument actually that it's not necessary for people to be able to do this? Or is it that it's not nearly in-depth enough. If you're arguing the latter, I'm pretty sure everyone agrees; this was described as his version of fizzbuzz, to weed out people who literally just can't program. If you're arguing the former, that seems insane. Knowing how a TCP/IP network works is great, but if you're incapable of writing code to implement your knowledge, you're not very useful
shasta 13y ago
[sarcasm]Please continue to use this question. It’s a wonderful marker for candidates (like me) who don’t want to work with folks who think questions like that are useful.[/sarcasm] That's a two way street. Asking this question to ward off people who are offended to be asked it sounds like a net win to me.
- jdowner 13y ago
  Completely agree. Also, some of the replies to the original article got me thinking about my own experiences as an interviewee. I realized that those engineers who have interviewed me in the past and did not ask much technically have been amongst the weakest engineers I have worked with. Really nice people, not really good engineers.
Too 13y ago
C'mon, this is not about knowing some algorithm by heart. He clearly describes the specifications and gives a test case. With that information you should be able to "troubleshoot/design/architect/solve" a solution to his problem even if you've never seen it before. This is a fizzbuzz, someone posted a quite sparse C++ solution in 75 LOC above. C++ ! That would be half in python, less than one laptop screens height.

mcguire 13y ago

* One class v1 public class BST { private BST left, right; private Integer value; } "All of the above are valid answers...." Wait, wait, wait. That one can't be empty.

JackFr 13y ago
value==null
- mcguire 13y ago
  Ahh. Good point. Thanks!
deleted 13y ago
[deleted]

shalmanese 13y ago

How many of the candidates you interview start off by writing simple test cases to make sure they've thought of all the edge cases before they dive into coding? Have you noticed any correlation between the test-first people vs develop-first people?

trcollinson 13y ago
I was recently in an interview where the interviewer asked me a rather convoluted and not easily explained algorithm implementation question. It took the interviewer some 10 minutes to explain it. This interviewer was the CTO of this particular, rather success, start-up and had formerly worked at other very large and success companies all over the Bay area. My very first instinct and the thing I started to do was write tests on the board to make sure I understood the requirements. The interviewer stopped me and said "Please, just get to the code, the tests are not important." I tried to explain that the tests are paramount to the success of an implementation because I need to make sure I understand the requirements. However, the interviewer disagreed. I actually told them I was no longer interested in interviewing with their company and excused myself without writing anything further on the board. The funny part is that the next day the CTO in question called and offered me a very nice position (I respectfully declined after a discussion of my concerns). So, two points. One, not all interviewers care about tests, which is sad. Two, the original post states, "you don’t get to choose how you get interviewed". This is false, you can certainly choose how you will be interviewed, as long as you are ok with the consequences of that decision.

angersock 13y ago

The thing I particularly like about this is that the problem spec is very rigid and clear: no generic solutions (ints only), don't worry about balancing, don't worry about visibility, make it work, and then they give example usage of the API. It's really easy to screw up a one-page toy problem spec: I've done that myself, and got many replies that failed to either follow the spec or failed to identify ambiguities in it. Having a simple problem as a baseline is really helpful. That said, what I don't like about this is that it doesn't really test the candidate's ability to reason about systems or architectural things--then again, as a better "fizzbuzz", this seems to fit perfectly.

lzhou 13y ago

So the old - allocate a massive array, then use 2n+1, 2n+2 for the left/right children wouldn't have flown with you huh?

bratfarrar 13y ago
People will occasionally try that, but my point to them is that they should be writing a general purpose BST, which should also allow degenerate trees. So no, I do try to steer people away from theoretically correct but desperately inefficient approaches.
- lzhou 13y ago
  That's when the flustered interviewee can either fight (patch his solution) or flight (start all over using a class with refs). The most obvious patch is to use a large hashmap instead of a massive array. Still inefficient, but no longer that desperate (and actually has some added benefits).
- dalke 13y ago
  To be fair, it's "desperately inefficient" only in the face of unbalanced trees, no? Which mostly only happens for unrealistic scenarios. As stated, the problem assumes that time lookup isn't important, even though someone who wants a BST almost certainly chose it to get faster than linear lookup along with fast insert/delete operations and ordered searches. (Otherwise, why not use a hash table?) A self-balancing tree gives that additional guarantee, and in that case an array-based data storage won't be "desperately inefficient". Indeed I suspect an array will be competitive or even better than an object based version, where each object has its own pointer overhead and associated memory fragmentation. At the very least, the early AVL work in the 1960s used a tape for storage, and I suspect they didn't waste all that much tape space. So someone's intuition from real-world use of BSTs might end up giving you a false negative.
  - detrino 13y ago
    If you need memory efficiency you can just use a B-Tree, which also has the advantage of being more cache efficient.

ollysb 13y ago

We do a quick phone call screener and then do some pair programming. We only do half a day of pairing (for which they're paid for) but I find that this is the perfect place to do a stealth interview with the candidate. They feel comfortable because they're in their daily environment (we do it remotely using floobits, so they're sitting at their usual desk with their usual apps etc.). Here you can get a really good conversation going about things that are actually relevant to the job. Anything else just seems like guessing now.

bratfarrar 13y ago

Time for BST code golf - winner does it in the fewest characters!

raverbashing 13y ago
Well, depends on the language It could be funny to test with a trinary or quaternary tree,(then you have 3 or 4 - or n - children) based on a different processing of the value For example, storing complex numbers and the child corresponds to the angle relative to the parent

Jemaclus 13y ago

The "haters" section leaves out one critical reason for not doing something like this that I think is quite relevant. For those of us who have never had to do a BST before (I do not have a degree in CS, though I've been coding professionally for 8 years), expecting us to solve a BST problem in the 10, 15 minutes alotted is not really great. Even if I've never seen it before, the idea that I can solve it in 15 minutes in a high pressure environment is unrealistic. In a real world scenario, if I had to solve this kind of thing, I'd rely on existing works first. I'd google the problem, and I'd see what solutions are out there. For most problems, there's something that can point me in the right direction. For solving a BST issue from scratch in 15 minutes, well.. let's just say the first guy to come up with BSTs probably didn't come up with his solution in 15 minutes. So I would give it my best shot, but if I don't succeed, you shouldn't hold it against me. I disagree with the premise that if I can't solve this, I can't solve novel problems. That's just blatantly incorrect. I solve novel problems every day -- just not on a whiteboard and not in 15 minutes. I would much much much rather see a real-world problem. Something you've actually run into. For instance, in my line of work, I deal a lot with addresses. One of the issues that I've had to solve in the past is parsing addresses. If I give you a string of "123 Main St, Boston, MA 02123", how do you break that up into street, city, state, zip? That's something I've actually had to solve. It's something that anyone with critical thinking skills can take a decent shot at in 15 minutes. A binary search algorithm? I got a question like this one time, and I floundered because I got 90% of the way there, but I couldn't figure out how to solve one of those edge cases. The guy basically ended the interview right there, but I asked for the solution. When he gave it to me, it was something straight out of an academic textbook. I said, "Oh, you guys must use binary trees a lot." And he laughed and said, "No, never. It's low-level stuff for databases." And I just sat there, dumbstruck. Why would you give me a problem that you've never had to solve yourself? I dunno. I just disagree with the premise of the article. I think there are far better questions to ask. Problem solving in general is required -- solving academic exercises much less so.

bad_user 13y ago
As an former interviewer, I also preferred to give algorithmic problems to candidates, though I avoid the kind of problems that involve practice, such as graph stuff or dynamic programming. The rationale being that developers need to know the basics of CS, since we were into algorithms. With the mention that I didn't want to see perfect solutions, being much more interested in how the candidate approaches the problem. But yes, I agree - my only problem with real world stuff is that it is hard to come up with a set of 15 mins problems that involve analytical thinking.

gameguy43 13y ago

I dig this problem. One thing it doesn't touch, though, is the importance of using descriptive variable names to organize your thinking (in this case the var names are kind of a given--left, right, node..."current" is the only one someone might find a useless name for). I've found the candidate's ability to choose descriptive variable names is strongly correlated with general organization and clarity of their thinking.

codr 13y ago

Indeed time to retired it - it's really not a creative question, nor will show how creative the candidate is. While I'm all for testing the bounds of a candidate's CS knowledge, try to come up with an original problem that nobody has asked before! You can get a lot of mileage out of doing stuff like reversing numbers (without using strings), etc.

detrino 13y ago

A quick C++ implementation: http://ideone.com/hGtbts http://ideone.com/hGtbts While this was easy to do in ~10 minutes using gedit/clang/valgrind, I have to wonder how well I would have done had I been forced to use a whiteboard. > Even if you haven’t studied or used BSTs in a while – even if I have to explain them to you on the spot – you should be able to complete the problem without much difficulty. I agree with this statement if you have access to a minimal development environment, but not on a whiteboard, which is entirely unforgiving to making any changes. In the end, this serves only to select candidates who know exactly how to solve this problem beforehand.

danbruc 13y ago

I put this first, because that is why I started writing this comment. I have to disagree with some of judgments made by the author. The first one is debatable but usually you don't want duplicates in your binary search tree - I consider all the example implementations broken. But he really lost me when he started talking about the coding style. The given example is not perfect but I consider it better then most of the other examples when it comes to coding style - if and else without braces, if with break but without else. Everywhere. It is a lot of religion, it is a lot of personal preferences, but all the more it seems really wrong to judge more on personal preferences of style than on correctness and other hard facts. And here what should have come first. I think this is a relative unrealistic task because writing your own data structures is quite a rare task for most programming jobs. Nonetheless it is a very basic task and every professional developer should be able to get this right within 15 to 30 minutes.

mrfusion 13y ago

I'll bet he ends up with a lot of employees who are great at writing BST's. Are they great at solving the problems his business faces? Who knows?

hackdays 13y ago

As daunting and necessary interviews and phone screens are , there is one thing that's surprisingly not used enoughto vet a candidate - Referrals. At http://referralhire.com http://referralhire.com we are adding that important data point to your hiring process. To have a person referred by an accomplished developer is extremely valuable and is something that cannot be judged in an interview. It will also help avoid a lot of false negatives! Very talented developers we have met were rejected at multiple interviews just because of the interview day performance. All companies need to start using this more in their candidate search and decision making process.

collyw 13y ago
I like the idea, but how does it not fail in the same way linked in does - when your mother endorses your SQL skills?

spinlock 13y ago

My problem with whiteboarding anything other than pseudo code is that I'm pretty dyslexic and I've spent years learning syntax at the keyboard. That learning does not translate to the whiteboard. To give an example of how much the presentation of problems matters to me, the first time I took the GREs I got a 340 on the verbal. The problem was that I had practiced out of a book not on a computer. The second time I to the GREs I scored a 740 on the verbal because I spent the time to learn how to take the test. Anyway, I don't have the time to learn how to program on the whiteboard. I also don't think it's a valid signal of how well I can program at a computer.

theboss 13y ago

>Top candidates If they are top candidates, why are you asking them to solve a problem that might as well be copied directly from a college text book? >my version of fizzbuzz How many times do you write a for/while loop a day when programming. A lot. How many times do you implement a full BST a day. I'd guess about 0.

agentultra 13y ago

Isn't the optimal strategy for an interviewee to game the system? There are groups like http://codingforinterviews.com http://codingforinterviews.com where you can find a set of classic and popular problems to memorize. Interview in rounds and refine your problem set. As interviewers... is this what you're looking for? What are the selection criteria after this then?

deleted 13y ago
[deleted]

kstenerud 13y ago

Generally, when it comes to coding, I'll ask the interviewer if we can just do it on my laptop in a real development environment. Nobody actually codes on a whiteboard, so why should it happen in an interview? I want to play with the code, reason about it, refactor it as my understanding of the problem space expands. I can't do that on a whiteboard.

collyw 13y ago
On the other hand, I think I write better code when I sit down and think about it first. Sketch some ideas. Sometimes implementing bit helps change your way of thinking, as you see problems that you didn't before.

namelezz 13y ago

Dude, you lost me when you consider "Switching the left and right sides" a critical mistake. It's an interview. Candidates can be very stressful and make mistakes easily. Also you are interviewing a human not a machine.

gumby 13y ago

I find the responses so far on HN quite interesting. The author of the article is pretty clear, but still, people question the appropriateness or whether it's passive aggressive. What you want to know from a programming question is: - have you actually written code and can you still do so? - do you have a "feel" for how the code works or are you a cut 'n paste person? - do you know "enough" (the last is elusive: it's like being able to calculate in your head: sure, I use a calculator, but I can tell when I see the result if I've made a key press error along the way because I have a rough idea of what the answer will look like.). And this is another reason not to sweat the small stuff. The odd lost semicolon is no big deal; not knowing the difference between recursion and iteration is. "Real" problem are rarely bite sized. Plus the interviewee won't have enough context to know which parts of the problem statement are significant and which aren't. Much better to provide something simple and abstract that only takes a couple of lines to answer. Another good starter question is "make a deck of cards however you like and shuffle it." An amazing number of people feel this is under constrained and ask for more definition. I don't care about the implementation of the deck (integers mod 13 for face and divided by 4 for suit work OK, or you could define an object). It's surprisingly common that people just make a complicated copy or inverse than an actual shuffle. One guy reversed the deck and when I gently asked if it was actually random laughed out loud, smacked himself on the forehead, rubbed out a bit of brain damage on the whiteboard and put a random() in. He turned out to be an awesome programmer. No way did I want him to feel bad about making a silly mistake. He knew how to solve that (and a couple of other problems). A little problem like this supplies plenty to talk about (what if we did this? How would you deal with this scaling up) to show the interviewee how we think about things and vice versa. As for the address problem: it is basically a huge set of special cases. That's a different kind of problem and not actually a programming question.

collyw 13y ago

Why would you implement a binary search tree in any of those languages. There are likely to be well written, tested, optimized libraries out there for that sort of thing.

GFK_of_xmaspast 13y ago
Thanks for reading!