10 ms·

The Worst Programming Interview Question

113 points by talhof8 12y ago

raldi 12y ago
What if you gave the answer immediately after asking the question and then judged the candidate by how much their face lit up?
- potatolicious 12y ago
  But why? One puzzling thing about our industry is our obsession with finding suitable proxy indicators for programming ability. But we can test for programming ability directly.
  - raldi 12y ago
    Oh, I agree. I just thought it was interesting to think that a bad question might be improved by giving its answer away.
mankyd 12y ago
This question has an "a-ha" moment, but it is not required to solve the problem adequately. I wholeheartedly disagree with this statement: > People like to pose puzzlers to “see how people think” but that’s nonsense in the case of puzzler questions. You can’t reason your way through a puzzler, that’s why it’s a puzzler There are plenty of ways to solve this problem. They're not all optimal, of course, but you don't ask these questions to get the optimal solution, you ask these questions to understand how the person reasons about them. This more falls on the interviewer than the candidate. It's upon the interviewer to encourage a dialogue about the problem and talk aloud through it. Yes, some qualified candidates are bad at this. I'm sorry to hear that, but it can be practiced. Being good at interviewing can be learned. It's not terribly difficult. My number one pro-tip? Never do this: > If you don’t have the a-ha moment in the interview, you won’t get it, and a good chunk of your brain will be devoted to thinking “oh shit I’m blowing this interview” rather than focusing on the question at hand. Never think that you're blowing the interview. I got a job at Google and I know for a fact that I didn't get the optimal solution to some of my questions. It's not about the solution, it's about the process.
- mathattack 12y ago
  Google and others have largely given up on these types of brain teasers. http://www.nytimes.com/2013/06/20/business/in-head-hunting-big-data-may-not-be-such-a-big-deal.html http://www.nytimes.com/2013/06/20/business/in-head-hunting-b...
  - mankyd 12y ago
    This is... debatable. It depends on what you consider a puzzler. I will tell you that I was asked questions similar to the one referenced in the parent article. It is a programming question that can be answered precisely with code, and that code can then be analyzed for time and memory considerations. I was not asked silly questions like "how many golf balls could you fit in a school bus" or "how do you move a mountain 3 feet to the side". These are the types of questions he explicitly references in the article. edit: I will also add that there are differences between eng and non-eng interviews. I'm not familiar with the non-eng process really.
    - mathattack 12y ago
      I used to have a math puzzler that I'd ask. Almost nobody got it right. One guy got close, and we ultimately hired him. He asked for the full answer, and I gave it to him. He told me I was wrong. I pointed out that I had asked this question at least 50 times, and knew it in and out, and that he should reconsider. Then he sent me a spreadsheet proving that I was wrong. Whoops.
      - zheshishei 12y ago
        So, if the guy "got close", but then proved that you were wrong, was his answer was actually right, but that you thought it was wrong?
        mathattack 12y ago
        Yes. Much to my chagrin. But I was glad we hired him because he was smart and thorough, and only rubbed my nose in it once or twice.
bitL 12y ago
Come on, this is like the easiest problem you could have gotten during Google's, Microsoft's or Facebook's phone screening interview. If you can't figure it out in 10 minutes, then you should forget about working there. I miss the old times when these puzzlers were asked during interviews. My theory is that you can recognize an excellent place of work with a great future when they actually ask you these sorts of questions as it attracts certain kind of excellent and creative people. I could see the "interestingness" of companies being shifted as they abandoned these questions, first Microsoft (picked up by Google), then Google (picked up by Facebook), like they were passing some kind of "greatness" token (MS->G->FB). I was told at Google that I solved two problems like this during an interview that nobody solved before me in 15 minutes (one led to a super complicated math formula and dynamic programming, the other I solved optimally but differently to their solution, and provided an optimality proof based on discrete calculus). It was the greatest and most challenging interview in my life. I miss it, all interviews nowadays are just boring as hell :-/
- DarkTree 12y ago
  cool.
- eddd 12y ago
  What did you exactly prove during this interview? That you know to write readable code? That you are know to code in team? Did you write any test case during this inteview? Any docs?
  - bitL 12y ago
    I proved that my solution had optimal time complexity using discrete calculus, for a highly non-trivial problem that requires to come up with unexpected ideas under huge stress. They saw my own open-space real-time software 3D rendering engine with texturing and shading (C++/Asm) at SourceForge already, they saw my own SQL server (many students at my first university were ripping it off for their own class projects in the next years so it was a mistake to make it open) as well as other projects I did prior to that interview so they were familiar with my coding style and quality. Also, before that while working at SUN I did some work on a test suite with 10,000s of tests, many of them for SUN's own compliance with one of their standards, making sure it was executing on a distributed cluster every day for every branch they had in order to ship the best quality to customers. Many of these tests were for obscure cluster failure cases using custom bleeding-edge test frameworks. So the answer is no, I didn't write any test at Google interview, it wasn't required. How can you prove you can code in a team during an one-on-one interview? At best you can give hints that you are willing to discuss stuff and change your progress on input from the interviewer and explore if there is any sort of chemistry between you two, which is about all you can do. I really hate this kind of nitpicking, averaging everyone to a "normal" level, trying to find something wrong in someone because she or he goes against (IMO) lazy typical stereotype. Enjoy your mediocrity! Are there still hackers on HN?
Kenji 12y ago
My solution would have been: Simply have a wrapper around the linked list that keeps count of the elements (+1 for insert, -1 for delete, initialized with 0). Traverse the list. If your traversal takes more steps than there are elements, you can stop it and conclude there's a cycle. I wonder how the interviewer would value this answer...
- mankyd 12y ago
  If I was interviewing you, I would point out that you're redefined the question: the question gives you a standard linked list, and you state that you want a wrapper-api around it. I would then ask you to try to find a solution that works for a bare bones linked list. I would make a note that you did find one type of solution, of course. edit: I would probably also ask why you created an api that even allows cycles, being as that you are defining control over adding and removing elements. Further, if you stated that your api explicitly allows cycles, I would ask why you don't simply mark them at insertion time and flag them, making the "detection" algorithm O(1).
- anon4 12y ago
  As others noted you can't know how many elements there are supposed to be in the list. But you can guesstimate. 1. Take a guess about how much memory the program has allocated so far. If you can't, go with 2^48 = 281474976710656 bytes - the maximum you can do on a 64bit pc today. 2. Divide by the minimum size of a list entry. 3. Traverse the list until the end or until you traverse more elements than there ever could be. In general though, as noted, you'll know if you're making a list that could possibly contain cycles due to exposing an interface that allows the creation of cycles. In that case, given that you want to be able to efficiently detect cycles, you'd make a special linked list implementation that does keep internal count of its size.
- probably_wrong 12y ago
  If you argued that many programming languages already provide list.size() or equivalent (more so if I told you "in a language of your choice" before), I'd swallow my pride and accept it. Then I'd suggest you try the other way, but it's a perfectly good answer.
deleted 12y ago
[deleted]
aleyan 12y ago
Has anyone actually answered this question on the spot without help and without knowing it? Probably not without help, but then how do we judge the amount help given to an interviewer? I have been going through my own crises of interview question. My go to question for interviews which I have asked of about half a dozen candidates so far, wasn't completely flubbed only once. The only people I know who gave the good answers besides myself were my boss and our intern from MIT during mock interviews. I have been grading the candidates not on being able to write the solution in code like I intended, but on being able to come up independently with bits needed for the solutions. This has been quite unsatisfactory. How do I know if my question is too hard, or if something else is wrong, like prescreening of candidates?
- phamilton 12y ago
  I have. I had help, but the process was just like any other problem. State constraints. Look for a violation of constraints. Sort of like proof by contradiction. I can't remember the actual hints. I blitzed through 3 or 4 naive solutions first. My favorite was using tagged pointers to mark visited nodes. Eventually through a combination of hints and exploration I got to the idea of using two cursors. At that point it was a simple constraint about which cursor would be in front of the other and if there was a violation of that constraint it could only be because of a cycle. It made for a good interview, but there was good chemistry between myself and my interviewer. Any question would have worked in reality.
- alain94040 12y ago
  Yes, I did figure it out. Actually, the answer I came up with was slightly different: it was pretty clear that I had to move the first pointer to get inside the cycle. Once I was inside, I thought the second pointer would need to move a lot to find the cycle, rather than just going two hops. So I proposed to advance the first pointer by n, and the second one by exp(n). Maybe it would go faster, who knows. By the way, this was the question at my first interview ever, so I do remember it quite well. PS: I interviewed many candidates since, and I would never ask such a question.
- anon4 12y ago
  Can you tell us what that question is? Not details, but the general idea. Me, I'd ask them this: 1. Write a function that takes a string of hex digits and converts them to a long (or equivalent in the language). Keep code minimal. 2. The opposite. Keep code minimal. 3. Write a function that reverses a UTF-8 encoded string (provide a good reference to the UTF-8 format), keeping combining characters in the reversed string in the same order they were in the original. I.e. aüç should be çüa, not ¸c¨ua. Assume the string of bytes is a proper utf-8 string, that only combining characters have to be order-preserved and that the only combining characters are the ones with unicode character codes in these ranges: (give them some standard ranges). Keep code minimal. Anybody who can do these three things should be able to learn most any other tech stack you throw at them. If on the other hand you're looking for people with specific expertise with a given branch of computer science, then you need a different set of tests. The central question is - do you need a developer or a mathematician specialising in discrete mathematics. Those are two different sets of people, though they tend to overlap.
