Answer to the most recent T-SQL challenge

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.)

Comments

• Anonymous
  February 12, 2006
  That's why I hate simple solutions :-)
  They are so obvious that you miss them.
• Anonymous
  February 13, 2006
  Out of curiosity, and while is wasn't the best solution, on what criteria did my solution fail on?  It was recorded before Oleg K's solution.  
• Anonymous
  February 13, 2006
  The comment has been removed
• Anonymous
  February 13, 2006
  Good puzzle. Funny how difficult it was to leave a set-based frame of mind.
  And I learned an algorithm, thank you.
  Appreciate your efforts!
  
  rockmoose
• Anonymous
  February 13, 2006
  Ouch, I didn't get that subtle hint :-(
• Anonymous
  February 15, 2006
  The crow is crunchy, thank you very much. Dangit.
  
  Now, being the sore loser that I am, let me tell you why I didn't see it: I took your "Your task is to change the proc's singleton SELECT code" too literally (key word: "change", not "add"). Of course, had I considered adding a second select, I would have come up with this solution in a heartbeat. cough cough No, really. cough  :-)
  
  Interview question you say? Hah, good thing I didn't waste anyone's time by applying for a job at Microsoft then. I'll just go back to my nice, pedestrian research of a nice, obscure SQL Server 2005 bug (and how to avoid it). Just in case someone else has run into it and has a workaround: how do you prevent SQL Server from hard dumps (which seem to hang themselves, leaving 10MB of dead SQLDumper and DW20 processes to bleed your server to death) on Updates that do not affect any records on certain tables (with computed columns, but that in and of itself does not seem to suffice) with a trigger on them that does a Cross Join between Inserted and Deleted? I'm finally getting around to it now that I fixed CHECKDB giving undocumented 3853 sql_dependencies errors (manually looking up the objects and recreating them), fun new parameter sniffing foibles, tightened rules on Order By clauses (okay, that's a good thing, but still, thanks for the warning)... and rewriting our automatic e-mail system to CDO (whose bright idea was it to allow installation and activation of SQL Mail on 64-bit SQL Server and then only when actually used finally taunt with a "SQL Mail doesn't work on 64-bit SQL Server"? Very cute.)
  
  Sorry about the rant. I guess I'm just a bit grumpy. I did enjoy the puzzle; keep 'em coming. I'll get you next time. I'll even save you some crow!
  
• Anonymous
  February 15, 2006
  The comment has been removed
• Anonymous
  February 16, 2006
  Okay, here's a rough idea:
  
  With Mentor(EmpID, Mentor)
  As (Select E.EmpID, E.Mentor
     From Employees As E
     Where E.Mentor Is Null
     
     Union All
     
     Select E.EmpID, E.Mentor
     From Employees E
     Inner Join Mentor M
     On E.Mentor = M.EmpID)
  Select EmpID, Mentor
  From Mentor    
  
  Only works up to 100 deep, and does not give a message on a loop -- it just stops.
  
  Was that what you meant?
• Anonymous
  November 11, 2006
  I wrote a circular reference prevention trigger that will check all the rows being inserted or updated to see if the Parent / Child relations do not loop or go deeper than 10 parent/children.

---

CREATE Trigger triu_Department_PreventCircularTree ON dbo.Department For Insert, Update As Declare @Count int Declare @ParentDepartmentID int Declare curUpdates Cursor For SELECT ParentDepartmentID FROM Department WHERE DepartmentID IN (SELECT DepartmentID FROM Inserted) For READ ONLY Open curUpdates Fetch Next From curUpdates INTO @ParentDepartmentID While @@Fetch_Status = 0 Begin SET @Count = 0 -- Go up through the Tree for a MAX of 10 deep ... if we exceed 10 then too much While (@ParentDepartmentID Is Not Null) AND (@Count < 10) Begin SET @Count = @Count + 1 SELECT @ParentDepartmentID = ParentDepartmentID FROM Department WHERE DepartmentID = @ParentDepartmentID End -- If we exceeded the limit then there is probably a circular reference If (@Count >= 10) Begin Raiserror('A Group can NOT be a Sub-Group of a Child.', 16, 1) Goto Cleanup End -- Get the Next Department record that was updated within this INSERT or UPDATE trigger Fetch Next From curUpdates INTO @ParentDepartmentID End Cleanup: Close curUpdates Deallocate curUpdates

• Anonymous
  May 30, 2008
  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 woul

• Anonymous
  June 05, 2008
  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 woul

• Anonymous
  June 01, 2009
  PingBack from http://paidsurveyshub.info/story.php?id=77513

• Anonymous
  June 09, 2009
  PingBack from http://quickdietsite.info/story.php?id=4699

• Anonymous
  June 16, 2009
  PingBack from http://topalternativedating.info/story.php?id=4067