Interview Question: Start of Loop in a Linked List
ฝัง
- เผยแพร่เมื่อ 22 ส.ค. 2024
- This famous interview question is about reporting if a linked list has a loop, and then finding it's start. We use the 'Hare and Tortoise' approach, where two pointers moving at different speeds meet at surprising positions.
(Excellent) Answer Link by CEGRD:
stackoverflow.c...
#linked-list #interview #puzzle
hey i have an alternate solution for finding head.
after hare and tortoise meet. we will make hare pointer stop at that point and make tortoise pointer move till it reaches hare pointer again and count number on nodes.
this will give us length of cycle. ( how many nodes are in cycle). lets denote dis with c.
then just take 2 pointers p1 and p2 at c distance apart.. and move both at SAME speed till p1 and p2 meets. that point will be head.
Hey Shlok, this will also work. Nice alternative :-)
Nice alternative. IMHO, that would increase the constant of the algorithm and also the code complexity. If you don't care about these, then it works.
simple solution sir great
@@DheerajKumar-hr8bf They can point anywhere. Make p1 point to start of list for example and p2 c distance apart.
github.com/BismeetSingh/linkedlistoperations
Let me know if any mistakes found.
Hey, shlok . Thanks Man. Great Imagination!
If you get asked this question in an interview and instantly respond with Tortoise and Hare you’ll likely get another question. I think some people forget the goal of interviews questions is often to see how you solve a problem you don’t already know... that being said, this is one of the better explanations I’ve seen for this algo
Best to brush up on those acting skills then (Oh, find a loop in a linked list?! Gee, I wonder how....)
@@gkcs nice thought...
@@gkcs haha
can you really end up figuring out haze and turtle by yourself for the first time you see this exercice ? I mean under pressure ?
@@splendidbeaver2027 definitely not, lol!
in the end, he meant we get to the Starting point in the cycle since,
Moving a Pointer from Head 'D' times = moving the pointer from the meeting point in cycle some constants times - K node
Hence the solution works.
Thanks, Gaurav this was really helpful.
You're not only good at the CS part of things, you're also an amazing teacher! I kept asking a question in my head only to have you answer it right after. Thank you for this amazing lesson!
Thank you 😁
Thank god, finally someone explained the intuition behind this..
You're just amazing 🙌
Bro, I searched the whole internet to get the proof which I could understand. I wasted my two days in that search and couldn't find one which made sense to me or which I can sink the proof in. I watched your video twice. And I could finally sink it in. Thank you so much man! you saved me. Especially the last proof of how to make the pointers point to the starting node.
most important thing is how to act like you have seen this question for first time in an interview :))
It was hard wrap my head around this concept. Thank you for making this video and providing with a detailed explanation.
Best Explanation. Thanks Gaurav for this.
1) At the meeting point one pointer that starts from start covers D.
2) Now at the same point when the next pointer start from meeting point trying to travel D, It will cover N*(circle Length) - k. so from the point it started at will be k steps before. And k steps before is actually the meeting point. So they both will meet at the meeting point.
Love the energy of your teaching style!
it is evident that he kept trying to understand why it works for a long time and then finally when he understood he was so happy❤
Hi Gaurav ,You nicely explained the explained the existance of solution for the equation but it can also be explained by the fact that if loop exist ,then when tortoise enter into the loop there are two particle in loop moving with different angular speed. So they have to meet at point.
Relative angular speed is non zero constant so they must collide.
+Shiwang Awasthi Ah, yes that is true. A really good and intuitive observation. Thanks!
Finally someone explaining the math, thanks!
oh man, you are something else, fantastic explanation!!!
So,this was a interesting questions. I found a solution after couple of years.😁
At last excellent explaination.
Your explanation deserves an extra like! Great video bro
Thanks!
Gaurav maaaan! I saw this question a few years back And couldn't understand the solution. This video helped! 😄. Thanks
Coming here after going through two different sources , now I don't need to go any where because solution
make sense to me now :) . Thanks for your efforts!!
Your explanation proves that from the meeting point i.e. c(j - 2i) it falls 'k' short to reach the intersection point, but it doesn't prove that from the meeting point it will take 'D' to reach the intersection point. I think what is missing over here is you will have to prove 'j-2i' is always equal to 1.
I think if it is not equal to 1 then it will end up in a never-ending loop as they are moving at the same speed. Any thoughts? @Gaurav Sen
start with fast and slow pointers.
When slow meets fast, stop.
Take a pointer p1, now assign head to p1.
Move p1 by one position and slow by one position till p1 and slow meet.
By the way, slow and p1 will meet exactly at the start of the loop.
Man this is wonderful, I was so stuck in this problem, went through multiple videos but finally found the perfect explanation. Thanks a ton, Gaurav.
You're welcome!
No need to add maths equations too. Consider a very large cycle so that the first pointer when it reaches the starting node of the cycle is t distance behind the fast pointer. That means that fast pointer is (c-t) distance behind the first to catch up with it. So, we have (c-t) + y = 2y assuming at y nodes far away the both will meet. so y = (c-t) or in other words, the meeting point is at distance c from the head pointer. So now just take head and slow pointer(at the meeting point) and keep doing ->next until they both coincide. That will be the answer.
atlast someone explained the algorithm with proof. amazing work.
Was stuck at this problem over a month, now i finally understand it, thanks a lot!!!
9:00 this was the missing link I was looking for!
Thanks Gaurav bhai for this explanation!!!
...15 years ago it took me couple of hours to find this solution, though after some fiddling with analytical approach which was hard to interpret, finished with much easier graphical...
Watch it twice to get the intuition :')
after watching it 3 times finally got it, now i can also explain it someone
Thanks a lot. This video help me understand the logic behind this.
If space complexity is not an issue, we can iterate the loop till it reaches null and keep checking each node in HashSet. If a node doesn't exist then add it to HashSet and if it exists then break the loop and return that node which is the start of loop.
To find length of the loop, we can keep extra Stack where we push the node while iterating until we discover the starting node of the loop as mentioned above. Then keep popping the nodes from the stack until we get the starting node and keep a counter while popping which is the length of the loop.
The -K part really hits the point! Nice work!
Beautiful Explanation Brother !!!
thankyou for this much needed explanation.
For those who are finding it little difficult to understand. Think of it this way:
From the equation, it is already known that if you move the hare pointer(after meeting) d times, you will end up falling short behind k pointers and hare pointer is already at a k distance from the meeting point. So, falling down short a distance of k means that it will be at meeting point when it moves a distance d
We don't know d. But we know the condition that hare pointer(after meeting) and head pointer will be equal only after moving d times. So, if they are equal we can conclude that they moved a distance d which is the meeting point
Awesome Explanation !!
Exactly the explanation I wanted to know.
Thank you!
The first question they ask in any damn interview.
We can explain it even simpler if we set the starting of loop at the head node( the starting node). And then make it complex by adding the nodes at the starting point.
Very good explanation. Thanks!
Thank you!
Would you please consider having better lighting or using brighter Colors? It’s not a pleasant experience to look at the poorly lit whiteboard. It is so hard to read the text/diagrams written on the board. Sometimes it becomes so difficult that one would want to rather stop watching the video than going thru the struggle
Hi Gaurav, Nice explanation. But you needed to say that k=(j-2i)x-D, so the slow pointer is at D iterations short of a cycle. So just by iterating it D number of time, we can get to the beginning
You are wrong.
4 years old vedio. Still clear explanation omong all vedios available in youtube.
finally understood the logic thanks
Hey Gaurav, let's say that if the question asked was to find out start point of the loop.
How is this algorithm efficient than hashing?
hashing would always take O(N) space and run time is O(N).
but this algorithm runtime can be more than O(N).. but I agree that this will always take a constant space O(1).
Just trying to understanding which one is better?
This algorithm has a run time of O(N) actually. The loop will have both pointers touching inside within 2 rounds. Thats because the gcd of (loop length and 2) is atmost 2.
This question is usually asked to test a candidate's resourcefulness. Hashing is the practical approach, but this works better in interviews 😊
thanks Gaurav - This GCD info helps..
Hey man, could you please explain the reasoning behind the GCD concept " The loop will have both pointers touching inside within 2 rounds. Thats because the gcd of (loop length and 2) is atmost 2". Or could you post a link where I can learn about it?
It's not mentioned anywhere I think...here is another video which might help with the intuition: th-cam.com/video/D-DYtUmRMa4/w-d-xo.html
Gotcha! I had to re-watch, but got it finally.
Awesome!
@@gkcs Hi Gaurav, can you make videos on the problem www.interviewbit.com/problems/matrix-median/ and system design of a voting system?
same here bro
"loor" dekhe amio hese more gelam. ki khilli. Btw really great video! Keep it up. :)
Loved this explanation, finally I fully understand how it works💡
Great explanation, love the intuition you give !!!
Amazing content, love your channel. I will share this video with my Junior college-mates :)
Don't you think the distance k should represent distance from 2 to 4 instead of 3 to 4? Otherwise, the equation itself will not be right. Moreover, when you say, in the end, that we would be 'k' short that means from the meeting point we would go back to 3 not 2, correct?
When ever we are choosing the slow pointer and fast pointer how fast they should move(can slow pointer move twice and fast pointer move three times .How we should decide.)
If you're going to move D nodes in cycles you're going to fall short of K nodes->Starting point of cycle in LL.
If you're going to move D nodes from head->Starting point of cycle in LL.
I got a very weak solution to this problem and somehow passed the challenge. So, what I did was : I changed the data value of each visited node to a particular number (say -25 for my case) and then checked the data of the next node that my loop encounters. If that is equal to -25, I conclude that there is a loop, else not. So, I remembered which nodes I had visited. I know that no number can fit as a "sentinel" value, but yes I tried and got results. HOWEVER, THIS IS NOT A REAL SOLUTION, JUST A BYPASS!
Hi Gaurav,
Alternative code for finding the starting node of linked list cycle. Please let me know if there are any issues.
if (loopExist) {
slwPtr = slwPtr.next;
List list = new ArrayList();
while (slwPtr != fstPtr) {
list.add(slwPtr);
slwPtr = slwPtr.next;
}
slwPtr = head;
while (slwPtr != fstPtr) {
if (list.contains(slwPtr)) {
return slwPtr;
}
slwPtr = slwPtr.next;
}
}
start = slwPtr;
return start;
Nice try but no.
No auxiliary space. That extra list used won't be allowed 🥺
Thanks for the mathematical proof but test case which includes a whole circular linked list requires slight change in finding the start of the loop ie. head
Such a nice explanation
D+K part was explained so nicely, thanks bhaiya
Keep up the stellar work! This is some really useful stuff!!
Alternative soln. Insert a unique key(say $) as you traverse the list. i.e. 0 - $ - 1 - $ - 2 - $ - 3 - $ - 4 - $ - 5 - $ until you find the next link of a node to point to $ which will also mark the beginning of the cycle.
Its a good idea if you can modify the list. Most of the interviewers don't allow that. :)
Excellent Explanation. Keep up the good work man...!
Great Explanation Sir
I got it! Very clear. Thank you!
Well explained! I didn't understand even though I read the solution but I totally got it with your video. Thank you :)
Glad to hear that 😁
Great video. Thanks for sharing!
Thanks 😊
it could be explained much easily:
1. the meeting point is at kth distance from loop entry(say 0th node)
2. basically if we go back (-k) from meeting point(k) we will get to the loop entry 0th node (k+(-k) = 0)
3. But the reality is that the meeting point k was met by doing 'c' cycles in loop which could be 1 cycle, 2 cycle.....c cycles
4. so if the meeting point was achieved after 1 cycle (assume for simplification) then 1*n-k will give us the loop entry(0th node) which is at a distance 'D' from the head
5 using the idea from step4, we move 'D' from meeting point(k) which will lead to loop entry(0th node)
Note: if we move further +k from loop entry after doing step-4 then we would have made a complete cycle +1n and will be again at meeting point
thnx buddy reall yhelpful
Nice explanation and logic deduction Gaurav_Sen..!!
Thank you for this video
U are really good at explaining things :)
Thanks!
when k = 0.. i.e loop is at the head.. you have to write extra code for this case.
Hi Gaurav
Thanks for the explanation.
Food for thought: Will this work ...
1. If Hare moves at 3x the speed and Tortoise moved 1x, for all the cases?
2. If the Hare runs at 3x and Tortoise moved at 2x the rate?
Food for thought: The gcd of the speeds must be 1 for a guaranteed meet :)
FINALLY GOT IT! THANKS
A little addition. The tortoise can never complete a cycle, so i will always be 0 in your equation
It can. Try a few test cases (odd even cycle length)
@@gkcs You might be assuming that at some point hare will jump over tortoise, which is not possible. The moment tortoise enters the cycle, hare would already be in the cycle and the distance between them will be less than a cycle. Since hare is faster, it'll catch the tortoise before it completes the cycle.
Try coming up with an example where tortoise completes a cycle and you'll know what I'm saying.
Unless I'm wrong. In that case your example would help me figure out why
Looks correct. Thanks for pointing this out. I'll try some other examples and verify if this is true 😁👍
great explanation. Written explanations out there are hard to understand. nice job!
thanks for explanation 😃
j < 2, will less than 2 tortoise can't go beyond two cycles in the loop without meeting hare.
I would have known the solution posted by @shlok singh
But your solution is smarter and shorter. I will keep this in mind.
At around 3:45 why does n need the c and i variables? Doesn't the tortoise never make it through a full cycle since the hair would intersect it before that happens?
+TrollkimNoah That might be true. But in the worst case, the tortoise and hare will meet at the start of the circle. Assume the whole graph to be a circular list.
Then the tortoise makes 1 revolution and the hare makes 2.
why can't we just mark the node when we visit them and when we reach them again that is the starting point of cycle. The complexity is same.
very nice explanation tank you
watching it in 2020... deeply explained. thanks !
Can you explain how to solve this question without using math in the interview? Because if we just writing these equations, the interviewer will think that we have mugged up the solution.
Sure, just remember these two steps:
1. Using a slow pointer and a fast pointer, find the "collision node"
2. Observe that the head node of linked list and collision node are equidistant from where loop begins. So,
move both pointers at 1x speed until they meet at loop start.
I agree I think the math bit is overkill for interview setting.
why do we only move the with difference of 1 step in slow and fast .?? why don't we move the slow pointer 1 step and fast pointer 3 or 4 steps ??
Thanks a lot Gaurav Bhai
is there any playlist of Interview Questions?
Thank You Sir.
Nice explanation
How do you compare nodes in a cyclic graph though? In the final solution it seems like you need to start a pointer at the head (hptr) and at the meeting point (mptr), move forward by 1 and then check if hptr == mptr.
how would the linked list implementation handle that? memory location or following the nodes?
Awesome video! Thank you for explaining so clearly
Why have you moved the D from 2nd node to 3rd node in the mid of video. It creates confusion
That was a great explanation. Thx so much for the help! :-)
Thanks buddy!
very well explained!
Thanks!
nice explaination
If we start the pointer at the start and one at the meeting point and move them by D+K then both end up at the same place? Can you be more specific around 8:05 to 8:12
We end up at the same place, which is the meeting point, if we move the pointers from the start and meeting point respectively.
The reason for this is D+K is where the meeting point is. Also, we see that D+K is a multiple of C, so any pointer inside the circle when moved by D+K nodes will revolve to the same place.
Thats because moving a distance divisible by C is like taking a few cycles around the loop.
Thank you so much! Your explanation is excellent! Really helps me a lot understanding the question!
Thanks!
Lovely explanation. Thank you
Can we find the starting point of the loop by using map in which we store the addresses of visited nodes until we find a node whose address has already been in the map.
No auxiliary space allowed.
Please use a dark marker.
Great Explaination! A dry run would really help though.
Thanks!
😆 😆 @Dev CS LOL
Awesome!
the equation that you figured out at 4:36 th sec that is N=C*(j-i). Does it mean that walking for some value of N
(where n is D+K+C(i)) steps is same as making few complete cyclic loops ?
Hi Gaurav, This was a great video. However, 1 thing which is still bugging me is , How every time ,Distance between starting node and the meeting point ends up to be equal to D i.e. if tortoise is moving D steps from head and hare is moving D steps from meeting point, they will definitely meet at the starting point ?
Have a look at the equations again. The meeting point and starting point are at a distance of D from the start of the loop.
I have a question. How are we going to compute the length D? Because if we dont we cannot stop the pointer P1.