yodsanklai 12y ago
I disagree with the author that this is a "puzzle question" that requires an "a-ha" moment. Quite the opposite, it is an easily solvable algorithmic question (maybe with a little guidance after the candidate suggest suboptimal solution). Also, the good thing from the candidate point of view is that it is the sort of questions you can prepare for.
- sergiotapia 12y ago
  >sort of questions you can prepare for. The point is why do you need to prepare for and regurgitate these silly answers that you will almost assuredly never ever ever use in your day to day job?
  - eweise 12y ago
    +1 to that. Most programming jobs are about integrating a bunch of different technologies together to solve a business problem. In 20 years I've never written a linked-list or sorting algorithm for work yet interviews are increasingly narrowly scoped to algorithm questions. I've found that these questions are usually asked by young people because they are fresh out of school and have been led to believe that knowledge of algorithms is the most important consideration. Give them a decade of creating products based on css, html, node.js, nosql, yessql, etc and they will come to realize that programming is more about understanding what a customer needs and finding the most efficient way of delivering a solution. Ability to work with other, lead a team, write clearly, explain to customers the tradeoffs and costs of different solutions are actually way more important than knowing how to find a cycle in a linked list.
    - twistedpair 12y ago
      But how do I test all of that in 30min or less? Do I have to actually get to know the person, their work history and their strengths? Does that mean I have to read the resume before I enter the room?
- Marazan 12y ago
  Did you miss the part where it took 12 years to come up with this solution?
dfox 12y ago
The article seems to imply that the turtle and hare algorithm is only valid solution for this problem, which is certainly not the case. This problem can be also solved by building big set of already seen list nodes or adding bit to list nodes themselves. Whis is both something that everybody should be able to come up with and implement. I think that this is in fact quite good interview question because while there is one non-obvious perfect answer, it also has some sub-optimal solutions that are pretty obvious and simple to implement.
- owenmarshall 12y ago
  Yeah - the article built it up and built it up, but when the question finally came up my thought was "wait, that's it?!" If the interviewer asked the question and rejected anyone that didn't immediately answer with the tortoise/hare approach that's the fault of the interviewer, not the question.
- potatolicious 12y ago
  You're right, though I think he's talking about the weird type of interviewer who expects candidates to know obscure, non-intuitive optimal solutions to these problems. I once met an interviewer who liked to use the "reverse a string" question, except he was expecting candidates to know the XOR trick. Suffice to say few, if anyone, ever got past his "filter". Primadonna interviewers who use interviews as ego-strokes are a problem in our industry. It's where the stupid "why are manhole covers round" questions came from, and it's where these hyper-optimized algorithms questions come from.
- skywhopper 12y ago
  This was my first thought about how to solve it. It provably works in finite time. This ought to be a satisfactory answer in an interview, particularly if the candidate points out that it's unlikely to be The Optimal Solution. After which point, the appropriate follow-up question from the interviewers would be to ask what the time complexity of the algorithm would be in the worst case.
- 16bytes 12y ago
  Agree. The anti-pattern here is expecting a specific answer for a question. The goal should be, "how does this candidate think through problems?" If they arrive at a logic solution and can critique it, then I would consider the question completed. Some questions are better than others here, specifically ones that have many correct implementations and varying levels of optimal-ness. I'm a big fan of asking for Fibonacci implementations, for instance. Since this question can have different correct implementations, then I would not consider it a bad question to ask. It's upon the interviewer to be open to different answers, evaluate them fairly and ask smart follow-up questions. "Ok, so what's the complexity of your answer? Do you think it's possible to do better?" or "Compare your answer with this implementation".
skywhopper 12y ago
I think an unreasonable question (ie, of a practical situation in which no one will ever find themselves) deserves an equally unreasonable answer: Write a program that starts at the head of the list and in a loop follows the "next" pointer on the current list entry, halting when the pointer is null. Run the program and wait. If the program never ends, there's a cycle in the list.
- csbrooks 12y ago
  Then just come up with an algorithm that proves if the program will halt or not. Easy peasy.
- gohrt 12y ago
  I have had this problem in real life. I had a graph database, and I needed to find the end of a path in the graph. If the the path looped back on itself, my program would not terminate.
  - hugofirth 12y ago
    This occurred to me as well: the graph data model is one of the few areas in which you might practically need to address this problem. Again, however, a lot of these issues specific to the graph data model are open research questions and not really appropriate to an engineering interview.
  - option_greek 12y ago
    Finding the loop in a graph is a much more valid scenario and any candidate aware of traversal algorithms will have a much better chance of dealing with it than finding loop in a LL.
gabemart 12y ago
> In this case, the generally “correct” answer is a tortoise-and-hare algorithm, where you have two pointers at the head of your linked list, one traverses the list two nodes at a time, and one traverses the list one node at a time; if ever the pointers point to the same node, you have a cycle somewhere. I'm an extreme novice to programming. I don't fully understand this. 1) How can you traverse a linked list two nodes at a time? Is this just short-hand for "go to the next node, then go to the node after that, and call that one operation"? 2) If you can detect when two pointers are pointing to the same address, couldn't you solve the problem by traversing the list one node at a time, storing the addresses of each node in an array, and checking to see if the array contains any duplicate values at intervals?
- nayefc 12y ago
  1) One loop, two pointers. Each iteration increments each pointer by a different margin. 2) Yes you can do this but not in all languages.
- mankyd 12y ago
  The "tortoise" pointer does a standard traversal - one at a time. The "hare" pointer goes from one node to the next _and then the next_ - i.e. two at a time. If the hare hits a null node, there's no loop. If the hare hits a cycle, it will eventually run back into the tortoise and there's a loop.
  - pessimizer 12y ago
    I must have learned this algorithm in school, but completely forgot it. My naive implementation was 2), but this is the first explanation on this page that made Floyd’s cycle-finding algorithm click for me:) Now I can't unknow it - thanks for the clarity and concision!
- aquamongoose 12y ago
  With regards to (2), this is one way of solving the problem. However, your solution uses O(n) memory (where n is the size of the linked list), and the tortoise-and-hare algorithm uses only O(1) memory. Here's how it works: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_ha...
patrickmay 12y ago
It's a bad question if you expect a quick, explicit answer. It's somewhat less bad if you're looking to have a conversation about how to solve problems the candidate hasn't seen before. I've used an arguably "puzzle" question that was presented to me in an interview with some success -- the missionaries and cannibals problem. There are three missionaries and three cannibals that you must get across a river. The boat holds only you and one other person. The cannibals on either bank must never outnumber the missionaries on that bank. It's a good question to see if a candidate understands how to apply some basic computer science concepts. It can easily lead to a 30 minute discussion at the white board, with no need to get working code. My favorite question is completely different. "What do you like best about your favorite programming language and what would you change about it if you could?" Anyone who doesn't see any flaws in their favorite language, particularly if it's Java, gets politely shown the door.
- mwnz 12y ago
  +1 to this. The objective is not to see the person solve the question immediately, but to observe their problem solving process.
- thisone 12y ago
  but now anyone who's watched Fargo (tv) will be able to work it out
- lostcolony 12y ago
  The problem with using this as a meta-question, is that someone who knows the answer may treat it as such. That is, the person who comes to realize the canonical way of solving it may truly be brilliant and having been hinted and helped along the way came up with the solution, or he might have already known it and just played a metagame, assuming that's what you wanted. Basically, you have four possible outcomes: People who have never heard of it, don't come up with the canonical solution. People who have heard of it and just blurt out the answer. People who have never heard of it, but who come to realize it over the course of the interview. People who have heard of it and who play it as a game, working towards it and then suddenly having an epiphany. The first is interesting. The second you hopefully dispense with the question as being useful. The third would be a great hire, but is indistinguishable from the fourth, who you've learned nothing about except they know how to play your interview process. Which may or may not be the criteria you're looking for.
shmerl 12y ago
> With all of those hundreds and hundreds of minds, this problem remained open for 12 years. A very good point. Some people just forget that while solution can look simple when it's already known, actually finding it can be extremely hard and more akin to invention breakthrough. So such question is more similar to asking to prove some difficult theorem really, than to anything else.
prelud 12y ago
I am the guy who asks that question on every interview. You can hate on me now! Let me clarify. I don't expect the candidate to get to the "a-ha" moment at all. I make my expectations very clear upfront so that the other side wouldn't panic. However, I expect to see how the candidate would approach the problem with the right attitude so I could get some insight of his/hers thinking patterns. I personally wouldn’t mind if an interviewer asked me something in the lines of "how would you build a nuclear plant?", although I have no knowledge on the matter.
peaton 12y ago
I completely disagree that this question is irrelevant. I can imagine this exact situation in compiler design where you have dependent types that can't have infinite loops (in pseudo-code where forward declarations are not needed or implied): type a = b type b = a If a program has a structure like this with cyclic dependencies, then the compiler must be aware of this and break. (At least, I can imagine a situation where this could be a desired attribute.)
- sz4kerto 12y ago
  You are mixing up cyclical linked lists with loops in a graph. The reason why the question is bad stems from the fact that it's specifically about linked lists.
  - peaton 12y ago
    I could definitely be mistaken, but I don't see a difference between a linked list and a graph. They are two ways to represent the same thing. That being said, if he asked me to find cycles in a linked list, I might determine the adjacency matrix and check for loops: http://stackoverflow.com/questions/16436165/detecting-cycles-in-an-adjacency-matrix http://stackoverflow.com/questions/16436165/detecting-cycles... This is at least very easy to reason about. However, if you are still right my thought process is just very wrong.
    - dllthomas 12y ago
      "I could definitely be mistaken, but I don't see a difference between a linked list and a graph." A linked list is a particular type of DAG (or at least DG). The relevant distinction between linked list and the general case is that a linked list restricts nodes to (zero or) one outbound edge. This is relevant to the problem at hand, because you only have one tortoise and one hare and so they can only follow one path.
      - peaton 12y ago
        Ok, that was poorly worded. What I mean is that a linked list can be thought of as a restrictive graph. I'm just saying I'd prefer to think of it as a graph. I could still be wrong. Is that kosher?
