Interview Question: Start of Loop in a Linked List
Vložit
- čas přidán 9. 04. 2017
- 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.com/questions/29...
#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!
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.
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!
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.
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 🙌
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❤
Love the energy of your teaching style!
It was hard wrap my head around this concept. Thank you for making this video and providing with a detailed explanation.
most important thing is how to act like you have seen this question for first time in an interview :))
Was stuck at this problem over a month, now i finally understand it, thanks a lot!!!
oh man, you are something else, fantastic explanation!!!
Finally someone explaining the math, thanks!
Your explanation deserves an extra like! Great video bro
Thanks!
Keep up the stellar work! This is some really useful stuff!!
So,this was a interesting questions. I found a solution after couple of years.😁
At last excellent explaination.
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!!
Exactly the explanation I wanted to know.
Thank you!
Great explanation, love the intuition you give !!!
Amazing content, love your channel. I will share this video with my Junior college-mates :)
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!
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.
atlast someone explained the algorithm with proof. amazing work.
Loved this explanation, finally I fully understand how it works💡
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!
Freakin awesome man ! thank you !
after watching it 3 times finally got it, now i can also explain it someone
Awesome video! Thank you for explaining so clearly
That was a great explanation. Thx so much for the help! :-)
Thank you, this is a new concept to me
The -K part really hits the point! Nice work!
FINALLY GOT IT! THANKS
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.
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 😁
Cool !! That was a great 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...
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.
watching it in 2020... deeply explained. thanks !
9:00 this was the missing link I was looking for!
Thanks Gaurav bhai for this explanation!!!
Great explanation!!
U are really good at explaining things :)
Thanks!
Excellent Explanation. Keep up the good work man...!
very well explained!
Thanks!
I got it! Very clear. Thank you!
Thanks a lot, this video was really helpful!!
Watch it twice to get the intuition :')
Awesome Explanation !!
Thanks a lot. This video help me understand the logic behind this.
Such a nice explanation
D+K part was explained so nicely, thanks bhaiya
Beautiful Explanation Brother !!!
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
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.
Great explanation with the equations
thankyou for this much needed 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?
Very good explanation. Thanks!
Thank you!
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
Nicely Explained! :)
Thanks!
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.
The first question they ask in any damn interview.
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.
Thank you so much! Your explanation is excellent! Really helps me a lot understanding the question!
Thanks!
Lovely explanation. Thank you
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
Great video. Thanks for sharing!
Thanks 😊
great work man. Keep doing. 👍👍👍👍👍👍👍
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.
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.
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 ?
Thank you Gaurav.
😁
"loor" dekhe amio hese more gelam. ki khilli. Btw really great video! Keep it up. :)
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?
I have a question. How are we going to compute the length D? Because if we dont we cannot stop the pointer P1.
Awesome explanation Gaurav!
finally understood the logic thanks
Thank you for this video
I would have known the solution posted by @shlok singh
But your solution is smarter and shorter. I will keep this in mind.
awesome explanation !!
Well explained :)
hey one thing that i dont understand is if we find out the node to which the last node of the linked list(here its 5) is pointing then also we can find the start of the loop. so can you help me with this.
How?
WOW, Thanks Gaurav
Great Explaination! A dry run would really help though.
Thanks!
😆 😆 @Dev CS LOL
Excellent explanation
Hey nice explanation :)
Thanks Reethika!
thanks for explanation 😃
great explanation. Written explanations out there are hard to understand. nice job!
Could someone please point me to the link of an implementation for this
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
Nice explanation and logic deduction Gaurav_Sen..!!
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.)
Great Explanation Sir
is there any playlist of Interview Questions?
Thanks buddy!
great explanation
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!
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: czcams.com/video/D-DYtUmRMa4/video.html
nice explanation bro.
Thanks a lot Gaurav Bhai
Thank You Sir.
Thanks !!
Thank you!
really nice bro ,keep teaching :)