News for hackers. Stuff that matters.
Re:The Worst Programming Interview Question by sjs1234 on Friday June 27, 2014 @10:54AM (#7954181)
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.

Re:The Worst Programming Interview Question by herge on Friday June 27, 2014 @10:58AM (#7954206)
How would you reverse a linked list with a loop?
Re:The Worst Programming Interview Question by nmrm on Friday June 27, 2014 @12:32PM (#7954821)
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.
Re:The Worst Programming Interview Question by herge on Monday June 30, 2014 @02:48PM (#7966795)
How could you have a linked list with a loop in contiguous memory? Or in an array?
Re:The Worst Programming Interview Question by dllthomas on Monday June 30, 2014 @02:52PM (#7966817)
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.
Re:The Worst Programming Interview Question by herge on Monday June 30, 2014 @03:32PM (#7967109)
If the linked list has a loop, but you don't know it, how do you figure out the length of the list to allocate enough space for your array? How do you copy the list into the array without traversing the list? How do you traverse the list without hitting the loop and looping infinitely?
Re:The Worst Programming Interview Question by dllthomas on Monday June 30, 2014 @03:40PM (#7967168)
If you know that all the elements in the loop are already in the array then traversing it is easy. Of course, if you have an upper bound for the length of the list, there's an easier check...