general_failure 12y ago
Once in an interview I was asked to implement a synchronization mechanism between processes using shared memory. It turns out this is the petersons algorithm. I mean if I could solve this, I would be Peterson :) heck, even smarter because I would do it in 20 mins.
JonnieCache 12y ago
Hypothetically, if when asked this question in an interview I were to reply "I'd look up the canonical solution on the internet and just implement that. I have better things to keep in my brain than linked-list algorithms, and there's no way I'm going to beat decades of phd work off the top of my head", what would happen? Obviously it depends on the job I was interviewing for. Let's assume I'm not angling for a position as lead on a distributed load balancing layer or something. I suppose if they're looking to see my problem solving workflow then I'd look like kindof a dick. But then, as the article points out, so would they.
- _mulder_ 12y ago
  A great response would be to just say "hold on", whip out your phone and Google the answer, show it to them and finish up with "How long did it take your other candidates to complete that task? next..." Point being, you're demonstrating initiative and, that old cliche, thinking outside the box. Think Will Smith in Men In Black. Some interviewers might be impressed with your lateral thinking, others might be annoyed at your attempt to be a 'smart ass' and avoid the intention of the question. But that's always the problem with these type of interview questions, it depends so much on the expectations of the interviewer.
  - JonnieCache 12y ago
    I think it would be funnier to silently transcribe the code from the phone to the whiteboard, and then just sit back down and look at them while you wait for a response.
    - jiggy2011 12y ago
      "oh, you can use google. Surely none of the other candidates could think of that"
      - TheOtherHobbes 12y ago
        The professionals use StackOverflow.
davidjeet 12y ago
Had that exact question given to me before, but it was in the form of a closed book "pre-screening" written test. I simply put down my pen, walked out of the room and told the recruiter if this company was hiring based on these type of questions I would be a terrible fit :)
- twistedpair 12y ago
  They were likely hiring to fill a PHP dev roll writing CRUD web forms too, right? I've been places with tough interviews and incompetent developers and the opposite as well. One does not necessarily correlate with the other.
sjs1234 12y ago
I had this in an interview (back '96). Came up with a linear time constant space solution: create a new node, push it on the front, reverse the list, check if the 1st node is the same one you pushed, if so it has a loop, otherwise it doesn't. The downside is you need to reverse again to get the original list. Another answer is to mark nodes using the low bits of the next pointer. Also linear time, but also requiring clean up. I can see how not knowing c would cause people to think this question was somewhat unfair, but I didn't see it that way.
- herge 12y ago
  How would you reverse a linked list with a loop?
  - nmrm 12y ago
    If your list is laid-out a contiguously in memory as structs with both next and prev ptrs, you can visit each member using ptr arith and switch the values without actually walking the list using next and prev. Ditto if there's an underlying data-structure involved such as an array.
    - herge 12y ago
      How could you have a linked list with a loop in contiguous memory? Or in an array?
      - dllthomas 12y ago
        You allocate an array of objects that contain pointers, then link them together. It does not have all of the typical benefits of a linked list (in particular, there's a hard max size and may require a fixed size, depending on just what you're doing to it here) but it does allow O(1) reordering elements for a list-order traversal, while also allowing a linear traversal through memory.
        herge 12y ago
azov 12y ago
I'm no fan of this particular interview question, but the article takes it too far. You can figure out tortoise-and-hare algorithm by reasoning (I'm pretty sure I did the first time I've seen the problem - although not in an interview setting). The key is to recognize that there's a very limited number of things you can do given all the constraints: moving pointers is pretty much the only tool you have. If it indeed took 12 years for the algorithm to appear, it's likely because finding loops in a linked list isn't a very common problem, not because the algorithm itself is that hard.
- peaton 12y ago
  Nor is the 12 years thing particularly good reasoning... By that thought process, it took humans hundreds/thousands/millions of years to develop a compiler, so how can I be expected to develop one over the course of 4 years in college? Or even over the course of my life?
  - csallen 12y ago
    Not exactly a valid analogy, because his start date isn't "the beginning of human history", rather it's the development of the linked list data structure, which is the first point at which humanity possessed sufficient knowledge and tools to figure out the cycle-detection algorithm. Given that we didn't have the knowledge or tools necessary to make a compiler hundreds/thousands/millions of years ago, you'd have to bump up your start date considerably.
    - peaton 12y ago
      Sure, I stretched that too far. But hopefully the point is made. Then should we expect no students (or anyone) to be able to build a compiler (or os kernel) in any amount of time given the internet and whatnot? While I may be articulating this poorly, I think my fundamental issue with his point is solid.
  - CocaKoala 12y ago
    Because over the course of 4 years in college you're provided with resources that explicitly teach you how to develop a compiler, a scenario which is entirely different from what happens in an interview.
option_greek 12y ago
I don't want to complain but one of the major culprits who conducts these kinds of interviews is Amazon. After going through their interview process, I'm of the opinion that they basically want you to memorize careercup, geeksforgeeks and leedcode and just spit it out in chunks at appropriate times during the interview.
ssw1n 12y ago
If I do not know any better, the first thought that would come to my mind would be: "Wow, this company has really messed-up code base, and people here cannot even get linked-list done right. Do I really want to work here?"
S4M 12y ago
The page is down, so here is the cached version: http://webcache.googleusercontent.com/search?q=cache:rwL5dDEDvTsJ:www.nomachetejuggling.com/2014/06/24/the-worst-programming-interview-question/+&cd=4&hl=en&ct=clnk&gl=uk http://webcache.googleusercontent.com/search?q=cache:rwL5dDE...
ollysb 12y ago
After a 10 minute phone screener I now rely on a paid pair-programming session to identify good candidates. This is what you're going to hire them to do so why waste your time asking questions that at best form a poor approximation of their skills?
dualogy 12y ago
Timely yet on-topic ;) https://twitter.com/tom_forsyth/status/482337551718440962 https://twitter.com/tom_forsyth/status/482337551718440962
- justinvh 12y ago
  Tom Forsyth listed one of the reasons--when a storage is explicitly expressed. The other two that I can think of are for external linkage and non-constant expressions on the rhs. In the end, you really don't know without some introspection. It's up to the compiler. External linkage is one that will force storage, but in general const will require internal linkage and fold expressions accordingly (at least for primitives). Edit: I would never expect anyone to actually remember or need to know that for an interview. It would be definitely something you would re-discover/discover because you had to run into it.
jameshart 12y ago
Disagree that this problem never arises if you're not implementing a linked list data structure. Here's a file a customer sent you that describes their organizational hierarchy: ID Name Manager 1 Alice 4 2 Bob 1 3 Charlie 8 4 Dave - 5 Elise 3 6 Fred 2 7 Gemma 1 8 Henry 5 Is this a valid hierarchical tree? Okay, it's not exactly the same problem, but it's certainly similar...
- phaedrus 12y ago
  Technically in the context of an org hierarchy that would be detecting cycles in a directed graph, not a linked list cycle. I don't think the algorithm to detect cycles in a linked list applies to general graph problems, and the problem is much harder for graph cycles.
  - jameshart 12y ago
    It's not a generic directed graph either, though - each node only has one outbound link. The sequence of parents for any given node is a linked list, and a cycle in that list is invalid. You certainly don't need to run tortoise and hare for every node path looking for cycles. There are other approaches, clearly - reachability analysis starting from each root node, for example. But if I were to ask you to write a routine to find the root node for a given node based on that data, then ask you to guard that routine against finding yourself in an infinite loop or stack overflow, tortoise and hare would be a legitimate answer. Just trying to make it clear that just because the question asks about linked lists, doesn't mean it's always about abstract data structures.
rgawdzik 12y ago
Uh we did this in our first year CS curriculum...you are telling me your interview candidates can't even do what a first year CS freshmen can?
- nmrm 12y ago
  Are you referring to tortoise-hare algorithm? I refuse to believe CS freshmen regularly come up with this on their own. Maybe a few percent, everyone else is googling or relying on huge hints from the lecturer. If you were referring to a more trivial algorithm (e.g. linear space), I think you misinterpreted what the interviewer was expecting and would not have gotten the job. It's also worth noting -- esp if you're referring to the TH algorithm -- that CS curricula are not standardized and that there are probably dozens of "clever trick" algorithms you haven't seen and couldn't come up with on the spot (e.g. can you initialize an array in constant time?), but someone else thinks is trivial because they happened to see it in a lecture/read it online.
