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 (14)

  1. Dis4ea says:

    That’s why I hate simple solutions 🙂

    They are so obvious that you miss them.

  2. Brooks says:

    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.  

  3. MSDN Archive says:

    Brooks:  I suppose you’re right.  The addition of the "Previous employee" and "Next employee" output technically changes the output of the proc, which I didn’t have an explicit rule against (I thought it was implicit) so I guess it would still be a correct solution.

    Dis4ea:  You actually had the solution before anyone else, but you unfortunately put it in the Mentor function.  That’s why I ended my response to you about it with an ellipsis 🙂

    Sjoerd:  I was just wondering:  how’s that bowl of crow tasting?  🙂

  4. rockmoose says:

    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

  5. Dis4ea says:

    Ouch, I didn’t get that subtle hint 🙁

  6. Sjoerd Verweij says:

    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!

  7. Sjoerd Verweij says:

    And oh, about the shortest solution without the silly rules in force… My CTE-fu is not strong at the moment, alas — my brain is currently well and truly fried. If noone has posted anything by tomorrow, I’ll have a stab at it.

  8. Sjoerd Verweij says:

    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?

  9. Daryl Blowes says:

    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

  10. Dating says:

    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

  11. Weddings says:

    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