Another Microsoft interview question

[the FooL]

Two solutions.

Elegant solution:
1. Set the Head node to point to Null
2. Traverse the list, and reverse the links as you go.
3. When you get to the end, if the End ptr is the same as the Head ptr,
you have a loop.


Hack solution:
1. Most current systems are word-aligned, so for each node, you set the
lowest bit to 1 (incrementing the ptr by 1 is wrong).
If you come across a Node that has it already set (dirty bit), you
have a loop.


Both cases have an order of N to solve, with the edge given to the hack.
the elegant solution was thought of by the only junior dev in my company.
the hack by a senior.
(I was busy working of course).

 

[poop]

Counting on alignment is the best hack, I think. It was the first thing that popped into my head. But it is not guaranteed across platforms. Hopefully everything is properly word aligned so you don't take the performance penalty of single byte accesses. It does happen, though.

Falcon actually hit the quickest solution. If you think about it, it takes a MAX of 3 list traversals (ie, moving a pointer across the list 1 whole time = traversal).

The most precise solution (my friend came up with a couple of days ago)
1. Reverse all links, you will eventually come back to the beginning. Count the number of nodes you traverse. This value is X.
2. Move 1/2 your count into the list. You are guaranteed to be in the loop at this point.
3. Store the address of your current node.
4. Traverse the Loop until you reach your known node. This count is the number of nodes in the loop (known as Y)
5. Subtract the second count form the first, and divide the left over amount in half. X now equals (X-Y)/2
6. This resultant tells you which node is looped to. (X)
7. X+Y is the size of the whole list.
8. Fix the list.


That is pretty involved, and is not as quick and nifty as the two pointer solution. this solution lets you know a lot about the list in about 3 traversals of time, though.

 

[the FooL]

Which answer?

I think the second is more than 3 traversals, depending on the size of the loop and the values chosen for the movement.
try it for 10 nodes, with the loop between 10 and 4.
A=3 B=6.
I got B looping 5 times and A 2 around the loop.
and this can take quite a while if the loop is larger than the move steps.

Your friends is the same as the reversal, with some more calculations.

Was the goal to find the loop or just detect it?