joesmo 12y ago
What all algorithm and idiotic interview questions (like moving Mt. Fiji) are great for is the interviewee himself, not the interviewer. They are a huge red-light indicator that there is something wrong with the engineering culture and department at the company you're interviewing. While there are exceptions, in my experience, there is such a direct correlation between the two, that questions like this have led me to walking out of interviews (politely of course). Why continue if you know you won't take that horrible position? Obviously, if you're hired to write algorithms, then it might be a different story, but most programmers are simply not writing new algorithms. Ever.
- pekk 12y ago
  Can you detail a little the kinds of things you associate with stupid questions that make you want to walk out?
- jiggy2011 12y ago
  Isn't writing algorithms almost the definition of programming?
  - nmrm 12y ago
    I think "coming up with interesting algorithms" was the intended meaning. In which case, no, everyday programming is mostly not about designing algorithms. Otherwise, programmers would spend most of their time with journals and books, with a few days of programming each month.
    - jiggy2011 12y ago
      Interesting is fairly subjective but ultimately you are designing processes to solve problems. If you cannot demonstrate ability to solve a simple, well trodden problem how will you be able to solve a new one?
      - nmrm 12y ago
        > Interesting is fairly subjective Interesting is a social construction. As such, I would define interesting as worthy of publication in a first or second-tier conference at some point in the history of the field. > If you cannot demonstrate ability to solve a simple, well trodden problem how will you be able to solve a new one? 0. I've seen many well-respected researchers who have solved truly interesting, new-to-humanity problems stumble on well-known problems others consider easy and/or fundamental. In fact, this is probably true for every single researcher. And doubly so for practitioners. One person's fundamental technique is another's blind spot. 1. Simple != easy to come up with. Often exactly the opposite! Take the TH algorithm as an example. It's a very simple algorithm. Small. Simple. Optimal. Awesome. Not trivial to discover, however. 2. Well-trodden -> unless the algorithm is absolutely fundamental and taught everywhere (e.g. sorting), you've given up on testing problem solving skills. You're just testing whether the person's intro/DS/algo professor covered this particular algorithm (and maybe their memory). Or, more likely, rather their random interview studying happened to hit your pet problem. Since curriculum is not anywhere close to uniform in CS -- even among top schools -- this is just silly. 3. Simple problems don't always have (simple) solutions. Create a fair voting scheme.
incision 12y ago
I appreciate all the technical discussion of this question in the article and here in the comments, but I think the question is just a symptom. The root issue here is the other interviewer and the apparent interview process. >'In the post-interview pow-wow, all of the engineers who’d interviewed him gave him the thumbs up, except my interview partner except my interview partner, who refused to hire him...' Yes, yes, optimizing for false negatives over false positives is all the rage, but this just sounds broken - wasting the efforts of a full panel only to accept an arbitrary single-question veto. >'..on the grounds that he completely flubbed this question, and "any engineer worth his salt should be able to answer it."' Good engineers don't necessarily make good interviewers. Outright excluding someone based on any single question is just horribly self-satisfied behavior.
- pekk 12y ago
  If you look at the structure of their pow-wow rather than its labeled purpose, you see that its real purpose is not to find a competent engineer but just to build a consensus. E.g. so nobody complains they wouldn't have hired the candidate. It's the same principle which puts multiple men on a firing squad.
  - walshemj 12y ago
    Good way to hire a camel when you need a mustang - your optimising for mediocrity. Everyone does know the joke about a camel being a horse designed by a committee? And should not have the chair/leader of the committee over ruled the outlier anyway.
    - qbrass 12y ago
      You should absolutely get a camel over a mustang. Even though they look like they're designed by committee, camels are an example of form following function. They're very well suited for their environment, and although they're stubborn, make good work animals. A mustang on the other hand, is a feral horse. They're harder to domesticate because they've known freedom, and they've adapted to living in the wild by being smaller and more timid than horses selectively bred for doing work. If you really do need a horse, there are few cases where you need that horse to be a mustang. If someone is hiring you because they think you're a mustang, you better hope they're caught up in the romanticism of cowboy stories instead of them being desperate for cheap labor or meat.
jerrickhoang 12y ago
I don't think interview must entirely be related to the practical world. I mean having a very hard and interesting practical problem is the best of both world but not necessarily the only way to go. If you want to know if the candidate can really build things you can check out his github/resume. I think the 45-min interview is just to determine how smart the candidate is. If you want to determine if someone is smart you put them in a very hard situation (not necessarily a practical one) and see how they reason about it.
blahedo 12y ago
This article raises, sort of incidentally, one of the issues I've noticed recently teaching intro CS. Every CS2 class teaches linked lists, right? (Except for the ones that hit them in CS1, of course.) But: when was the last time you had to roll your own linked list? Once, not that long ago, it was important to cover linked lists (and other data structures) because you'd have to be writing them in order to implement a program of any significant size. Now, though, all the common ones are already implemented for you (and to be honest, we don't even use LinkedList all that often---array-based lists are better in most real use cases). So now their role in (my) CS2 is chiefly as setup. I still need to cover linked lists because they establish concepts that will be important when we get to trees (links) and to more general graphs (cycles and the lack thereof), as well as in operating systems (continuation inodes, memory allocation) and other areas. But implementing an honest-to-god plain-old linked list holding ints or strings or whatever? Who does that anymore?
- belovedeagle 12y ago
  This is a question I see asked all the time and it's absolutely mind-boggling to me that you could ask it. Who do you think writes the linked-list libraries you use? Do you think the libraries just magically appear when someone wishes them up? Do you think we should use the current set of libraries forever, calling them "good enough", and limiting ourselves to current programming languages for all of history? That's what will happen if we no longer teach people to write these things; or else (more realistically) we leave it up to them to make the same mistakes and waste time solving the same problems which were solved decades ago, because no one ever bothered to teach them the answers. Give it a few years and we'll have no one left who can program in anything but javascript; no one left to write the browsers! --- or so I worry when I read HN sometimes.
  - blahedo 12y ago
    You'll notice I'm not suggesting we stop teaching them. But what you describe are specialised applications; my point is that where linked lists were once something that every programmer, large and small, could reliably expect to have to write repeatedly, they're now something that are only directly relevant to, say, library maintainers.
dllthomas 12y ago
'Between 1955 and 1967, the problem of “how do we determine if there is a cycle in a linked list without modifying the list” was an open problem. Meaning, any number of PhD candidates in Mathematics or Computer Science could have written about it as part of their dissertation. With all of those hundreds and hundreds of minds, this problem remained open for 12 years.' Were there any computer science graduate programs between 1955 and 1967? You're not dealing with "hundreds and hundreds of minds", you're dealing with those minds who 1) heard about linked lists, 2) heard about or realized there was a cycle detection problem, and 3) devoted any energy to that problem as opposed to the myriad other problems available to a mathematics or electrical engineering graduate student. All of this has to have happened between 1955 and when the problem was solved in advance of starting to write the paper on it, in advance of publication of the paper in 1967. The paper also presumably included a proof of correctness that isn't being asked for in the interview. The interviewee has the further advantage that they know there is an answer in the space of the constraints the interviewer has drawn. As they suggest less optimal solutions, those constraints get tighter, and the answer gets easier to find. If they have been through an undergraduate computer science course, they probably also have more familiarity with linked lists than most of the people attempting to solve the problem before 1967. None of which is to say that failing to find the answer deserves disqualification - that's probably still unreasonable - but the picture is nowhere near as absurd as presented.
nsxwolf 12y ago
I would love to find the definitive resource for preparing for interviews like this. Besides answers like "just be awesome", is there such a book or page? In the past I've searched for various compendiums of algorithm interview questions and saw the cycle detection one come up. I knew I would never be able to solve such a problem on the spot. This blog post initially put it in perspective for me, that its pretty much a BS academic question that you have to already know the answer to - until I read the comments here, full of totally awesome alpha SV nerds who are saying "I instantly got the optimal answer without any foreknowledge". Now I don't know what to think.
mcguire 12y ago
"...'Write a function that can detect a cycle in a linked list'...You can’t reason your way through [that question]...all you’re doing is testing if someone has seen your particular puzzler before or not." I think I'll take a pass on interview advice from this character.
tzs 12y ago
A not quite serious solution [1]: Let m = size_of_current_process / sizeof(list_node) + 3 Let np = pointer or reference to first node in list while (np != null) if (m-- == 0) return HAS_CYCLE np = np->next return NO_CYCLE [1] this approach might actually be acceptable in some circumstances
jgg 12y ago
My problem with this type of interviewing is not the questions themselves, but when the end products (i.e., code) don't reflect what the company is ostensibly screening for. Ask me all the data structure questions you want, ask me about C and Scheme because Spolsky said so, ask me some irrelevant puzzle or ask me how I would "fix problem A we've been having", when I obviously don't know your application well enough to respond adequately - I don't really care. If your flagship product turns out to be a buggy web application full of SQL injection vulnerabilities, it tells me that you're really just partaking in a sadistic circlejerk. It reminds me of the anecdote about a football coach who took a team, worked them as physically hard as possible in preparation and then proceeded to lose almost every game.

