Introduction to Linked Lists and Interview Challenges in C#

Introduction to Linked Lists and Interview Challenges

Welcome back! As we continue to master the art of interview-oriented problems using linked lists in C#, we're setting our sights on practical, algorithmic challenges you are likely to face.

Problem 1: Eliminating Duplicates in Linked Lists

Consider the following real-life problem: You’re tasked with organizing a digital library where some books have been accidentally duplicated. You aim to identify and remove these redundant entries to ensure each title is unique in your catalog.

Problem 1: Naive Approach and Its Drawbacks

O(n^2)

Problem 1: Efficient Approach Explanation and Comparison

O(n)

Problem 1: Step-by-Step Solution with Detailed Explanation

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

using System.Collections.Generic;

public class ListNode {
    public int Value;
    public ListNode Next;
    public ListNode(int x) { Value = x; }
}

public class LinkedListChallenges {
    public ListNode RemoveDuplicates(ListNode head) {
        // If the library is empty or has only one book, no duplicates can exist.
        if (head == null || head.Next == null) {
            return head;
        }
        
        // We initiate our checklist to keep track of unique books we've already checked out.
        HashSet<int> SeenBooks = new HashSet<int>();
        ListNode Current = head; // Start checking from the first book on the shelf.
        SeenBooks.Add(Current.Value); // The first book is always unique.

        while (Current.Next != null) {
            if (SeenBooks.Contains(Current.Next.Value)) {
                // We've already seen this book, so we remove it from the shelf by 
                // redirecting the current pointer to the next unique book.
                Current.Next = Current.Next.Next;
            } else {
                // Upon detecting a unique book, we add it to the checklist and move to the next on the shelf.
                SeenBooks.Add(Current.Next.Value);
                Current = Current.Next;
            }
        }

        // The cleaned-up library with no duplicate titles.
        return head;
    }
}

public class LinkedListChallenges {
    public double AverageOfEveryThird(ListNode head) {
        // A race with fewer than three checkpoints doesn't provide enough data for averaging.
        if (head == null || head.Next == null || head.Next.Next == null) {
            return 0.0;
        }
        
        // Here, we'll record the total times at selected checkpoints.
        int Sum = 0; 
        // The number of checkpoints that have contributed to our sum.
        int Count = 0; 
        ListNode Current = head; // The start of the race.

        // We use 'Index' as our countdown timer, ticking off each checkpoint as we pass.
        for (int Index = 1; Current != null; Current = Current.Next, Index++) {
            // Our timer activates at every third checkpoint.
            if (Index % 3 == 0) {
                Sum += Current.Value; // Add the checkpoint time to our total.
                Count++; // Another checkpoint contributes to the average.
            }
        }
        
        // The average timing at every third checkpoint, calculated just as a timing system might do.
        return (double)Sum / Count;
    }
}

public class LinkedListChallenges {
    public double AverageOfEveryThird(ListNode head) {
        // A race with fewer than three checkpoints doesn't provide enough data for averaging.
        if (head == null || head.Next == null || head.Next.Next == null) {
            return 0.0;
        }
        
        // Here, we'll record the total times at selected checkpoints.
        int Sum = 0; 
        // The number of checkpoints that have contributed to our sum.
        int Count = 0; 
        ListNode Current = head; // The start of the race.

        // We use 'Index' as our countdown timer, ticking off each checkpoint as we pass.
        for (int Index = 1; Current != null; Current = Current.Next, Index++) {
            // Our timer activates at every third checkpoint.
            if (Index % 3 == 0) {
                Sum += Current.Value; // Add the checkpoint time to our total.
                Count++; // Another checkpoint contributes to the average.
            }
        }
        
        // The average timing at every third checkpoint, calculated just as a timing system might do.
        return (double)Sum / Count;
    }
}

public class LinkedListChallenges {
    public double AverageOfEveryThird(ListNode head) {
        // A race with fewer than three checkpoints doesn't provide enough data for averaging.
        if (head == null || head.Next == null || head.Next.Next == null) {
            return 0.0;
        }
        
        // Here, we'll record the total times at selected checkpoints.
        int Sum = 0; 
        // The number of checkpoints that have contributed to our sum.
        int Count = 0; 
        ListNode Current = head; // The start of the race.

        // We use 'Index' as our countdown timer, ticking off each checkpoint as we pass.
        for (int Index = 1; Current != null; Current = Current.Next, Index++) {
            // Our timer activates at every third checkpoint.
            if (Index % 3 == 0) {
                Sum += Current.Value; // Add the checkpoint time to our total.
                Count++; // Another checkpoint contributes to the average.
            }
        }
        
        // The average timing at every third checkpoint, calculated just as a timing system might do.
        return (double)Sum / Count;
    }
}

Introduction to Linked Lists and Interview Challenges

Problem 1: Eliminating Duplicates in Linked Lists

Problem 1: Naive Approach and Its Drawbacks

Problem 1: Efficient Approach Explanation and Comparison

Problem 1: Step-by-Step Solution with Detailed Explanation

Join the 1M+ learners on CodeSignal

Problem 2: Finding the Average of Every Third Element

Problem 2: Problem Actualization

Problem 2: Efficient Approach

Building the Solution Step-by-Step with Detailed Explanation

Lesson Summary