The simplest rule-compliant solution to the employee-mentor challenge I recently posted is to change the loop such that it iterates through the relationships at more than one speed.  Making no other changes to clean up the code, something like this would do:

CREATE PROC ListMentors(@LastEmpIdAdded int) as

DECLARE @i int

DECLARE @j int

SELECT @i = @LastEmpIdAdded  -- ID of last employee added (known in advance)

PRINT 'Employee: '+CAST(@i AS varchar(10))

SELECT  @i = dbo.Mentor(@i)

PRINT 'Mentor: '+CAST(@i AS varchar(10))

SELECT @j = dbo.Mentor(@i)

WHILE (@i IS NOT NULL) 

BEGIN

      PRINT 'Employee: '+CAST(@i AS varchar(10))

      SELECT @i = dbo.Mentor(@i)

      PRINT 'Mentor: '+CAST(@i AS varchar(10))

      SELECT @j = dbo.Mentor(dbo.Mentor(@j))

      IF (@i=@j)

      BEGIN

            PRINT 'List is corrupt'

            BREAK

      END

END

The type of list corruption the challenge presented was a loop.  Due to a bug in the app that updated the list when an employee left the company, a circular relationship was being introduced between an employee and his mentors.  This caused ListMentors to find itself trapped in an infinite loop.  

If there is indeed a circular relationship in the list, having two iterators that walk it at different speeds will cause them to collide at some point.  Thus, the code prints a message and exits the loop when @i and @j equal one another.

You’ll recall that I made the challenge off-limits to MS people.  In addition to the reason I stated, this is also because the puzzle is a variation on a question that’s commonly used in Microsoft interviews.  If you search the net for “Microsoft interview questions” and “circular linked list,” you’ll find it.  I explicitly avoided referring to the relationships as a “list” and the corruption as “circular” in the original post because I wanted to see whether anyone would figure out that the data structure being described was really a singly-linked list, and I wanted people to think a bit rather than merely grabbing an answer off the net.

Of course, the challenge for me in porting this puzzle to T-SQL is that SQL has the ability to “walk” the list without needing the references between the nodes.  That’s not true of a linked list.  Good ol’ SELECT, coupled with an aggregate or two, makes short work out of problems like this.  That's why I made set-oriented approaches and variations on COUNT() off-limits.

As for who was first with a solution that met all the criteria, that would be Oleg K.  Scan the comments for the challenge, and you’ll find his solution.

This is a good example of where knowledge of other languages and the common techniques used to solve problems with them comes in handy with T-SQL. 

Exercise for the curious:  If I do away with rules 3-5, what’s the shortest solution to the problem you can come up with?  (Remember that you can use techniques specific to SQL Server 2005.)