113 points by talhof8 12y ago

raldi 12y ago

What if you gave the answer immediately after asking the question and then judged the candidate by how much their face lit up?

potatolicious 12y ago
But why? One puzzling thing about our industry is our obsession with finding suitable proxy indicators for programming ability. But we can test for programming ability directly.
- raldi 12y ago
  Oh, I agree. I just thought it was interesting to think that a bad question might be improved by giving its answer away.

mankyd 12y ago

This question has an "a-ha" moment, but it is not required to solve the problem adequately. I wholeheartedly disagree with this statement: > People like to pose puzzlers to “see how people think” but that’s nonsense in the case of puzzler questions. You can’t reason your way through a puzzler, that’s why it’s a puzzler There are plenty of ways to solve this problem. They're not all optimal, of course, but you don't ask these questions to get the optimal solution, you ask these questions to understand how the person reasons about them. This more falls on the interviewer than the candidate. It's upon the interviewer to encourage a dialogue about the problem and talk aloud through it. Yes, some qualified candidates are bad at this. I'm sorry to hear that, but it can be practiced. Being good at interviewing can be learned. It's not terribly difficult. My number one pro-tip? Never do this: > If you don’t have the a-ha moment in the interview, you won’t get it, and a good chunk of your brain will be devoted to thinking “oh shit I’m blowing this interview” rather than focusing on the question at hand. Never think that you're blowing the interview. I got a job at Google and I know for a fact that I didn't get the optimal solution to some of my questions. It's not about the solution, it's about the process.

mathattack 12y ago
Google and others have largely given up on these types of brain teasers. http://www.nytimes.com/2013/06/20/business/in-head-hunting-big-data-may-not-be-such-a-big-deal.html http://www.nytimes.com/2013/06/20/business/in-head-hunting-b...
- mankyd 12y ago
  This is... debatable. It depends on what you consider a puzzler. I will tell you that I was asked questions similar to the one referenced in the parent article. It is a programming question that can be answered precisely with code, and that code can then be analyzed for time and memory considerations. I was not asked silly questions like "how many golf balls could you fit in a school bus" or "how do you move a mountain 3 feet to the side". These are the types of questions he explicitly references in the article. edit: I will also add that there are differences between eng and non-eng interviews. I'm not familiar with the non-eng process really.
  - mathattack 12y ago
    I used to have a math puzzler that I'd ask. Almost nobody got it right. One guy got close, and we ultimately hired him. He asked for the full answer, and I gave it to him. He told me I was wrong. I pointed out that I had asked this question at least 50 times, and knew it in and out, and that he should reconsider. Then he sent me a spreadsheet proving that I was wrong. Whoops.
    - zheshishei 12y ago
      So, if the guy "got close", but then proved that you were wrong, was his answer was actually right, but that you thought it was wrong?
      - mathattack 12y ago
        Yes. Much to my chagrin. But I was glad we hired him because he was smart and thorough, and only rubbed my nose in it once or twice.

bitL 12y ago

Come on, this is like the easiest problem you could have gotten during Google's, Microsoft's or Facebook's phone screening interview. If you can't figure it out in 10 minutes, then you should forget about working there. I miss the old times when these puzzlers were asked during interviews. My theory is that you can recognize an excellent place of work with a great future when they actually ask you these sorts of questions as it attracts certain kind of excellent and creative people. I could see the "interestingness" of companies being shifted as they abandoned these questions, first Microsoft (picked up by Google), then Google (picked up by Facebook), like they were passing some kind of "greatness" token (MS->G->FB). I was told at Google that I solved two problems like this during an interview that nobody solved before me in 15 minutes (one led to a super complicated math formula and dynamic programming, the other I solved optimally but differently to their solution, and provided an optimality proof based on discrete calculus). It was the greatest and most challenging interview in my life. I miss it, all interviews nowadays are just boring as hell :-/

DarkTree 12y ago
cool.
eddd 12y ago
What did you exactly prove during this interview? That you know to write readable code? That you are know to code in team? Did you write any test case during this inteview? Any docs?
- bitL 12y ago
  I proved that my solution had optimal time complexity using discrete calculus, for a highly non-trivial problem that requires to come up with unexpected ideas under huge stress. They saw my own open-space real-time software 3D rendering engine with texturing and shading (C++/Asm) at SourceForge already, they saw my own SQL server (many students at my first university were ripping it off for their own class projects in the next years so it was a mistake to make it open) as well as other projects I did prior to that interview so they were familiar with my coding style and quality. Also, before that while working at SUN I did some work on a test suite with 10,000s of tests, many of them for SUN's own compliance with one of their standards, making sure it was executing on a distributed cluster every day for every branch they had in order to ship the best quality to customers. Many of these tests were for obscure cluster failure cases using custom bleeding-edge test frameworks. So the answer is no, I didn't write any test at Google interview, it wasn't required. How can you prove you can code in a team during an one-on-one interview? At best you can give hints that you are willing to discuss stuff and change your progress on input from the interviewer and explore if there is any sort of chemistry between you two, which is about all you can do. I really hate this kind of nitpicking, averaging everyone to a "normal" level, trying to find something wrong in someone because she or he goes against (IMO) lazy typical stereotype. Enjoy your mediocrity! Are there still hackers on HN?

Kenji 12y ago

My solution would have been: Simply have a wrapper around the linked list that keeps count of the elements (+1 for insert, -1 for delete, initialized with 0). Traverse the list. If your traversal takes more steps than there are elements, you can stop it and conclude there's a cycle. I wonder how the interviewer would value this answer...

mankyd 12y ago
If I was interviewing you, I would point out that you're redefined the question: the question gives you a standard linked list, and you state that you want a wrapper-api around it. I would then ask you to try to find a solution that works for a bare bones linked list. I would make a note that you did find one type of solution, of course. edit: I would probably also ask why you created an api that even allows cycles, being as that you are defining control over adding and removing elements. Further, if you stated that your api explicitly allows cycles, I would ask why you don't simply mark them at insertion time and flag them, making the "detection" algorithm O(1).
anon4 12y ago
As others noted you can't know how many elements there are supposed to be in the list. But you can guesstimate. 1. Take a guess about how much memory the program has allocated so far. If you can't, go with 2^48 = 281474976710656 bytes - the maximum you can do on a 64bit pc today. 2. Divide by the minimum size of a list entry. 3. Traverse the list until the end or until you traverse more elements than there ever could be. In general though, as noted, you'll know if you're making a list that could possibly contain cycles due to exposing an interface that allows the creation of cycles. In that case, given that you want to be able to efficiently detect cycles, you'd make a special linked list implementation that does keep internal count of its size.
probably_wrong 12y ago
If you argued that many programming languages already provide list.size() or equivalent (more so if I told you "in a language of your choice" before), I'd swallow my pride and accept it. Then I'd suggest you try the other way, but it's a perfectly good answer.

deleted 12y ago

[deleted]

aleyan 12y ago

Has anyone actually answered this question on the spot without help and without knowing it? Probably not without help, but then how do we judge the amount help given to an interviewer? I have been going through my own crises of interview question. My go to question for interviews which I have asked of about half a dozen candidates so far, wasn't completely flubbed only once. The only people I know who gave the good answers besides myself were my boss and our intern from MIT during mock interviews. I have been grading the candidates not on being able to write the solution in code like I intended, but on being able to come up independently with bits needed for the solutions. This has been quite unsatisfactory. How do I know if my question is too hard, or if something else is wrong, like prescreening of candidates?

phamilton 12y ago
I have. I had help, but the process was just like any other problem. State constraints. Look for a violation of constraints. Sort of like proof by contradiction. I can't remember the actual hints. I blitzed through 3 or 4 naive solutions first. My favorite was using tagged pointers to mark visited nodes. Eventually through a combination of hints and exploration I got to the idea of using two cursors. At that point it was a simple constraint about which cursor would be in front of the other and if there was a violation of that constraint it could only be because of a cycle. It made for a good interview, but there was good chemistry between myself and my interviewer. Any question would have worked in reality.
alain94040 12y ago
Yes, I did figure it out. Actually, the answer I came up with was slightly different: it was pretty clear that I had to move the first pointer to get inside the cycle. Once I was inside, I thought the second pointer would need to move a lot to find the cycle, rather than just going two hops. So I proposed to advance the first pointer by n, and the second one by exp(n). Maybe it would go faster, who knows. By the way, this was the question at my first interview ever, so I do remember it quite well. PS: I interviewed many candidates since, and I would never ask such a question.
anon4 12y ago
Can you tell us what that question is? Not details, but the general idea. Me, I'd ask them this: 1. Write a function that takes a string of hex digits and converts them to a long (or equivalent in the language). Keep code minimal. 2. The opposite. Keep code minimal. 3. Write a function that reverses a UTF-8 encoded string (provide a good reference to the UTF-8 format), keeping combining characters in the reversed string in the same order they were in the original. I.e. aüç should be çüa, not ¸c¨ua. Assume the string of bytes is a proper utf-8 string, that only combining characters have to be order-preserved and that the only combining characters are the ones with unicode character codes in these ranges: (give them some standard ranges). Keep code minimal. Anybody who can do these three things should be able to learn most any other tech stack you throw at them. If on the other hand you're looking for people with specific expertise with a given branch of computer science, then you need a different set of tests. The central question is - do you need a developer or a mathematician specialising in discrete mathematics. Those are two different sets of people, though they tend to overlap.

