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.
Yes, someone who can code the solution you describe on demand would be a flying colors pass for me.
I agree with you that there are probably better questions. As you say, I'm looking for a medium difficulty fizzbuzz. I also agree with you that this is not going to be challenging and interesting for high performing candidates.
Incidentally, if someone has managed to memorize the solution to this and other algorithm problems I would consider that a pass. just the ability to do that is enough. there's enough code involved that they have to understand the problem pretty well to memorize it, and its the ability to understand that i'm interested in. (Barring some extreme outlier with super memory but bad other skills, but I'll have to detect that with other questions).
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.