3 ms·
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 prog
by 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 agoThen just come up with an algorithm that proves if the program will halt or not. Easy peasy.
- gohrt 12y agoI 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 agoThis 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 agoFinding 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.