yodsanklai 12y ago

I disagree with the author that this is a "puzzle question" that requires an "a-ha" moment. Quite the opposite, it is an easily solvable algorithmic question (maybe with a little guidance after the candidate suggest suboptimal solution). Also, the good thing from the candidate point of view is that it is the sort of questions you can prepare for.

sergiotapia 12y ago
>sort of questions you can prepare for. The point is why do you need to prepare for and regurgitate these silly answers that you will almost assuredly never ever ever use in your day to day job?
- eweise 12y ago
  +1 to that. Most programming jobs are about integrating a bunch of different technologies together to solve a business problem. In 20 years I've never written a linked-list or sorting algorithm for work yet interviews are increasingly narrowly scoped to algorithm questions. I've found that these questions are usually asked by young people because they are fresh out of school and have been led to believe that knowledge of algorithms is the most important consideration. Give them a decade of creating products based on css, html, node.js, nosql, yessql, etc and they will come to realize that programming is more about understanding what a customer needs and finding the most efficient way of delivering a solution. Ability to work with other, lead a team, write clearly, explain to customers the tradeoffs and costs of different solutions are actually way more important than knowing how to find a cycle in a linked list.
  - twistedpair 12y ago
    But how do I test all of that in 30min or less? Do I have to actually get to know the person, their work history and their strengths? Does that mean I have to read the resume before I enter the room?
Marazan 12y ago
Did you miss the part where it took 12 years to come up with this solution?

dfox 12y ago

The article seems to imply that the turtle and hare algorithm is only valid solution for this problem, which is certainly not the case. This problem can be also solved by building big set of already seen list nodes or adding bit to list nodes themselves. Whis is both something that everybody should be able to come up with and implement. I think that this is in fact quite good interview question because while there is one non-obvious perfect answer, it also has some sub-optimal solutions that are pretty obvious and simple to implement.

owenmarshall 12y ago
Yeah - the article built it up and built it up, but when the question finally came up my thought was "wait, that's it?!" If the interviewer asked the question and rejected anyone that didn't immediately answer with the tortoise/hare approach that's the fault of the interviewer, not the question.
potatolicious 12y ago
You're right, though I think he's talking about the weird type of interviewer who expects candidates to know obscure, non-intuitive optimal solutions to these problems. I once met an interviewer who liked to use the "reverse a string" question, except he was expecting candidates to know the XOR trick. Suffice to say few, if anyone, ever got past his "filter". Primadonna interviewers who use interviews as ego-strokes are a problem in our industry. It's where the stupid "why are manhole covers round" questions came from, and it's where these hyper-optimized algorithms questions come from.
skywhopper 12y ago
This was my first thought about how to solve it. It provably works in finite time. This ought to be a satisfactory answer in an interview, particularly if the candidate points out that it's unlikely to be The Optimal Solution. After which point, the appropriate follow-up question from the interviewers would be to ask what the time complexity of the algorithm would be in the worst case.
16bytes 12y ago
Agree. The anti-pattern here is expecting a specific answer for a question. The goal should be, "how does this candidate think through problems?" If they arrive at a logic solution and can critique it, then I would consider the question completed. Some questions are better than others here, specifically ones that have many correct implementations and varying levels of optimal-ness. I'm a big fan of asking for Fibonacci implementations, for instance. Since this question can have different correct implementations, then I would not consider it a bad question to ask. It's upon the interviewer to be open to different answers, evaluate them fairly and ask smart follow-up questions. "Ok, so what's the complexity of your answer? Do you think it's possible to do better?" or "Compare your answer with this implementation".

skywhopper 12y ago

I think an unreasonable question (ie, of a practical situation in which no one will ever find themselves) deserves an equally unreasonable answer: Write a program that starts at the head of the list and in a loop follows the "next" pointer on the current list entry, halting when the pointer is null. Run the program and wait. If the program never ends, there's a cycle in the list.

csbrooks 12y ago
Then just come up with an algorithm that proves if the program will halt or not. Easy peasy.
gohrt 12y ago
I have had this problem in real life. I had a graph database, and I needed to find the end of a path in the graph. If the the path looped back on itself, my program would not terminate.
- hugofirth 12y ago
  This occurred to me as well: the graph data model is one of the few areas in which you might practically need to address this problem. Again, however, a lot of these issues specific to the graph data model are open research questions and not really appropriate to an engineering interview.
- option_greek 12y ago
  Finding the loop in a graph is a much more valid scenario and any candidate aware of traversal algorithms will have a much better chance of dealing with it than finding loop in a LL.

gabemart 12y ago

> In this case, the generally “correct” answer is a tortoise-and-hare algorithm, where you have two pointers at the head of your linked list, one traverses the list two nodes at a time, and one traverses the list one node at a time; if ever the pointers point to the same node, you have a cycle somewhere. I'm an extreme novice to programming. I don't fully understand this. 1) How can you traverse a linked list two nodes at a time? Is this just short-hand for "go to the next node, then go to the node after that, and call that one operation"? 2) If you can detect when two pointers are pointing to the same address, couldn't you solve the problem by traversing the list one node at a time, storing the addresses of each node in an array, and checking to see if the array contains any duplicate values at intervals?

nayefc 12y ago
1) One loop, two pointers. Each iteration increments each pointer by a different margin. 2) Yes you can do this but not in all languages.
mankyd 12y ago
The "tortoise" pointer does a standard traversal - one at a time. The "hare" pointer goes from one node to the next _and then the next_ - i.e. two at a time. If the hare hits a null node, there's no loop. If the hare hits a cycle, it will eventually run back into the tortoise and there's a loop.
- pessimizer 12y ago
  I must have learned this algorithm in school, but completely forgot it. My naive implementation was 2), but this is the first explanation on this page that made Floyd’s cycle-finding algorithm click for me:) Now I can't unknow it - thanks for the clarity and concision!
aquamongoose 12y ago
With regards to (2), this is one way of solving the problem. However, your solution uses O(n) memory (where n is the size of the linked list), and the tortoise-and-hare algorithm uses only O(1) memory. Here's how it works: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_ha...

patrickmay 12y ago

It's a bad question if you expect a quick, explicit answer. It's somewhat less bad if you're looking to have a conversation about how to solve problems the candidate hasn't seen before. I've used an arguably "puzzle" question that was presented to me in an interview with some success -- the missionaries and cannibals problem. There are three missionaries and three cannibals that you must get across a river. The boat holds only you and one other person. The cannibals on either bank must never outnumber the missionaries on that bank. It's a good question to see if a candidate understands how to apply some basic computer science concepts. It can easily lead to a 30 minute discussion at the white board, with no need to get working code. My favorite question is completely different. "What do you like best about your favorite programming language and what would you change about it if you could?" Anyone who doesn't see any flaws in their favorite language, particularly if it's Java, gets politely shown the door.

mwnz 12y ago
+1 to this. The objective is not to see the person solve the question immediately, but to observe their problem solving process.
thisone 12y ago
but now anyone who's watched Fargo (tv) will be able to work it out
lostcolony 12y ago
The problem with using this as a meta-question, is that someone who knows the answer may treat it as such. That is, the person who comes to realize the canonical way of solving it may truly be brilliant and having been hinted and helped along the way came up with the solution, or he might have already known it and just played a metagame, assuming that's what you wanted. Basically, you have four possible outcomes: People who have never heard of it, don't come up with the canonical solution. People who have heard of it and just blurt out the answer. People who have never heard of it, but who come to realize it over the course of the interview. People who have heard of it and who play it as a game, working towards it and then suddenly having an epiphany. The first is interesting. The second you hopefully dispense with the question as being useful. The third would be a great hire, but is indistinguishable from the fourth, who you've learned nothing about except they know how to play your interview process. Which may or may not be the criteria you're looking for.

shmerl 12y ago

> With all of those hundreds and hundreds of minds, this problem remained open for 12 years. A very good point. Some people just forget that while solution can look simple when it's already known, actually finding it can be extremely hard and more akin to invention breakthrough. So such question is more similar to asking to prove some difficult theorem really, than to anything else.

prelud 12y ago

I am the guy who asks that question on every interview. You can hate on me now! Let me clarify. I don't expect the candidate to get to the "a-ha" moment at all. I make my expectations very clear upfront so that the other side wouldn't panic. However, I expect to see how the candidate would approach the problem with the right attitude so I could get some insight of his/hers thinking patterns. I personally wouldn’t mind if an interviewer asked me something in the lines of "how would you build a nuclear plant?", although I have no knowledge on the matter.

peaton 12y ago

I completely disagree that this question is irrelevant. I can imagine this exact situation in compiler design where you have dependent types that can't have infinite loops (in pseudo-code where forward declarations are not needed or implied): type a = b type b = a If a program has a structure like this with cyclic dependencies, then the compiler must be aware of this and break. (At least, I can imagine a situation where this could be a desired attribute.)

