Author: tomc (Tom Carmichael)
Date: 2003-Dec-05 02:27:32

Since someone broached the topic of job interview questions, I thought I'd 
throw one out there that I had on the interview to my current job, 5-6 
years ago.  (I guess I did okay.)

It's a bit computer science-y, but it does have a strong math background to 
it as well.  I'll try to give a brief overview of the CS elements.

Suppose you have a (linked) list of elements, such that each element had a 
pointer to the 'next' member or an 'end of list' marker.  The 'next' 
element is in fact allowed to be a 'previous' element in the list to form 
rings.  This means your list could look like:

[] -> [] -> [] -> [] -> EOL

or

[] -> [] -> []
       |     |
       ^    []
       |     |
      [] <- []

or even

[] <-> []

Your task, should you choose to accept it, is to find an algorithm which 
determines if the list ends (reaches an EOL marker) or continues forever.

For the requirements below, O(x) is 'Big O' notation.  This means that the 
governing formula's largest term is 'x'.  For example, a simple quadratic 
ax^2+bx+c is O(x^2).  N refers to the number of elements in the list.  To 
do a simple 'walk' of the list (visit each node in turn) is an O(N) 
fuction, since you hit N different elements.  An O(1) function means it is 
constant, like dividing a number by 2.

Here are the catches:

a)  Any algorithm will suffice
b)  Your solution must use no more than O(N) operations and O(N) memory
c)  Your solution can use any number of operations, but can 
only use O(1) [constant] memory.  In other words, your use of memory must 
be fixed regardless of the size of the list.
d)  Your solution must use no more than O(N) operations and O(1) memory.

These are in increasing difficulty.  I'm told that no one has ever gotten 
the answer to (d) in an actual interview setting.  (I do know the 
solution.)

Good luck!


Author: jason (Jason Jordan) Date: 2003-Dec-05 03:59:25 Nice problem! It's very similar to a problem I was planning on posting, so I'm going to bite my tongue on this one. :-) I'll post my variation after all is said and done, so that I don't inadvertently give anything away.
Author: migo (Mikhael Goikhman) Date: 2003-Dec-05 04:21:14 This riddle was popular 8 years ago in my University. :) I thought that I completely forgot the solution, but it seems that not completely, because I was able to reconstruct it without much problems. I don't have a time to reconstruct (a), (b) and (c) now, it should be easy, I think. So I only reconstructed the solution for (d). :-) P.S. I think it may be better to always set meaningful subjects.
Author: bandsmer (Michael Bandsmer) Date: 2003-Dec-05 19:03:49 Solutions for (b) and (c) are fairly obvious, but it took me a little longer to come up with a solution for (d). I'll not post it yet, though, in case others want to try it.
Author: tomc (Tom Carmichael) Date: 2003-Dec-09 16:25:21 So, does anyone want to post their solution? :-) Tom
Author: jason (Jason Jordan) Date: 2003-Dec-09 16:39:08 One solution for (d) is to walk the list with two pointers A and B. For each 2 steps that A advances, have B advance one step. If A ever points to the same location as B after 1 or more iterations, then there is a loop and the list "continues forever".
Author: bandsmer (Michael Bandsmer) Date: 2003-Dec-09 18:13:37 My solution is essentially the same as Jason's. Since the slower pointer (B) will never hit the same element twice, we have O(N) time.
Author: migo (Mikhael Goikhman) Date: 2003-Dec-09 18:07:23 How about this solution for (d). Reverse all pointers in-place. :) I.e: head -> node1 -> node2 -> NULL is converted to: head <- node1 <- node2 NULL Now, if you ever encounter "head" again, this means there are loops, if you come to NULL, there are no loops. I leave it to you to prove that this algorithm works. You will want to travel again and reverse all links, i.e. to restore the original list. h -> a -> b >>> h -> a <- b ^ | becomes | ^ | v <<< v | d <- c d -> c We traveled and reversed the first link twice (because of loops) and all other links in this case are walked reversed once. We came to head, this means there are loops. Now, just travel the resulting list again and reverse all links in the same way, this restores the original list. This solution uses 2 * N steps (time) and one running pointer (memory).
Author: jason (Jason Jordan) Date: 2003-Dec-09 19:22:15 Nice Mikhael, I was hoping there would be another neat solution, and you provided it. :) I'm actually surprised nobody has been able to solve part (d) of this problem in an interview setting.
Author: bandsmer (Michael Bandsmer) Date: 2003-Dec-09 20:24:08 Mikhael's solution just gave me an idea for an extension to this puzzle: For linked lists with a loop, find the total number of unique list elements, N. I think it's possible in time O(N) and memory O(1). Feel free to post your solution when you find it.
Author: tomc (Tom Carmichael) Date: 2003-Dec-09 20:40:15 The solution I knew was the double pointer 'race' (single and double increment). The pointer reversal is quite ingenious. :-) As for why anyone wouldn't get it in an interview situation, it's a bit hard to come up with something like that on the fly while holding a marker in your hand up at a white board. With a bit of thought, sure. :-) I'll need to ponder the new problem some. :-) Tom
Author: jason (Jason Jordan) Date: 2003-Dec-09 22:49:46 To find N, simply extend the "race" algorithm like so: 1. Start at A = B = head 2. Advance A two nodes for each node B advances, until either A = EOL or A = B, counting the number of nodes each has traversed (call this a and b, respectively) 3. If A = EOL, then N = a, and we are done 4. If A = B, then advance A until we reach B again, counting the nodes along the way (call this c). This gives us the number of nodes in the loop. 5. To get the number of nodes in the portion of the list outside of the loop, set A = head and advance A by c nodes. Now set B = head, and advance A and B until A = B, counting the nodes along the way (call this d). 6. N = c + d
Author: bandsmer (Michael Bandsmer) Date: 2003-Dec-10 01:00:12 I like Jason's way of getting N. The solution I had in mind isn't nearly as clean. (My way is: First apply the "race" algorithm; let b=number of nodes before 'm', where 'm' is the node where the 2 pointers first match. Then invert the directions of the pointers within the loop, starting at 'm', counting c=number of nodes in the loop. Then start from the head of the list and find 'm' again, counting d=number of nodes before 'm'. If b=d, then N=b+c; otherwise N=(b+c+d)/2. Then you have to re-invert the pointer directions in the loop to get the original list back.) Jason's solution is more intuitive as well as cleaner. Nice.