Linked Lists and Interview Challenges with Kotlin

Introduction to Linked Lists and Interview Challenges

Welcome back! As we continue to master the art of interview-oriented problems using linked lists in Kotlin, we're setting our sights on practical, algorithmic challenges you will likely 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

Kotlin

fun removeDuplicates(head: ListNode?): ListNode? {
    // 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.
    val seenBooks = mutableSetOf<Int>()
    var 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 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
}

Kotlin

fun averageOfEveryThird(head: ListNode?): Double {
    // 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.
    var sum = 0
    // The number of checkpoints that have contributed to our sum.
    var count = 0
    var current = head // The start of the race.

    // We use 'index' as our countdown timer, ticking off each checkpoint as we pass.
    var index = 1
    while (current != null) {
        // 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.
        }
        current = current.next
        index++
    }

    // The average timing at every third checkpoint, calculated just as a timing system might do.
    return sum.toDouble() / count
}

fun averageOfEveryThird(head: ListNode?): Double {
    // 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.
    var sum = 0
    // The number of checkpoints that have contributed to our sum.
    var count = 0
    var current = head // The start of the race.

    // We use 'index' as our countdown timer, ticking off each checkpoint as we pass.
    var index = 1
    while (current != null) {
        // 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.
        }
        current = current.next
        index++
    }

    // The average timing at every third checkpoint, calculated just as a timing system might do.
    return sum.toDouble() / count
}

Kotlin

fun averageOfEveryThird(head: ListNode?): Double {
    // 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.
    var sum = 0
    // The number of checkpoints that have contributed to our sum.
    var count = 0
    var current = head // The start of the race.

    // We use 'index' as our countdown timer, ticking off each checkpoint as we pass.
    var index = 1
    while (current != null) {
        // 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.
        }
        current = current.next
        index++
    }

    // The average timing at every third checkpoint, calculated just as a timing system might do.
    return sum.toDouble() / 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