| | |
finding the point where a loop begins
Please support our C advertiser: Programming Forums - DaniWeb Sister Site
![]() |
•
•
Join Date: Apr 2006
Posts: 26
Reputation:
Solved Threads: 0
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 :
If not the figure take a look at this where I make the error.
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.
Find where the loop begins in simple linked list.
I hope this figure will help understand what I mean :
C Syntax (Toggle Plain Text)
[1] ->[2] ->[3] ->[4] ->[5] ^ | | U [10] [6] ^ | | U [9]<- [8]<- [7]
If not the figure take a look at this where I make the error.
C Syntax (Toggle Plain Text)
int main(void) { struct list { int val; struct list *pnext; } *phead, *plast, *pptr, *ploop, **pptmp, *p1, *p2; int i; phead = NULL; pptmp = &phead; for ( i = 1 ; i <= 10 ; ++i ) { plast = (*pptmp) = malloc(sizeof(*phead)) ; (*pptmp)->val = i; (*pptmp)->pnext = NULL; if ( i == 3 ) ploop = (*pptmp); pptmp = &(*pptmp)->pnext; } /* Doing the error !!!!!!!!!! */ plast->pnext = ploop; /* Trying to find the error. e.g. cell 10 */ /* Not its value of course but its address */ getchar(); return(0); }
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.
•
•
Join Date: Jul 2005
Posts: 1,757
Reputation:
Solved Threads: 283
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.
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.
C Syntax (Toggle Plain Text)
//declare node struct to create list from struct list { int val; list *pnext; } int main() { list *phead, *plast, *ploop, *pptmp; //pointers to use int i; for ( i = 1 ; i <= 10 ; ++i ) //create total of 10 list objects { //declare memory for a new list object pptmp = new list ; //initialize each objects member variables pptmp->val = i; pptmp->pnext = NULL; //keep track of the desired place to create the loop if ( i == 3 ) ploop = pptmp; //create the list if(i == 1) plast = phead = pptemp; else { plast->next = pptmp; plast = plast->pnext; } } /* Doing the error !!!!!!!!!! */ /*create the loop*/ plast->pnext = ploop; /* Trying to find the error. e.g. cell 10 */ /* Not its value of course but its address */ getchar(); return 0; }
> 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
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; C Syntax (Toggle Plain Text)
while ( node && !node->seen ) { node->seen = true; node = node->next; } if ( node ) { // I'm the start of the loop }
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.
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.
•
•
Join Date: Jul 2005
Posts: 1,757
Reputation:
Solved Threads: 283
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.
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.
Using a hash would also be linear time (usually), but probably slower.
All my posts may be redistributed under the GNU Free Documentation License.
![]() |
Similar Threads
- how to find loop (C)
Other Threads in the C Forum
- Previous Thread: I need help!!
- Next Thread: remote monitoring software
Views: 1304 | Replies: 9
| Thread Tools | Search this Thread |
Tag cloud for C
#include adobe ansi api array arrays asterisks binarysearch calculate centimeter char command convert copyimagefile cprogramme creafecopyofanytypeoffileinc csyntax directory dynamic fflush file fork forloop framework frequency functions getlasterror givemetehcodez grade graphics gtkgcurlcompiling hacking hardware highest homework inches incrementoperators kernel km lazy linked linkedlist linux linuxsegmentationfault list lists locate logical_drives looping loopinsideloop. match matrix microsoft motherboard multi mysql number opendocumentformat opensource owf pattern pdf performance pointer posix problem probleminc process program programming radix recursion recv repetition research scanf scripting segmentationfault sequential shape socket socketprograming spoonfeeding stack standard string strings structures student systemcall testautomation threads turboc unix user variable voidmain() wab win32 windows.h






