Garbage Collector Circular Reference Detection
I was recently reading about how the Garbage Collector is able to detect circular references and I remembered something from one of my interviews at Microsoft in Summer 2002. The question I got asked was, if you have a very large linked list, how would you find out if an infinite loop condition exists.

Well, for all you nascar/F1 fans, think of a racing track. If you have a very fast car, lets call it the Ferrari car driven by Michael Schumaker and a very slow car, lets call that Cristiano da Matta in Toyota, then the Ferrari which is going faster than the Toyota, will overlap the Toyota.

So if you get an overlap in the race, then you know that the track is connected ie. the cars are driving in circles.

In the linked list approach, start one Node pointer traversal at 1 node per tick, and a second Node pointer at 2 nodes per tick. Then at some point in time, both nodes will inevitably point to the same node if a circular reference occurs.

Thus you can detect a circular reference. So now how can you apply this to infinite loops. Well it turns out that a lot of the infinite loops are just that, loops. The same process of "different speeds" can be used for the infinite loop nodes too.
- posted by Sushant Bhatia @ 11:32 PM