Google Software Developer Mock Interview
Practice 30 Google Software Developer interview questions covering algorithms, system design, and coding challenges.
Question 3 of 30
How do you find the starting node of a cycle if a link contains a cycle?
How to Answer
Example Answer
Community Answers
William Swansen has worked in the employment assistance realm since 2007. He is an author, job search strategist, and career advisor who helps individuals worldwide and in various professions to find their ideal careers.
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 one step at a time and the second cyclist two 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 the mention of, let's say, that a meeting point is 'P' steps away from the beginning of the cycle, and the 'cyclists' meet when cyclist one has taken a '7' total steps toward the point.
William Swansen has worked in the employment assistance realm since 2007. He is an author, job search strategist, and career advisor who helps individuals worldwide and in various professions to find their ideal careers.
"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."
Interview Coach
Jaymie
A real coach, not AI. I read every answer myself and write back with personalized feedback.
Typically responds within 24 hours.
0 - Character Count
Unlock All 30 Google Questions
Prepare with questions that reflect Google's rigorous technical interview process.
Get StartedJump to Question