finding the point where a loop begins

Please support our C advertiser: Programming Forums - DaniWeb Sister Site
Reply

Join Date: Apr 2006
Posts: 26
Reputation: dude543 is an unknown quantity at this point 
Solved Threads: 0
dude543 dude543 is offline Offline
Light Poster

finding the point where a loop begins

 
0
  #1
May 27th, 2006
This is/was an interview question I got two weeks ago.
Find where the loop begins in simple linked list.
I hope this figure will help understand what I mean :
  1. [1] ->[2] ->[3] ->[4] ->[5]
  2. ^ |
  3. | U
  4. [10] [6]
  5. ^ |
  6. | U
  7. [9]<- [8]<- [7]


If not the figure take a look at this where I make the error.
  1.  
  2. int main(void)
  3. {
  4. struct list
  5. {
  6. int val;
  7. struct list *pnext;
  8. } *phead, *plast, *pptr, *ploop, **pptmp, *p1, *p2;
  9. int i;
  10. phead = NULL;
  11. pptmp = &phead;
  12. for ( i = 1 ; i <= 10 ; ++i )
  13. {
  14. plast = (*pptmp) = malloc(sizeof(*phead)) ;
  15. (*pptmp)->val = i;
  16. (*pptmp)->pnext = NULL;
  17. if ( i == 3 )
  18. ploop = (*pptmp);
  19. pptmp = &(*pptmp)->pnext;
  20. }
  21.  
  22.  
  23. /* Doing the error !!!!!!!!!! */
  24. plast->pnext = ploop;
  25.  
  26.  
  27. /* Trying to find the error. e.g. cell 10 */
  28. /* Not its value of course but its address */
  29. getchar();
  30. return(0);
  31. }



My solutions :
1) If we have a filed in the struct which his value
is known to us. We can loop throw the list checking
if it is the value known to us, else chaning it to something else.
When we encounter the changed value, the previous cell
is the beging of the loop.
2) Allocating an array of pointers. Looping throw the list
and adding its address to the array. Every time we had
a new address we check if it is not in the array.
If it is in the array the previous cell is the beging
of the loop.

Anybody has other solutions ?
Thanks in advance.


Reply With Quote Quick reply to this message  
Join Date: Jul 2005
Posts: 1,757
Reputation: Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all 
Solved Threads: 283
Lerner Lerner is offline Offline
Posting Virtuoso

Re: finding the point where a loop begins

 
0
  #2
May 27th, 2006
To me node three is the start of the loop, not node two or node 10, both of which point to node three. I agree that node 10 is where the error is, if you are looking for the error, but it isn't where the loop begins, IMO.

In any case, I think the second protocol you describe seems most likely to succeed, though I'm not sure the code you posted reproduces the loop you drew. In particular I question why you made pptemp a pointer to pointer instead of just a pointer. The following makes more sense to me, though I admit I have not compiled either your version or mine.

  1. //declare node struct to create list from
  2. struct list
  3. {
  4. int val;
  5. list *pnext;
  6. }
  7.  
  8. int main()
  9. {
  10. list *phead, *plast, *ploop, *pptmp; //pointers to use
  11. int i;
  12.  
  13. for ( i = 1 ; i <= 10 ; ++i ) //create total of 10 list objects
  14. {
  15. //declare memory for a new list object
  16. pptmp = new list ;
  17.  
  18. //initialize each objects member variables
  19. pptmp->val = i;
  20. pptmp->pnext = NULL;
  21.  
  22. //keep track of the desired place to create the loop
  23. if ( i == 3 )
  24. ploop = pptmp;
  25.  
  26. //create the list
  27. if(i == 1)
  28. plast = phead = pptemp;
  29. else
  30. {
  31. plast->next = pptmp;
  32. plast = plast->pnext;
  33. }
  34. }
  35.  
  36.  
  37. /* Doing the error !!!!!!!!!! */
  38. /*create the loop*/
  39. plast->pnext = ploop;
  40.  
  41.  
  42. /* Trying to find the error. e.g. cell 10 */
  43. /* Not its value of course but its address */
  44. getchar();
  45. return 0;
  46. }
Reply With Quote Quick reply to this message  
Join Date: Dec 2005
Posts: 5,850
Reputation: Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute 
Solved Threads: 751
Team Colleague
Salem's Avatar
Salem Salem is offline Offline
Void main'ers are DOOMed

Re: finding the point where a loop begins

 
0
  #3
