This is part of my series on interview questions, so welcome aboard!
This installment deals with a common question about linked lists — how do we detect when one has a loop?
Linked Lists
Linked lists are one of the most simple data structures and most aspiring programmers learn them early on. But for completeness' sake let's cover that ground.
A linked list is a sequence of nodes. Each node contains a piece of data and a reference to the next node in the list. Graphically it looks like this
Loopy Linked Lists
It's possible, though, that a node in a linked list might point to a previous element in the list. This is bad for many reasons, not the least of which is that any loop which iterates over all the nodes in the list by accessing the next node will never terminate.
So, it becomes important to detect when linked lists have loops. Here's what one such errant linked list looks like.
The Easy Solution
The easy solution is to keep track of every node seen so far and check if the current node is in that list. Here's a very simple linked list implementation in Ruby.
attr_accessor :data, :next
def initialize(data = nil)
@data = data
@next = nil
end
end
Here is the simple solution for detecting loops using the above implementation
seen = []
until node.next.nil? do
return true if seen.include? node
seen << node
node = node.next
end
false
end
This solution is workable but sub-optimal (surprise!). This has O(n2) complexity in CPU and O(n) complexity in memory, but a solution with O(n) complexity in CPU and O(1) complexity in memory is possible. In fact, this question is usually posed to preclude the above solution.
The Tortoise and the Hare
The better solution involves a bit of mathematical thinking. If there is a loop then that means any iterator, no matter how many steps it takes per iteration, must hit the offending node.
So, if we have two iterators, one of which has a length that is a multiple of the other, they'll eventually land on the same node. The usual solution is to have one iterator advance one at a time ("the tortoise") and a second iterator advance two at a time ("the hare").
That algorithm looks like this
slow = node
fast = node
until slow.next.nil? or fast.next.nil? do
slow = slow.next
fast = fast.next.next
return true if (slow == fast)
end
false
end
More Questions
Assuming you answer the above correctly and quickly the interviewer will probably follow up with some related questions. How do you fix the linked list when you detect a loop? What is the linked list has multiple loops? How do you determine the size of the loop?
I'll leave you to ponder these questions. Cheers!
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.
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.
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.
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).
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.
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).
Jim,
1) I never said it ran in constant time. I said it took constant memory, which is true.
2) has_loop? 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
[…] question suffers from the same problems that the reversing linked lists in that you probably either know the solution or you […]
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.
Shaneal,
You’re right.
In the ‘easy solution’ you also first need to check for a list that has 2 nodes that are in loop.