20bits: Interview Questions: Loops in Linked Lists | 20bits
vidarh
· 1 year ago
I've asked a number of people that question over the years, and I've actually yet to meet someone who's given the "tortoise and the hare" version without a _lot_ of prompting and hints. It's only a good interview question if you use it to engage in a conversation, because frankly a lot of the people I've asked it that have been unable to answer have been fantastic developers. However it does give you an idea about how people react in the face of a tough problem - some people clam up and seems like they've just been defeated in personal combat, while others will instantly get interested and start throwing out ideas, and ask probing questions to try to figure it out.
Jesse
· 1 year ago
Vidar,
The first time I was asked this question I was unable to give that answer, too. I don't think it's a very good question, personally.
Good interview questions have multiple levels or some sort of path the interviewee can be lead down. You either know this solution or you don't. I didn't, and that's probably just because I've never had need to know if there's a loop in a linked list.
vidarh
· 1 year ago
Jesse,
It does/can have a path depending on how it's asked. There are many ways of finding the loops, and and generally most developers I've worked with can come up with several of them off the top of their head. The problem is when you specifically ask for a space efficient one.
When I've used this question I've always been careful to state up front that I care more about people telling me how they're thinking about it than the actual answer. With some prompting and discussion most good candidates can throw out good ideas, and many of them get pretty close.
I agree it's not a good question if it's asked in its most precise form and the interviewer expects the interviewee to come up with the good answer entirely on their own, though.
The first time I heard the problem was actually in an interview, and I did figure it out, but I also went through a number of other solutions first, and what ultimately got me on the right track was reasoning more or less like this:
- There are two possible situations: There is a loop or there's not a loop. If there's not a loop you'll eventually hit the end by following the list, so you only need to worry about what happens if you don't reach the end. - Well, the most immediate thing that happens if you don't reach the end is that you revisit old nodes. This is obvious to most people, hence the number of people that suggest keeping a list of all visited nodes as one of the first suggestions. - Whats your ideal scenario then if you can't keep all the nodes? It is to know that you have previously seen the node that marks the start of the loop. - If you can't know what node is the start of the loop, is it ok to know _any_ node in the loop? Yes, because if you keep iterating you'll eventually hit it. - That reduces the problem to finding a node that is guaranteed to be inside the loop if there is one.
- At this point I was stuck for a while, but the logical next step is to consider if you can divide the problem further. Well, you can try to divide the list. But you don't know how long it is. However, does it matter? - It matters if you don't step into the loop. If you don't move your marker into the loop, you'll never see it when iterating over the list. - How can you make sure you eventually get into the loop? You can keep moving the marker. But how do you ensure you see the marker when iterating over the list? You make sure you move the marker "slow enough", in other words slower than the speed you are iterating over the list with.
It is interesting to look at some of the methods used to solve it more than the solution: - Divide the problem if possible. In this case the case with a loop and without. The case without a loop is trivial. - Identify the consequences of the goal. In this case: you see old nodes again. - Reformulate that as a goal. In this case: Find a way to recognize an old node. - Simplify the goal. In this case: Determine whether a specific node is needed, or if any or all nodes are needed. In this case, any node in the loop is what you need to find. - Divide the problem (or at least try). In this case: What happens if you try to consider part of the list? In this case that doesn't in itself work so well, but it is a good step towards the realization that you don't need to solve the problem for each part the first time you divide, or even to know how to split it in two - you just need to continue to get closer to the solution. Once you reach that realization you're on the home stretch with this problem, and the rest is just details.
Signs of understanding how to divide and conquer, and analytically approach a problem in ways that drive you towards a reasonable solution is what I look for when I ask a question like this, or similar ones. If someone provides the answer immediately it doesn't tell me anything, and I'd have to find something else to ask.
Jesse
· 1 year ago
If I want to see how people think I ask them questions with many moving parts rather than a very small question like this. In my mind questions like this are designed to see whether the person has a basic level of programming competency or not, but since the exercise has an "ah-ha!" solution it's not very fair.
In that vein asking how to reverse a linked list is better if you're going to be asking questions about linked lists.
In general if I'm not testing basic competency I want real-world examples. So, if I were hell-bent on asking about cycle detection I'd think of a scenario where cycle detection is an important part of the system (e.g., a question about dependency trees).
Bruno
· 1 year ago
That's a very cute solution, the hare will eventually get to the end or catch the tortoise in at best n, at worst 1.5*n iterations.
Jim
· 1 year ago
It's O(n) time, not O(1) time. Also, your tortoise/hare program will die on nil values (e.g. if fast.next.next is nil).
Jesse
· 1 year ago
Jim,
1) I never said it ran in constant time. I said it took constant memory, which is true.
2) <tt>has_loop?</tt> expects a Node object to be passed in, so it should never be nil. In a real-world situation I'd of course have exception handling, but the examples were meant to be illustrative rather than complete.
Cheers, Jesse
Shaneal Manek
· 1 year ago
I believe you have an error in your analysis of the 'easy solution.'
It runs in O(n^2) time, not O(n). I think since you are using an array to store the nodes already seen,for an n item list it will take take a total of n + (n-1) + (n-2) + ... + 1 operations, to determine if a given node has already been seen.
This is an arithmetic progression sums to n*(n+1)/2 = 1/2*(n^2+n) which is O(n^2) complexity.
I believe you can get an O(n) time complexity if you use a hash table to store the nodes already seen instead of an array.
Jesse
· 1 year ago
Shaneal,
You're right.
jc
· 1 year ago
In the 'easy solution' you also first need to check for a list that has 2 nodes that are in loop.
All Comments
The first time I was asked this question I was unable to give that answer, too. I don't think it's a very good question, personally.
Good interview questions have multiple levels or some sort of path the interviewee can be lead down. You either know this solution or you don't. I didn't, and that's probably just because I've never had need to know if there's a loop in a linked list.
It does/can have a path depending on how it's asked. There are many ways of finding the loops, and and generally most developers I've worked with can come up with several of them off the top of their head. The problem is when you specifically ask for a space efficient one.
When I've used this question I've always been careful to state up front that I care more about people telling me how they're thinking about it than the actual answer. With some prompting and discussion most good candidates can throw out good ideas, and many of them get pretty close.
I agree it's not a good question if it's asked in its most precise form and the interviewer expects the interviewee to come up with the good answer entirely on their own, though.
The first time I heard the problem was actually in an interview, and I did figure it out, but I also went through a number of other solutions first, and what ultimately got me on the right track was reasoning more or less like this:
- There are two possible situations: There is a loop or there's not a loop. If there's not a loop you'll eventually hit the end by following the list, so you only need to worry about what happens if you don't reach the end.
- Well, the most immediate thing that happens if you don't reach the end is that you revisit old nodes. This is obvious to most people, hence the number of people that suggest keeping a list of all visited nodes as one of the first suggestions.
- Whats your ideal scenario then if you can't keep all the nodes? It is to know that you have previously seen the node that marks the start of the loop.
- If you can't know what node is the start of the loop, is it ok to know _any_ node in the loop? Yes, because if you keep iterating you'll eventually hit it.
- That reduces the problem to finding a node that is guaranteed to be inside the loop if there is one.
- At this point I was stuck for a while, but the logical next step is to consider if you can divide the problem further. Well, you can try to divide the list. But you don't know how long it is. However, does it matter?
- It matters if you don't step into the loop. If you don't move your marker into the loop, you'll never see it when iterating over the list.
- How can you make sure you eventually get into the loop? You can keep moving the marker. But how do you ensure you see the marker when iterating over the list? You make sure you move the marker "slow enough", in other words slower than the speed you are iterating over the list with.
It is interesting to look at some of the methods used to solve it more than the solution:
- Divide the problem if possible. In this case the case with a loop and without. The case without a loop is trivial.
- Identify the consequences of the goal. In this case: you see old nodes again.
- Reformulate that as a goal. In this case: Find a way to recognize an old node.
- Simplify the goal. In this case: Determine whether a specific node is needed, or if any or all nodes are needed. In this case, any node in the loop is what you need to find.
- Divide the problem (or at least try). In this case: What happens if you try to consider part of the list? In this case that doesn't in itself work so well, but it is a good step towards the realization that you don't need to solve the problem for each part the first time you divide, or even to know how to split it in two - you just need to continue to get closer to the solution. Once you reach that realization you're on the home stretch with this problem, and the rest is just details.
Signs of understanding how to divide and conquer, and analytically approach a problem in ways that drive you towards a reasonable solution is what I look for when I ask a question like this, or similar ones. If someone provides the answer immediately it doesn't tell me anything, and I'd have to find something else to ask.
In that vein asking how to reverse a linked list is better if you're going to be asking questions about linked lists.
In general if I'm not testing basic competency I want real-world examples. So, if I were hell-bent on asking about cycle detection I'd think of a scenario where cycle detection is an important part of the system (e.g., a question about dependency trees).
1) I never said it ran in constant time. I said it took constant memory, which is true.
2) <tt>has_loop?</tt> expects a Node object to be passed in, so it should never be nil. In a real-world situation I'd of course have exception handling, but the examples were meant to be illustrative rather than complete.
Cheers,
Jesse
It runs in O(n^2) time, not O(n). I think since you are using an array to store the nodes already seen,for an n item list it will take take a total of
n + (n-1) + (n-2) + ... + 1 operations,
to determine if a given node has already been seen.
This is an arithmetic progression sums to n*(n+1)/2 = 1/2*(n^2+n) which is O(n^2) complexity.
I believe you can get an O(n) time complexity if you use a hash table to store the nodes already seen instead of an array.
You're right.