sz4kerto 12y ago
You are mixing up cyclical linked lists with loops in a graph. The reason why the question is bad stems from the fact that it's specifically about linked lists.
- peaton 12y ago
  I could definitely be mistaken, but I don't see a difference between a linked list and a graph. They are two ways to represent the same thing. That being said, if he asked me to find cycles in a linked list, I might determine the adjacency matrix and check for loops: http://stackoverflow.com/questions/16436165/detecting-cycles-in-an-adjacency-matrix http://stackoverflow.com/questions/16436165/detecting-cycles... This is at least very easy to reason about. However, if you are still right my thought process is just very wrong.
  - dllthomas 12y ago
    "I could definitely be mistaken, but I don't see a difference between a linked list and a graph." A linked list is a particular type of DAG (or at least DG). The relevant distinction between linked list and the general case is that a linked list restricts nodes to (zero or) one outbound edge. This is relevant to the problem at hand, because you only have one tortoise and one hare and so they can only follow one path.
    - peaton 12y ago
      Ok, that was poorly worded. What I mean is that a linked list can be thought of as a restrictive graph. I'm just saying I'd prefer to think of it as a graph. I could still be wrong. Is that kosher?

general_failure 12y ago

Once in an interview I was asked to implement a synchronization mechanism between processes using shared memory. It turns out this is the petersons algorithm. I mean if I could solve this, I would be Peterson :) heck, even smarter because I would do it in 20 mins.

JonnieCache 12y ago

Hypothetically, if when asked this question in an interview I were to reply "I'd look up the canonical solution on the internet and just implement that. I have better things to keep in my brain than linked-list algorithms, and there's no way I'm going to beat decades of phd work off the top of my head", what would happen? Obviously it depends on the job I was interviewing for. Let's assume I'm not angling for a position as lead on a distributed load balancing layer or something. I suppose if they're looking to see my problem solving workflow then I'd look like kindof a dick. But then, as the article points out, so would they.

_mulder_ 12y ago
A great response would be to just say "hold on", whip out your phone and Google the answer, show it to them and finish up with "How long did it take your other candidates to complete that task? next..." Point being, you're demonstrating initiative and, that old cliche, thinking outside the box. Think Will Smith in Men In Black. Some interviewers might be impressed with your lateral thinking, others might be annoyed at your attempt to be a 'smart ass' and avoid the intention of the question. But that's always the problem with these type of interview questions, it depends so much on the expectations of the interviewer.
- JonnieCache 12y ago
  I think it would be funnier to silently transcribe the code from the phone to the whiteboard, and then just sit back down and look at them while you wait for a response.
  - jiggy2011 12y ago
    "oh, you can use google. Surely none of the other candidates could think of that"
    - TheOtherHobbes 12y ago
      The professionals use StackOverflow.

davidjeet 12y ago

Had that exact question given to me before, but it was in the form of a closed book "pre-screening" written test. I simply put down my pen, walked out of the room and told the recruiter if this company was hiring based on these type of questions I would be a terrible fit :)

twistedpair 12y ago
They were likely hiring to fill a PHP dev roll writing CRUD web forms too, right? I've been places with tough interviews and incompetent developers and the opposite as well. One does not necessarily correlate with the other.

sjs1234 12y ago

I had this in an interview (back '96). Came up with a linear time constant space solution: create a new node, push it on the front, reverse the list, check if the 1st node is the same one you pushed, if so it has a loop, otherwise it doesn't. The downside is you need to reverse again to get the original list. Another answer is to mark nodes using the low bits of the next pointer. Also linear time, but also requiring clean up. I can see how not knowing c would cause people to think this question was somewhat unfair, but I didn't see it that way.

herge 12y ago
How would you reverse a linked list with a loop?
- nmrm 12y ago
  If your list is laid-out a contiguously in memory as structs with both next and prev ptrs, you can visit each member using ptr arith and switch the values without actually walking the list using next and prev. Ditto if there's an underlying data-structure involved such as an array.
  - herge 12y ago
    How could you have a linked list with a loop in contiguous memory? Or in an array?
    - dllthomas 12y ago
      You allocate an array of objects that contain pointers, then link them together. It does not have all of the typical benefits of a linked list (in particular, there's a hard max size and may require a fixed size, depending on just what you're doing to it here) but it does allow O(1) reordering elements for a list-order traversal, while also allowing a linear traversal through memory.
      - herge 12y ago

azov 12y ago

I'm no fan of this particular interview question, but the article takes it too far. You can figure out tortoise-and-hare algorithm by reasoning (I'm pretty sure I did the first time I've seen the problem - although not in an interview setting). The key is to recognize that there's a very limited number of things you can do given all the constraints: moving pointers is pretty much the only tool you have. If it indeed took 12 years for the algorithm to appear, it's likely because finding loops in a linked list isn't a very common problem, not because the algorithm itself is that hard.

peaton 12y ago
Nor is the 12 years thing particularly good reasoning... By that thought process, it took humans hundreds/thousands/millions of years to develop a compiler, so how can I be expected to develop one over the course of 4 years in college? Or even over the course of my life?
- csallen 12y ago
  Not exactly a valid analogy, because his start date isn't "the beginning of human history", rather it's the development of the linked list data structure, which is the first point at which humanity possessed sufficient knowledge and tools to figure out the cycle-detection algorithm. Given that we didn't have the knowledge or tools necessary to make a compiler hundreds/thousands/millions of years ago, you'd have to bump up your start date considerably.
  - peaton 12y ago
    Sure, I stretched that too far. But hopefully the point is made. Then should we expect no students (or anyone) to be able to build a compiler (or os kernel) in any amount of time given the internet and whatnot? While I may be articulating this poorly, I think my fundamental issue with his point is solid.
- CocaKoala 12y ago
  Because over the course of 4 years in college you're provided with resources that explicitly teach you how to develop a compiler, a scenario which is entirely different from what happens in an interview.

option_greek 12y ago

I don't want to complain but one of the major culprits who conducts these kinds of interviews is Amazon. After going through their interview process, I'm of the opinion that they basically want you to memorize careercup, geeksforgeeks and leedcode and just spit it out in chunks at appropriate times during the interview.

ssw1n 12y ago

If I do not know any better, the first thought that would come to my mind would be: "Wow, this company has really messed-up code base, and people here cannot even get linked-list done right. Do I really want to work here?"

S4M 12y ago

The page is down, so here is the cached version: http://webcache.googleusercontent.com/search?q=cache:rwL5dDEDvTsJ:www.nomachetejuggling.com/2014/06/24/the-worst-programming-interview-question/+&cd=4&hl=en&ct=clnk&gl=uk http://webcache.googleusercontent.com/search?q=cache:rwL5dDE...

ollysb 12y ago

After a 10 minute phone screener I now rely on a paid pair-programming session to identify good candidates. This is what you're going to hire them to do so why waste your time asking questions that at best form a poor approximation of their skills?

dualogy 12y ago

Timely yet on-topic ;) https://twitter.com/tom_forsyth/status/482337551718440962 https://twitter.com/tom_forsyth/status/482337551718440962

justinvh 12y ago
Tom Forsyth listed one of the reasons--when a storage is explicitly expressed. The other two that I can think of are for external linkage and non-constant expressions on the rhs. In the end, you really don't know without some introspection. It's up to the compiler. External linkage is one that will force storage, but in general const will require internal linkage and fold expressions accordingly (at least for primitives). Edit: I would never expect anyone to actually remember or need to know that for an interview. It would be definitely something you would re-discover/discover because you had to run into it.

jameshart 12y ago

Disagree that this problem never arises if you're not implementing a linked list data structure. Here's a file a customer sent you that describes their organizational hierarchy: ID Name Manager 1 Alice 4 2 Bob 1 3 Charlie 8 4 Dave - 5 Elise 3 6 Fred 2 7 Gemma 1 8 Henry 5 Is this a valid hierarchical tree? Okay, it's not exactly the same problem, but it's certainly similar...

phaedrus 12y ago
Technically in the context of an org hierarchy that would be detecting cycles in a directed graph, not a linked list cycle. I don't think the algorithm to detect cycles in a linked list applies to general graph problems, and the problem is much harder for graph cycles.
- jameshart 12y ago
  It's not a generic directed graph either, though - each node only has one outbound link. The sequence of parents for any given node is a linked list, and a cycle in that list is invalid. You certainly don't need to run tortoise and hare for every node path looking for cycles. There are other approaches, clearly - reachability analysis starting from each root node, for example. But if I were to ask you to write a routine to find the root node for a given node based on that data, then ask you to guard that routine against finding yourself in an infinite loop or stack overflow, tortoise and hare would be a legitimate answer. Just trying to make it clear that just because the question asks about linked lists, doesn't mean it's always about abstract data structures.

rgawdzik 12y ago

Uh we did this in our first year CS curriculum...you are telling me your interview candidates can't even do what a first year CS freshmen can?

nmrm 12y ago
Are you referring to tortoise-hare algorithm? I refuse to believe CS freshmen regularly come up with this on their own. Maybe a few percent, everyone else is googling or relying on huge hints from the lecturer. If you were referring to a more trivial algorithm (e.g. linear space), I think you misinterpreted what the interviewer was expecting and would not have gotten the job. It's also worth noting -- esp if you're referring to the TH algorithm -- that CS curricula are not standardized and that there are probably dozens of "clever trick" algorithms you haven't seen and couldn't come up with on the spot (e.g. can you initialize an array in constant time?), but someone else thinks is trivial because they happened to see it in a lecture/read it online.

