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.

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.

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.

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.

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

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?

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.

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

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

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.

'Between 1955 and 1967, the problem of “how do we de­ter­mine if there is a cycle in a linked list without mod­i­fy­ing the list” was an open problem. Meaning, any number of PhD can­di­dates in Math­e­mat­ics or Com­puter Science could have written about it as part of their dis­ser­ta­tion. With all of those hun­dreds and hun­dreds of minds, this problem re­mained 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.

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.

undefined

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?

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

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

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.

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?

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

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.

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.

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

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

The page is down, so here is the cached version: http://webcache.googleusercontent.com/search?q=cache:rwL5dDE...

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

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.

"...'Write a func­tion 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 par­tic­u­lar puzzler before or not."

I think I'll take a pass on interview advice from this character.

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.

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.

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.

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?

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

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.

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.

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 :-/