3

I was asked in an interview to find if the single linked list has a loop. I have searched this SO and found few answers Interview question: How to detect a loop in a linked list? and I knew about those answers before but somehow I answered it different which I had in mind from my discussion with friends long time back, but I wasn't sure if the answer is correct. If try it myself it works as expected. Somehow the interviewer is not happy. Can someone clarify what is wrong in this ?

struct node {
int flag;
struct node *next;
}

My idea here is not to use two pointers and hop variantly but to use single pointer and traverse each node e.g:

node =  node->next;

Only this I would do is set the flag variable to 1 when ever I traverse the node and check each time e.g

if (node->flag)
{ 
  return TRUE; // implies list is a loop
}
else{
   node->flag = 1;
}

Other than efficiency, what is wrong in this approach ?

3
  • See stackoverflow.com/questions/34249/… and the questions linked to there for other approaches.
    – user395760
    Dec 29, 2011 at 10:53
  • @delnan : Yes , I went through this question also. I mostly covered all the related questions in SO. However, my question is to understand what is wrong in this approach.
    – dicaprio
    Dec 29, 2011 at 10:55
  • These kind of questions only shows if you've read these kind of questions before and are familiar with the answer. I would never use it as a measure on how skilled a developer are.
    – onemasse
    Dec 29, 2011 at 13:32

5 Answers 5

3

You need additional data (flag) to store for each list item. So your approach needs O(N) additional memory, while approach with two pointers needs only O(1) memory.

So you approach is not memory efficient.

2
  • Good answer, but the example in the question also requires the list structure to be modified which is probably more relevant.
    – JeremyP
    Dec 29, 2011 at 13:23
  • @JeremyP, interview questions of this type is aimed to show knowledge of algorithms, data structures, complexity, etc. So I think, more relevant is memory efficiency, regardless how this memory is used.
    – werewindle
    Dec 29, 2011 at 13:44
2

Your approach is even more efficient but relies on the fact that you may modify the list representation. When asked the same question I gave the same solution but the interviewer told me I am not allowed to modify the list in any way.

2
  • So the approach is not wrong then, if you already know this approach earlier then its not something i found myself :). Is there a algorithm or somebody already named it ?
    – dicaprio
    Dec 29, 2011 at 10:31
  • Honestly saying I just invented it on the spot :) Dec 29, 2011 at 10:38
1

You are using an extra integer variable flag and say if the sizeof(int) in your machine is 4 bytes and say you have 100,000 nodes in the linked-list, then you will end up using 400,000 bytes more. That will be approximately 390M/.38G

To reset the flag for all the nodes in the linked-list, even though it is O(n), you'll have to traverse all the 100,000 nodes. Its an overhead.

Now, if you compare your flag based solution with the 2-variable solution, then it is almost the same computational time but 2-variable solution is considered very memory efficient as it does not use 390M of memory to identify the loop!

6
  • After all linked list is used to store the data which can be of some size, I don't disagree but that cannot be the reason I think so. Also, i'll be setting flag as and when I traverse the node how is it overhead.
    – dicaprio
    Dec 29, 2011 at 10:36
  • Efficiency I agree , that's what I mentioned.
    – dicaprio
    Dec 29, 2011 at 10:38
  • @dicaprio There is nothing wrong with the flag approach. It will work! There is no doubt about that. But compare to the other solution(s), this may not be very efficient. And, the approaches are compared based on efficiency - memory, computation and many other factors! :) Dec 29, 2011 at 11:01
  • @dicaprio Are you not finding my answer reasonable?! Dec 29, 2011 at 22:44
  • As I said , I don't disagree with your comments; perfectly reasonable with regards to efficiency, which I already told the interviewer, his question was not specific.
    – dicaprio
    Dec 30, 2011 at 5:31
1

Your answer is not wrong, rather instead of using two pointers, it makes use of just one pointer. But giving this answer for the interview question you over looking one basic premise.

You are generally not supposed to alter the data structure of the problem which you are given until it is absolutely necessary to do so. Consider it from this point of view.

What if it's not a linked list but an application that the company has developed and they need you to find out if a particular thing stands true for that application or not. In this case they don't expect you to change the application code(as that is impractical unless unavoidable) but would like you to work around with what you have got.

Because of this your interviewer was not happy with the answer. You can always give this answer in addition to the other answer, but not as your answer of choice.

1

Perhaps Hare and Turtle would work. The Turtle interates through the list normally, one item at a time, while the Hare goes twice as fast, two items at a time. If the Hare passes the Turtle, there is a loop.

Edit: I see this suggestion is already here, and that it has already been rejected by the OP, in his comments.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.