A (human) index that likes to code
Also drinks way too much coffee
Published Jun 19, 2019 12:00
Well; I told you - I would have had quite an experience and be able to make a blog post today.
I wanted to talk about one of the problems that was presented to me during the interview:
How do you figure out if a linked list is incorrectly looping?
Incorrect Looped Link List | Source: geeksforgeeks.com
There are so many possible answers to this solution. I came up with a solution which involves using a
set object to store all the pointers, and check with the set to ensure that there are no duplicates. It’s a really bad algorithm, but I said it to answer the question. The interviewer’s (his) solution was more interesting, and is something that I haven’t encountered before - do keep in mind that I don’t indulge myself into algorithms in my diploma course and free time, because I’m more focused in actually trying to do something than to do it well.
Anyway, his algorithm was like this:
Ptr2point at the same element;
Ptr2will advance two steps per iteration, and
Ptr1will advance one step per iteration;
NULL, then the algorithm proves that there are no loops in the linked list;
Ptr2will eventually collide in the loop, if neither pointer has hit
NULL, it signifies that there is a loop in the linked list.
This blew my mind a little bit, and after hitting
geeksforgeeks.org, this 5 step proceedure I described was actually one part of the Flyod’s Cycle detection algorithm (Flyod’s Cycle detection algorithm is completed in the subsequent steps). What really displaced what little intellectual points I had left in me was the next part:
How do you resolve the incorrectly looping linked list?
His algorithm was like this:
Ptr2back to the beginning of the linked list;
Ptr2go through the link list at the same speed, at one step per iteration;
You may ask: wait, why is Step 3 true?
x number of nodes within the linked list. This menas that
2x number of nodes before it collides with
Ptr1. What this also implies, is that if you were to let
Ptr1 travel another
x number of nodes, it will collide with
Ptr2 again, as
x + x = 2x, which is the same distance
Ptr2 has travelled. Now, think about the distances travelled by
Ptr1: it needed
x number of nodes to collide with
Ptr2 from the start of the linked list, and, by travelling another
x number of nodes, it collides with
Ptr2 again. This implies that if I were to have another pointer, called
Ptr3, which travels at the same speed as
Ptr1 starting at the collision position and
Ptr3 starting at the start, then
Ptr3 will collide at the same collision point. Meaning: the first collision point between
Ptr3 will signify the problematic node. If we were to make
Ptr1 travel through the whole loop again, checking the next node pointed by
Ptr3, we can find the culprit causing the loop in the linked list, and route it to null.
In the above chunk of text, you realize that
Ptr2 is only used to prove that
Ptr3’s first collision is the point where the loop begins. Hence, we can use
Ptr2 instead of
Ptr3, saving us one memory location.
That’s was interesting ain’t it?
One more thing I learned during the interview is the existance of a trie:
A trie | Source: Wikipedia
Which is helpful in search suggestions, especially if you have hundreds of thousands of such suggestions.
Well, I’ll probably not get what I interviewed for; but that’s fine. The experience taught me how it’s like to be interviewed for my technical skills; and helped me come up with possible strategies to try before my next interview.
Good luck for your own interviews, if they’re coming up!