Round #573

Use a CTE to find the longest chain of referrals in a referrals table.

```csharp using System; using System.Collections.Generic; using System.Data; using System.Linq; public class Referral { public int Id { get; set; } public int ReferredBy { get; set; } } class Program { static void Main() { var referrals = new List<Referral> { new Referral { Id = 1, ReferredBy = null }, new Referral { Id = 2, ReferredBy = 1 }, new Referral { Id = 3, ReferredBy = 2 }, new Referral { Id = 4, ReferredBy = 3 }, new Referral { Id = 5, ReferredBy = 4 }, new Referral { Id = 6, ReferredBy = null }, new Referral { Id = 7, ReferredBy = 6 }, new Referral { Id = 8, ReferredBy = 7 }, new Referral { Id = 9, ReferredBy = 8 }, }; var longestChain = FindLongestChain(referrals); Console.WriteLine("Longest chain of referrals:"); foreach (var referral in longestChain) { Console.WriteLine($"Id: {referral.Id}, ReferredBy: {referral.ReferredBy}"); } } static List<Referral> FindLongestChain(List<Referral> referrals) { var referralDict = referrals.ToDictionary(r => r.Id, r => r); var longestChain = new List<Referral>(); var maxLength = 0; foreach (var referral in referrals) { var chain = new List<Referral>(); var currentReferral = referral; while (currentReferral != null) { chain.Add(currentReferral); currentReferral = referralDict.ContainsKey(currentReferral.ReferredBy) ? referralDict[currentReferral.ReferredBy] : null; } if (chain.Count > maxLength) { longestChain = chain; maxLength = chain.Count; } } return longestChain; } } ```

```csharp using System; using System.Data; using System.Data.SqlClient; public class ReferralChainFinder { public static void FindLongestReferralChain(string connectionString) { using (var connection = new SqlConnection(connectionString)) { connection.Open(); var query = @" WITH ReferralCTE AS ( SELECT ReferrerId, ReferredId, 1 AS Level FROM Referrals WHERE ReferrerId IS NULL -- anchor query: referrals with no referrer UNION ALL SELECT r.ReferrerId, r.ReferredId, Level + 1 FROM Referrals r INNER JOIN ReferralCTE cte ON r.ReferrerId = cte.ReferredId ) SELECT ReferredId, Level FROM ReferralCTE ORDER BY Level DESC OFFSET 0 ROWS FETCH NEXT 1 ROW ONLY; -- get the longest chain "; using (var command = new SqlCommand(query, connection)) { using (var reader = command.ExecuteReader()) { while (reader.Read()) { Console.WriteLine($"Longest chain: ReferredId = {reader["ReferredId"]}, Level = {reader["Level"]}"); } } } } } public static void Main(string[] args) { var connectionString = "Server=myServerAddress;Database=myDataBase;User Id=myUsername;Password=myPassword;"; FindLongestReferralChain(connectionString); } } ``` This C# code uses a recursive Common Table Expression (CTE) to find the longest chain of referrals in a `Referrals` table. The `ReferralCTE` CTE starts with referrals that have no referrer (i.e., the anchor query) and then recursively joins the `Referrals` table to find the next level of referrals. Here's a step-by-step explanation: 1. The `ReferralCTE` CTE is defined with two parts: the anchor query and the recursive query. 2. The anchor query selects referrals with no referrer (`ReferrerId IS NULL`) and assigns a level of 1 to each referral. 3. The recursive query joins the `Referrals` table with the `ReferralCTE` CTE on the condition that the `ReferrerId` in the `Referrals` table matches the `ReferredId` in the `ReferralCTE`. This effectively finds the next level of referrals. 4. The recursive query increments the level by 1 for each new level of referrals. 5. The `UNION ALL` operator combines the results of the anchor query and the recursive query. 6. The final query selects the `ReferredId` and `Level` from the `ReferralCTE` CTE, orders the results by level in descending order, and fetches the top row (i.e., the longest chain). Note that this code assumes a SQL Server database connection. You may need to modify the connection string and the query to suit your specific database system.