How to Answer: How do you find the starting node of a cycle if a link contains a cycle?
Advice and answer examples written specifically for a Software Developer job interview.
28. How do you find the starting node of a cycle if a link contains a cycle?
How to Answer
Let's say for argument's sake that two cyclists (no pun intended) are pointed at the beginning of the starting line with their cycles. For clarification purposes, the two cyclists are the pointers. In this example, if we move cyclist 1 a step at a time and the second cyclist 2 steps at a time, they would eventually meet at a single point. An interviewer wants to know whether you can explain how you arrive at an answer and the reasoning behind your findings. This is important because when you explain if a link contains a cycle, you need to back that up with a verbal or written (whiteboard) example. A common response might be to mention that a meeting point is 'P' steps away from the beginning of the cycle, and the 'cyclists' meet when cyclist 1 has taken a '7' total steps toward the point.
Written by Tom Dushaj on August 31st, 2021
1st Answer Example
"The way I find a starting node of a cycle is to measure the length of 'R' and how far the distance is away from the cycle. That's a simple explanation. A more complex explanation I can illustrate is when cyclist 1 travels double the speed of cyclist 2, they both arrive at the same meeting point when time is constant. Since there are several examples I can give to make my point, I would like to share one more. The next pointer of each node that is traversed is made to point to this temporary node. This way, we are using the next pointer of a node as a flag to indicate whether the node has been traversed or not. If I come across a node that points to null, then the loop doesn't exist. If I find that the code runs in O(n) time complexity and uses constant memory space, then that tells me that this needs to be researched further."
Written by Tom Dushaj on August 31st, 2021
2nd Answer Example
"I use Floyd's Cycle-Finding Algorithm to find the starting node of a cycle. I believe it to be the fastest method I have used. I make sure that every node is checked to see if the next one in the sequence is pointing to a temporary node or not. Here's an example of what I mean.
I can use traverse linked list pointers
Traverse linked lists using two pointers
I can move one pointer (slow_p) to one and another pointer (fast_p) by two.
If these pointers meet at the same mode, then there is a complete loop. On the other hand, if pointers do not meet, the linked list doesn't have a complete loop."
Written by Tom Dushaj on August 31st, 2021