Introduction to Linked Lists and Algorithmic Challenges with Scala

Introduction to Linked Lists and Interview Challenges

Welcome back! As we continue to master the art of interview-oriented problems using linked lists in Scala, 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

Scala

case class ListNode(var value: Int, var next: Option[ListNode] = None)

object LinkedListChallenges {
  def removeDuplicates(head: Option[ListNode]): Option[ListNode] = {
    // If the library is empty or has only one book, no duplicates can exist.
    head match {
      case None => None
      case Some(first) if first.next.isEmpty =>
        head
      case Some(first) =>
        // We initiate our checklist to keep track of unique books we've already checked out.
        var seenBooks = Set[Int]()
        var current = first // Start checking from the first book on the shelf.
        seenBooks += current.value // The first book is always unique.

        while (current.next.nonEmpty) {
          current.next match {
            case Some(nextNode) if seenBooks.contains(nextNode.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 = nextNode.next
            case Some(nextNode) =>
              // Upon detecting a unique book, we add it to the checklist and move to the next on the shelf.
              seenBooks += nextNode.value
              current = nextNode
            case None => ()
          }
        }
        
        // The cleaned-up library with no duplicate titles.
        head
    }
  }
}

Scala

object LinkedListChallenges {
  def averageOfEveryThird(head: Option[ListNode]): Double = {
    // A race with fewer than three checkpoints doesn't provide enough data for averaging.
    @annotation.tailrec
    def loop(current: Option[ListNode], index: Int, sum: Long, count: Int): Double =
      current match {
        case None =>
          if (count == 0) 0.0
          else sum.toDouble / count
        case Some(node) =>
          // We use 'index' as our countdown timer, ticking off each checkpoint as we pass.
          val (newSum, newCount) =
            if (index % 3 == 0) {
              // Our timer activates at every third checkpoint.
              (sum + node.value, count + 1)
            } else {
              (sum, count)
            }
          loop(node.next, index + 1, newSum, newCount)
      }

    loop(head, 1, 0L, 0)
  }
}

object LinkedListChallenges {
  def averageOfEveryThird(head: Option[ListNode]): Double = {
    // A race with fewer than three checkpoints doesn't provide enough data for averaging.
    @annotation.tailrec
    def loop(current: Option[ListNode], index: Int, sum: Long, count: Int): Double =
      current match {
        case None =>
          if (count == 0) 0.0
          else sum.toDouble / count
        case Some(node) =>
          // We use 'index' as our countdown timer, ticking off each checkpoint as we pass.
          val (newSum, newCount) =
            if (index % 3 == 0) {
              // Our timer activates at every third checkpoint.
              (sum + node.value, count + 1)
            } else {
              (sum, count)
            }
          loop(node.next, index + 1, newSum, newCount)
      }

    loop(head, 1, 0L, 0)
  }
}

Scala

object LinkedListChallenges {
  def averageOfEveryThird(head: Option[ListNode]): Double = {
    // A race with fewer than three checkpoints doesn't provide enough data for averaging.
    @annotation.tailrec
    def loop(current: Option[ListNode], index: Int, sum: Long, count: Int): Double =
      current match {
        case None =>
          if (count == 0) 0.0
          else sum.toDouble / count
        case Some(node) =>
          // We use 'index' as our countdown timer, ticking off each checkpoint as we pass.
          val (newSum, newCount) =
            if (index % 3 == 0) {
              // Our timer activates at every third checkpoint.
              (sum + node.value, count + 1)
            } else {
              (sum, count)
            }
          loop(node.next, index + 1, newSum, newCount)
      }

    loop(head, 1, 0L, 0)
  }
}

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