Ad:

C Discussion Thread
Unsolved
Views: 1492

May 27th, 2006

finding the point where a loop begins

Expand Post »

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 :

C Syntax (Toggle Plain Text)
[1] ->[2] ->[3] ->[4] ->[5] 
            ^           |
            |           U
           [10]        [6]
            ^           |
            |           U
           [9]<- [8]<- [7]
[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);
}
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.

Similar Threads

how to find loop in C

dude543

Reputation Points: 12

Solved Threads: 0

Light Poster

Offline

26 posts
since Apr 2006

Permalink

May 27th, 2006

Re: finding the point where a loop begins

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.

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;
}
 //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;
}

Lerner

Reputation Points: 718

Solved Threads: 373

Nearly a Posting Maven

Offline

2,253 posts
since Jul 2005

Permalink

May 28th, 2006

Re: finding the point where a loop begins

> 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;

C Syntax (Toggle Plain Text)
while ( node && !node->seen ) {
  node->seen = true;
  node = node->next;
}
if ( node ) {
  // I'm the start of the loop
}
while ( node && !node->seen ) {
  node->seen = true;
  node = node->next;
}
if ( node ) {
  // I'm the start of the loop
}

Salem

Team Colleague

Reputation Points: 5862

Solved Threads: 950

Posting Sage

Offline

7,164 posts
since Dec 2005

Permalink

May 28th, 2006

Re: finding the point where a loop begins

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.

dude543

Reputation Points: 12

Solved Threads: 0

Light Poster

Offline

26 posts
since Apr 2006

Permalink

May 30th, 2006

Re: finding the point where a loop begins

Any more ideas ?

dude543

Reputation Points: 12

Solved Threads: 0

Light Poster

Offline

26 posts
since Apr 2006

Permalink

May 30th, 2006

Re: finding the point where a loop begins

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.

Salem

Team Colleague

Reputation Points: 5862

Solved Threads: 950

Posting Sage

Offline

7,164 posts
since Dec 2005

Permalink

May 30th, 2006

Re: finding the point where a loop begins

Quote 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.

dude543

Reputation Points: 12

Solved Threads: 0

Light Poster

Offline

26 posts
since Apr 2006

Permalink

May 30th, 2006

Re: finding the point where a loop begins

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.

Lerner

Reputation Points: 718

Solved Threads: 373

Nearly a Posting Maven

Offline

2,253 posts
since Jul 2005

Permalink

May 30th, 2006

Re: finding the point where a loop begins

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.

Rashakil Fol

Team Colleague

Reputation Points: 1135

Solved Threads: 173

Super Senior Demiposter

Offline

2,479 posts
since Jun 2005

Permalink

Jun 2nd, 2006

Re: finding the point where a loop begins

Thanks All.

dude543

Reputation Points: 12

Solved Threads: 0

Light Poster

Offline

26 posts
since Apr 2006

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C Forum Timeline: I need help!!

Next Thread in C Forum Timeline: remote monitoring software

DaniWeb Message

Cancel Changes

User Name
Password