May 28th, 2006
> 1) If we have a filed in the struct which his value is known to us
Seems good to me - no extra storage needed, like working out how to allocate a big enough array of pointers. Also, checking time increases with the length of the list.

Call the new member say bool seen;
  1. while ( node && !node->seen ) {
  2. node->seen = true;
  3. node = node->next;
  4. }
  5. if ( node ) {
  6. // I'm the start of the loop
  7. }
Reply With Quote Quick reply to this message  
Join Date: Apr 2006
Posts: 26
Reputation: dude543 is an unknown quantity at this point 
Solved Threads: 0
dude543 dude543 is offline Offline
Light Poster

Re: finding the point where a loop begins

 
0
  #4
May 28th, 2006
Thank you guys, Lerner and Salem.
But I wasnt interstead in the way to implenent the code.
But rather, other ideas then mine to find node 10.
Reply With Quote Quick reply to this message  
Join Date: Apr 2006
Posts: 26
Reputation: dude543 is an unknown quantity at this point 
Solved Threads: 0
dude543 dude543 is offline Offline
Light Poster

Re: finding the point where a loop begins

 
0
  #5
May 30th, 2006
Any more ideas ?
Reply With Quote Quick reply to this message  
Join Date: Dec 2005
Posts: 5,850
Reputation: Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute 
Solved Threads: 751
Team Colleague
Salem's Avatar
Salem Salem is offline Offline
Void main'ers are DOOMed

Re: finding the point where a loop begins

 
0
  #6
May 30th, 2006
How many more ideas do you want?

You already have two perfectly feasible answers.

Or is this a game of "guess which answer the interviewer" decided was the right approach?

How about
- a solution based on sets
- a solution based on hashes
- a solution based on strings

Pick any other data structure you like which has some concept of "membership" and try that.
Reply With Quote Quick reply to this message  
Join Date: Apr 2006
Posts: 26
Reputation: dude543 is an unknown quantity at this point 
Solved Threads: 0
dude543 dude543 is offline Offline
Light Poster

Re: finding the point where a loop begins

 
0
  #7
May 30th, 2006
Originally Posted by Salem
How many more ideas do you want?
I apologize for upsetting you.
Sorry.

But maybe someone else will have a better solution.
Reply With Quote Quick reply to this message  
Join Date: Jul 2005
Posts: 1,757
Reputation: Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all 
Solved Threads: 283
Lerner Lerner is offline Offline
Posting Virtuoso

Re: finding the point where a loop begins

 
1
  #8
May 30th, 2006
I think "better" is in the eye of the beholder. For example: is it better to be short and obfuscated or lenthy and perfectly readable. Answer: Depends on what constraints you have. If memory is at a premium it's better to be short and obfuscated. If not, it's better to lenthy and perfectly readable. In this setting I would choose an approach I could justify and be able to explain clearly why I'm doing what I'm doing. That way even if I don't happen to hit the format "desired", if there is a format desired, I can defend my approach. Often it's not whether you get the right answer but how do approach the problem, how do you communicate your approach, and then if it isn't working out for you alone, someone else can help you come up with a workable solution, a more palatable solution, a "better" solution.
Reply With Quote Quick reply to this message  
Join Date: Jun 2005
Posts: 2,055
Reputation: Rashakil Fol is just really nice Rashakil Fol is just really nice Rashakil Fol is just really nice Rashakil Fol is just really nice 
Solved Threads: 139
Team Colleague
Rashakil Fol's Avatar
Rashakil Fol Rashakil Fol is offline Offline
Super Senior Demiposter

Re: finding the point where a loop begins

 
3
  #9
May 30th, 2006
I think a good solution is to check if you've reached a node the second time only on nodes whose distance from the beginning is a power of two. This lets you find a loop in linear time. From this you can also use divide and conquer to find the starting point of the loop in linear time.

Using a hash would also be linear time (usually), but probably slower.
All my posts may be redistributed under the GNU Free Documentation License.
Reply With Quote Quick reply to this message  
Join Date: Apr 2006
Posts: 26
Reputation: dude543 is an unknown quantity at this point 
Solved Threads: 0
dude543 dude543 is offline Offline
Light Poster

Re: finding the point where a loop begins

 
0
  #10
Jun 2nd, 2006
Thanks All.
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:



Similar Threads
Other Threads in the C Forum


Views: 1304 | Replies: 9
Thread Tools Search this Thread



Tag cloud for C
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC