5 ms·

Can I ask for your thoughts on the cycle in a linked list question? I asked someone that today, and it didn't go very well. I gave him the hint to start with w

• jerf 12y ago
  It depends on how you ask it. If you ask it as an exploratory question, it can be useful. If you ask it as a question where you're expecting the "right answer", it's awful for interviewing, because the insight is difficult to spontaneously come up with, yet easy to have already encountered online. Neither result is very informative. It seems to me to still be very poorly understood in general that the purpose of a question in an interview is not to see if the candidate gets the right answer, but to see how they function. (In those interested enough to read the discussion this deeply it's probably somewhat better understood.)
  • jspiral 12y ago
    The reason I ask the question is that I want to see if the person can handle thinking about recursion, and how their debugging process works, and how they built toward a solution. I always stipulate that they can use whatever brute force approach they want, and that i'm not judging on the algorithm. (Though we'll then discuss the big O complexity of what they've done and i'll ask them to brainstorm some avenues for optimization). The main drawback of this particular problem is that it's biased toward people with more formal CS experience who have probably seen more tree and graph stuff, when i'm not really trying to measure for that experience directly. I'd be interested in a problem that doesn't have that aspect but still takes up a fair bit of brain space when thinking through. What I mean by that is that when you're trying to build and debug something recursive, you have to hold in your mind some representation of what the stack will be at various points, and not everyone has a great aptitude for that.
• mrowland 12y ago
  For what it's worth, the solution to that question was an open question in computer science for over ten years, so I would guess that people who get it quickly in an interview are more likely to have heard the answer before than successfully invent the tortoise-and-hare algorithm on the spot. Further reading on that question in this old thread: https://news.ycombinator.com/item?id=7953725 https://news.ycombinator.com/item?id=7953725.
  • jspiral 12y ago
    In practice, what happens is that we both acknowledge that if this was a real work problem, step 1 is to google it. I then tell the candidate that i'm not going to judge them on the algorithm they use, just their ability to work through the problem. This isn't a whiteboard problem, it's done on a machine. It's never happened to me yet with this type of problem, but i'd be really impressed if I did run into someone who has the optimal algorithm for this memorized and can code it on demand in an interview. I'd certainly want to check that they haven't spent all of their time just memorizing algorithms and they can still do other things of course. If this did happen i'd want to validate that they really understand the solution and aren't just spamming it out by rote, but if they've really got a few algorithms in the bank like this i'll just consider this box checked and move onto other considerations. all I really want to know is if the candidate has the "horsepower" to deal with these sorts of problems, many people don't. someone who can code optimal solutions to these things on demand obviously does. That said, obviously this is much easier for someone who's dealt with trees and graphs and such a lot before, so it's not ideal. I'd certainly be interested in a better way.
    • jcrites 12y ago
      Would you accept with full credit an answer like this? Iterate through the list adding its nodes to a set. If a node is already present when we go to add it, then stop, since we've found a cycle. Otherwise if we reach the end there is no cycle. With a hash set which has O(1) insert and membership check, the algorithm takes O(n) time and space since. Note that I mean we're adding the nodes themselves to the set, not the element stored by / pointed to by the nodes. This may mean storing a pointer to the node in the set, or some other kind of object identifier. I think this solution is fair to expect from anyone, including the caveat about node identity. Plus a candidate who already knows tortoise and hare should be able to come up with this when asked to solve the problem another way ("what's the simplest, most naive solution you can think of?"). I am not sure that I would expect anyone to come up with solutions beyond this one and the O(n^2) solution during an interview. I think those solutions correspond to knowledge that everyone should have in their working set. "Have I seen this thing before" is a pretty simple application of data structures. The O(n^2) solution trades off storage to track whether a node has been seen with determining it on demand in duplicate each time by traversing the list from the beginning repeatedly. (If solutions are fair game that involve modifying the list, such as reversing it, or assuming that list nodes can be marked as seen, then make sure the boundary of what's allowed is clearly communicated. Make sure that the candidate does not neglect to consider a category of solutions by mistaking it as out of bounds. Candidates who are asked to design an algorithm to process a data structure cannot usually modify that structure to make the problem easier, so if this is something that you want to encourage, then you might tip the candidate in that direction by asking them to write the definition of their list node, and encouraging them to implement the node however they want as long as it meets your definition of being a linked list. Conversely if this is out of bounds, it might be best to provide the definition of a list node.) Anyway, it seems like a fair simple interview question along the lines of a medium difficulty FizzBuzz, if the answers above give full credit. I don't think effective software engineers would be tripped up by this. One area of concern might be people looking for overly fancy solutions without trying "er... can I just track what nodes I've seen in a set?", but finding simple solutions is part of being a good engineer. I think there are better questions than this one: (1) it's too easy to memorize all the answers (2) it's already well known by this point (3) I have not heard of a good way to build on the question to make it challenging and interesting for high performing candidates. This might be an OK intro question before moving onto a harder one. I've never asked this in an interview - just going by instinct.
• justrudd 12y ago
  The problem I see with your question is that you have a bias towards a solution. "The goal of that question from my perspective is to watch them solve a problem that requires recursion" I wouldn't use recursion for my solution. It takes up stack space for no reason. If I'm going to be allowed to use more space, I'd just loop through the list, add them to a set, and check if I've already seen it. No recursion, but extra space. Is it more space than another stack frame? Depends on the type of set I'm using. But at least I know I won't blow up the stack (maybe the heap :-) Since you are asking for opinions from others, I'm going to assume you wouldn't be upset with me solving it this way. So am I less of an engineer because I didn't immediately go for recursion? With that said, everyone has a baseline - answers they expect to see. But everyone has to keep an open mind. My company is trying to come up with a corpus of questions and answers to those questions at the junior, normal, and senior level. I've voiced my opinion that it is a slippery slope. If you get someone who isn't a skilled interviewer, and the interviewee doesn't use one of the prescribed 3 answers, what happens to that candidate? Granted it is one data point in the loop, and not the only data point. But as I stated, it becomes easier to be "lazy" during the interview.
  • jspiral 12y ago
    >So am I less of an engineer because I didn't immediately go >for recursion? No, not at all. a stack is a stack, whether it's the call stack or one you maintain in code. Its not the recursion that's important to me, it's holding a problem of moderate complexity in your head in order to be able to come up with a solution. Problems that lend themselves to recursion seem to present a bar that some engineers struggle with, and others find easier, in my anecdotal experience. I know I said recursion is important all over the place, clearly my thinking is sloppy on this and needs to improve. I have this idea that there is a class of problem, that lends itself to recursion, that separates the wheat from the chaff in some ways. maybe that's nonsense. What I really want to test for is the ability to juggle abstractions while working through code problems. there's probably a better way to do it. Thinking about this corpus of questions and answers, I guess the common idea of fixing broken code might have a bit more merit because it removes the risk of an interview focusing too much on judging the approach and turning it into a trivia contest (have you seen this before and do you remember how to do it).