joesmo 12y ago

What all algorithm and idiotic interview questions (like moving Mt. Fiji) are great for is the interviewee himself, not the interviewer. They are a huge red-light indicator that there is something wrong with the engineering culture and department at the company you're interviewing. While there are exceptions, in my experience, there is such a direct correlation between the two, that questions like this have led me to walking out of interviews (politely of course). Why continue if you know you won't take that horrible position? Obviously, if you're hired to write algorithms, then it might be a different story, but most programmers are simply not writing new algorithms. Ever.

pekk 12y ago
Can you detail a little the kinds of things you associate with stupid questions that make you want to walk out?
jiggy2011 12y ago
Isn't writing algorithms almost the definition of programming?
- nmrm 12y ago
  I think "coming up with interesting algorithms" was the intended meaning. In which case, no, everyday programming is mostly not about designing algorithms. Otherwise, programmers would spend most of their time with journals and books, with a few days of programming each month.
  - jiggy2011 12y ago
    Interesting is fairly subjective but ultimately you are designing processes to solve problems. If you cannot demonstrate ability to solve a simple, well trodden problem how will you be able to solve a new one?
    - nmrm 12y ago
      > Interesting is fairly subjective Interesting is a social construction. As such, I would define interesting as worthy of publication in a first or second-tier conference at some point in the history of the field. > If you cannot demonstrate ability to solve a simple, well trodden problem how will you be able to solve a new one? 0. I've seen many well-respected researchers who have solved truly interesting, new-to-humanity problems stumble on well-known problems others consider easy and/or fundamental. In fact, this is probably true for every single researcher. And doubly so for practitioners. One person's fundamental technique is another's blind spot. 1. Simple != easy to come up with. Often exactly the opposite! Take the TH algorithm as an example. It's a very simple algorithm. Small. Simple. Optimal. Awesome. Not trivial to discover, however. 2. Well-trodden -> unless the algorithm is absolutely fundamental and taught everywhere (e.g. sorting), you've given up on testing problem solving skills. You're just testing whether the person's intro/DS/algo professor covered this particular algorithm (and maybe their memory). Or, more likely, rather their random interview studying happened to hit your pet problem. Since curriculum is not anywhere close to uniform in CS -- even among top schools -- this is just silly. 3. Simple problems don't always have (simple) solutions. Create a fair voting scheme.

incision 12y ago

I appreciate all the technical discussion of this question in the article and here in the comments, but I think the question is just a symptom. The root issue here is the other interviewer and the apparent interview process. >'In the post-interview pow-wow, all of the engineers who’d interviewed him gave him the thumbs up, except my interview partner except my interview partner, who refused to hire him...' Yes, yes, optimizing for false negatives over false positives is all the rage, but this just sounds broken - wasting the efforts of a full panel only to accept an arbitrary single-question veto. >'..on the grounds that he completely flubbed this question, and "any engineer worth his salt should be able to answer it."' Good engineers don't necessarily make good interviewers. Outright excluding someone based on any single question is just horribly self-satisfied behavior.

pekk 12y ago
If you look at the structure of their pow-wow rather than its labeled purpose, you see that its real purpose is not to find a competent engineer but just to build a consensus. E.g. so nobody complains they wouldn't have hired the candidate. It's the same principle which puts multiple men on a firing squad.
- walshemj 12y ago
  Good way to hire a camel when you need a mustang - your optimising for mediocrity. Everyone does know the joke about a camel being a horse designed by a committee? And should not have the chair/leader of the committee over ruled the outlier anyway.
  - qbrass 12y ago
    You should absolutely get a camel over a mustang. Even though they look like they're designed by committee, camels are an example of form following function. They're very well suited for their environment, and although they're stubborn, make good work animals. A mustang on the other hand, is a feral horse. They're harder to domesticate because they've known freedom, and they've adapted to living in the wild by being smaller and more timid than horses selectively bred for doing work. If you really do need a horse, there are few cases where you need that horse to be a mustang. If someone is hiring you because they think you're a mustang, you better hope they're caught up in the romanticism of cowboy stories instead of them being desperate for cheap labor or meat.

jerrickhoang 12y ago

I don't think interview must entirely be related to the practical world. I mean having a very hard and interesting practical problem is the best of both world but not necessarily the only way to go. If you want to know if the candidate can really build things you can check out his github/resume. I think the 45-min interview is just to determine how smart the candidate is. If you want to determine if someone is smart you put them in a very hard situation (not necessarily a practical one) and see how they reason about it.

blahedo 12y ago

This article raises, sort of incidentally, one of the issues I've noticed recently teaching intro CS. Every CS2 class teaches linked lists, right? (Except for the ones that hit them in CS1, of course.) But: when was the last time you had to roll your own linked list? Once, not that long ago, it was important to cover linked lists (and other data structures) because you'd have to be writing them in order to implement a program of any significant size. Now, though, all the common ones are already implemented for you (and to be honest, we don't even use LinkedList all that often---array-based lists are better in most real use cases). So now their role in (my) CS2 is chiefly as setup. I still need to cover linked lists because they establish concepts that will be important when we get to trees (links) and to more general graphs (cycles and the lack thereof), as well as in operating systems (continuation inodes, memory allocation) and other areas. But implementing an honest-to-god plain-old linked list holding ints or strings or whatever? Who does that anymore?

belovedeagle 12y ago
This is a question I see asked all the time and it's absolutely mind-boggling to me that you could ask it. Who do you think writes the linked-list libraries you use? Do you think the libraries just magically appear when someone wishes them up? Do you think we should use the current set of libraries forever, calling them "good enough", and limiting ourselves to current programming languages for all of history? That's what will happen if we no longer teach people to write these things; or else (more realistically) we leave it up to them to make the same mistakes and waste time solving the same problems which were solved decades ago, because no one ever bothered to teach them the answers. Give it a few years and we'll have no one left who can program in anything but javascript; no one left to write the browsers! --- or so I worry when I read HN sometimes.
- blahedo 12y ago
  You'll notice I'm not suggesting we stop teaching them. But what you describe are specialised applications; my point is that where linked lists were once something that every programmer, large and small, could reliably expect to have to write repeatedly, they're now something that are only directly relevant to, say, library maintainers.

dllthomas 12y ago

'Between 1955 and 1967, the problem of “how do we determine if there is a cycle in a linked list without modifying the list” was an open problem. Meaning, any number of PhD candidates in Mathematics or Computer Science could have written about it as part of their dissertation. With all of those hundreds and hundreds of minds, this problem remained open for 12 years.' Were there any computer science graduate programs between 1955 and 1967? You're not dealing with "hundreds and hundreds of minds", you're dealing with those minds who 1) heard about linked lists, 2) heard about or realized there was a cycle detection problem, and 3) devoted any energy to that problem as opposed to the myriad other problems available to a mathematics or electrical engineering graduate student. All of this has to have happened between 1955 and when the problem was solved in advance of starting to write the paper on it, in advance of publication of the paper in 1967. The paper also presumably included a proof of correctness that isn't being asked for in the interview. The interviewee has the further advantage that they know there is an answer in the space of the constraints the interviewer has drawn. As they suggest less optimal solutions, those constraints get tighter, and the answer gets easier to find. If they have been through an undergraduate computer science course, they probably also have more familiarity with linked lists than most of the people attempting to solve the problem before 1967. None of which is to say that failing to find the answer deserves disqualification - that's probably still unreasonable - but the picture is nowhere near as absurd as presented.

nsxwolf 12y ago

I would love to find the definitive resource for preparing for interviews like this. Besides answers like "just be awesome", is there such a book or page? In the past I've searched for various compendiums of algorithm interview questions and saw the cycle detection one come up. I knew I would never be able to solve such a problem on the spot. This blog post initially put it in perspective for me, that its pretty much a BS academic question that you have to already know the answer to - until I read the comments here, full of totally awesome alpha SV nerds who are saying "I instantly got the optimal answer without any foreknowledge". Now I don't know what to think.

mcguire 12y ago

"...'Write a function that can detect a cycle in a linked list'...You can’t reason your way through [that question]...all you’re doing is testing if someone has seen your particular puzzler before or not." I think I'll take a pass on interview advice from this character.

tzs 12y ago

A not quite serious solution [1]: Let m = size_of_current_process / sizeof(list_node) + 3 Let np = pointer or reference to first node in list while (np != null) if (m-- == 0) return HAS_CYCLE np = np->next return NO_CYCLE [1] this approach might actually be acceptable in some circumstances

jgg 12y ago

My problem with this type of interviewing is not the questions themselves, but when the end products (i.e., code) don't reflect what the company is ostensibly screening for. Ask me all the data structure questions you want, ask me about C and Scheme because Spolsky said so, ask me some irrelevant puzzle or ask me how I would "fix problem A we've been having", when I obviously don't know your application well enough to respond adequately - I don't really care. If your flagship product turns out to be a buggy web application full of SQL injection vulnerabilities, it tells me that you're really just partaking in a sadistic circlejerk. It reminds me of the anecdote about a football coach who took a team, worked them as physically hard as possible in preparation and then proceeded to lose almost every game.