a fun algorithms problem

eLiu

Diamond Member
Jun 4, 2001
6,407
1
0
Here's an interesting problem for you guys. Before anyone starts, this is *not* homework; I first solved it half a year ago or so.

The setup:
I'll give you a pointer to the head node of a linked list. Suppose the list is set up as in C, so you can access the pointer value directly if you want to. (i.e. the implementation is not hidden as in Java)

The problem is then to tell me if the linked list has a cycle. A cycle means that at some point, a node points to a previous node. This means that the "last" node points to say itself, the first node, the fifth node, or wherever. (Point is that it is not just the last node pointing to the first node).

Notes:
>You DO NOT know how long the list is.
>You cannot edit the list--no changing pointers for example. I spent years making the list, and there is not enough HD space on earth to make a copy. Yeah... right.
>It is a singly-linked list.



I'll go ahead and give you the worst solution:
Use a pointer to march through the list and build an array of pointer values as you go. At each step, compare the current value to the entire array to see if you've been there before.

You can do better than that.

Edit: if this is a well-known problem, don't share the answer if you've seen it before. I'm not a CS major so I have no idea :)
 

eLiu

Diamond Member
Jun 4, 2001
6,407
1
0
Originally posted by: tfinch2
Reverse the linked-list. If the last element is the same as the first element, there is a cycle. Then reverse the list again to return it back to the way it was.

I don't see how you can reverse the list if you don't know how long it is...

Edit: I mean to reverse, you would first have to figure out where the last element is. But if you figure that out, then the problem is trivial because there's a cycle if last.next != null.
 

linkgoron

Platinum Member
Mar 9, 2005
2,286
810
136
well this is kind of dumb,

but theoretically you can make something like a x node that every node you're at you change your NEXT to, and if you ever get to X it means that it's a never ending list.

as


A->b->c->d->e->f->(back to)c

so you need two pointers. and one you put to the next, and then you change the current to the x node and then make the current equal to the next.

THIS IS kind of dumb.
 

TuxDave

Lifer
Oct 8, 2002
10,572
3
71
I think the point is if you get a linked like

1-->2-->3-->4-->5-->3(cycle detected)-->4..... The cycle doesn't have to point back the the first element.
 

DaveSimmons

Elite Member
Aug 12, 2001
40,730
670
126
So this is a singly-linked list, and you're only given the first element?

Is it true that the last element in the list may not actually be reachable if there is a cycle? (ie. element 20 of 100 could have the link starting the cycle)?

Are we allowed to alter list elements or their pointers?
 

eLiu

Diamond Member
Jun 4, 2001
6,407
1
0
Originally posted by: DaveSimmons
So this is a singly-linked list, and you're only given the first element?
Yes.

Is it true that the last element in the list may not actually be reachable if there is a cycle? (ie. element 20 of 100 could have the link starting the cycle)?

Yes, that is true. I was having a hard time expressing that idea in the original post. But I think you and TuxDave clarified, thanks :)

Are we allowed to alter list elements or their pointers?

That's a key point that I forgot: you cannot modify the list.

Edit: linkgoron, you can't edit the list so that won't work. Sorry for not mentioning this earlier. If you could edit the list, I don't think your solution is dumb at all... but maybe I don't know what I'm talking about, haha :)
 

DaveSimmons

Elite Member
Aug 12, 2001
40,730
670
126
Since you can't alter the elements, my lazy brain can't think of anything better than using a hash table of the pointers, which is faster than a linear array search per element but uses even more memory :(
 

shuttleboi

Senior member
Jul 5, 2004
669
0
0
There is a well-known solution to this. If you google "programming interview questions", you will undoubtedly find the answer.
 

DaveSimmons

Elite Member
Aug 12, 2001
40,730
670
126
Originally posted by: shuttleboi
There is a well-known solution to this. If you google "programming interview questions", you will undoubtedly find the answer.
Sure, but where's the fun in looking up the answer?
 

Chronoshock

Diamond Member
Jul 6, 2004
4,860
1
81
Given a list of n elements:

Iterate through the linked list constructing an adjacency graph. This takes O(n) time, O(n^2) space
Use elimination to determine if the matrix is singular. This takes O(n) time. I forget if there are faster tests for singularity but its quick enough.
Overall time: O(n)
 

her209

No Lifer
Oct 11, 2000
56,352
11
0
Originally posted by: Chronoshock
Given a list of n elements:

Iterate through the linked list constructing an adjacency graph. This takes O(n) time, O(n^2) space
Use elimination to determine if the matrix is singular. This takes O(n) time. I forget if there are faster tests for singularity but its quick enough.
Overall time: O(n)
I don't think you know how long the list is.
 

Chronoshock

Diamond Member
Jul 6, 2004
4,860
1
81
Originally posted by: her209
Originally posted by: Chronoshock
Given a list of n elements:

Iterate through the linked list constructing an adjacency graph. This takes O(n) time, O(n^2) space
Use elimination to determine if the matrix is singular. This takes O(n) time. I forget if there are faster tests for singularity but its quick enough.
Overall time: O(n)
I don't think you know how long the list is.

You don't have to know how long it is, just construct the matrix as you go along. Maintain a side mappping of index to address. As you expand it, just zero pad the old entries
 

shuttleboi

Senior member
Jul 5, 2004
669
0
0
Originally posted by: Chronoshock
Given a list of n elements:

Iterate through the linked list constructing an adjacency graph. This takes O(n) time, O(n^2) space
Use elimination to determine if the matrix is singular. This takes O(n) time. I forget if there are faster tests for singularity but its quick enough.
Overall time: O(n)

I assume you are constructing an adjacency matrix, right? How does testing if the matrix is singular show that there is a loop?

Also, what do you mean by "Use elimination to determine if the matrix is singular. This takes O(n) time."? Do you mean use Gaussian elimination to find if the matrix is singular? To the best of my knowledge, Gaussian elimination for an nxn matrix is O(n^3).
 

Chronoshock

Diamond Member
Jul 6, 2004
4,860
1
81
Originally posted by: shuttleboi
Originally posted by: Chronoshock
Given a list of n elements:

Iterate through the linked list constructing an adjacency graph. This takes O(n) time, O(n^2) space
Use elimination to determine if the matrix is singular. This takes O(n) time. I forget if there are faster tests for singularity but its quick enough.
Overall time: O(n)

I assume you are constructing an adjacency matrix, right? How does testing if the matrix is singular show that there is a loop?

Also, what do you mean by "Use elimination to determine if the matrix is singular. This takes O(n) time."? Do you mean use Gaussian elimination to find if the matrix is singular? To the best of my knowledge, Gaussian elimination for an nxn matrix is O(n^3).

Given a cycle a1->a2-> ... _> an-> a1
summing the cols corresponding to a1 through an should give the row for an->a1. This means that one col is a linear combination of other cols. (Hmm I forget, maybe its not a check for singularity but rather full col rank). As for the running time of elimination, I think I was wrong initially, but it should be O(n^2) not O(n^3). For each row, you eliminate all rows below it (giving you the sum from 1 to n-1 which is ~n^2)
 

shuttleboi

Senior member
Jul 5, 2004
669
0
0
Originally posted by: Chronoshock
Originally posted by: shuttleboi
Originally posted by: Chronoshock
Given a list of n elements:

Iterate through the linked list constructing an adjacency graph. This takes O(n) time, O(n^2) space
Use elimination to determine if the matrix is singular. This takes O(n) time. I forget if there are faster tests for singularity but its quick enough.
Overall time: O(n)

I assume you are constructing an adjacency matrix, right? How does testing if the matrix is singular show that there is a loop?

Also, what do you mean by "Use elimination to determine if the matrix is singular. This takes O(n) time."? Do you mean use Gaussian elimination to find if the matrix is singular? To the best of my knowledge, Gaussian elimination for an nxn matrix is O(n^3).

Given a cycle a1->a2-> ... _> an-> a1
summing the cols corresponding to a1 through an should give the row for an->a1. This means that one col is a linear combination of other cols. (Hmm I forget, maybe its not a check for singularity but rather full col rank). As for the running time of elimination, I think I was wrong initially, but it should be O(n^2) not O(n^3). For each row, you eliminate all rows below it (giving you the sum from 1 to n-1 which is ~n^2)

You might be onto something, but you are playing too loosely with your matrix terminology and definitions. Can you be more precise? I think you are visualising that if there is a cycle in the linked list, the corresponding adjacency matrix will be such that every column will have all 0's and one 1, right?

According to wikipedia, Gaussian elimination takes O(n^3) time.

At any rate, I don't think you can use this solution. The original poster did a bad job with the problem's constraints. The way this interview problem is traditionally stated is that you cannot use extra memory that is proportional to n (i.e. you cannot use O(n) extra memory). This not only elminates your soluton (which uses O(n^2) memory), but it also eliminates a solution where you use a hash table to store memory addresses as you traverse the list.
 

eLiu

Diamond Member
Jun 4, 2001
6,407
1
0
Originally posted by: Chronoshock
Given a list of n elements:

Iterate through the linked list constructing an adjacency graph. This takes O(n) time, O(n^2) space
Use elimination to determine if the matrix is singular. This takes O(n) time. I forget if there are faster tests for singularity but its quick enough.
Overall time: O(n)

I have no idea as to what an adjacency graph is, but I can tell you that this solution is not the best.

You can do O(n) time and O(1) space.

chuckywang clearly knows the method :)
 

sao123

Lifer
May 27, 2002
12,648
201
106
Originally posted by: chuckywang
Hint: Have two pointers traverse the linked list.


I was right... I clearly remembered something from data structures of almost 10 years ago.
 

tmc

Golden Member
Aug 14, 2001
1,116
1
81
this is a nice problem. solved it more than a year ago. yup, u should have two pointers. i can say more, PM me if you need a solution. btw, u can "google" it as well :)