Interview Coding Challenge - Duplicate Integers

Today’s article is focused on a frequently asked interview coding exercise. I will jump on directly on the question that you might face when you interview for your next job.

The interviewers do not demand a complete solution and even most of them do not care of the programming language you use even pseudo code works, they are more interested in the approach and the efficiency of the algorithm. However, here I am going to use Scala.

I will share some possible solutions. So, lets start!

Question: Write a function that takes a list of integers and returns the list of duplicate integers.
Example: input -> [1,2,3,4,2,5,5,3,5], output -> [2,3,5]

First lets go with traditional approach.

def findDups(input: List[Int]) : Set[Int] = {
 var result = List[Int]()
 for(i <- 0 to input.length-1){
  var count = 0
  for(j <- i+1 to input.length-1){
   if(input(i) == input(j)){
    result = result :+ input(i)
    count = count + 1 
   }
  }
 }
 result.toSet
}
findDups(List(1,2,3,4,2,5,5,3,5))

This approach uses two loops and does the linear search over the list making its complexity O(n^2).

Lets make it more efficient.

def findDups(input: List[Int]) : Set[Int] = {
 var result = List[Int]()
 val sortedInput = input.sorted 
 for(i <- 0 to sortedInput.length-2){
  if(sortedInput(i) == sortedInput(i+1))
   result = result :+ sortedInput(i)
 }
 result.toSet
}
findDups(List(1,2,3,4,2,5,5,3,5))

Now it uses a single loop on a sorted list, making it complexity (sorting + for loop) = (O(nlogn) + O(n)) which is O(nlogn). If we already had a sorted list then it would be O(n).

Lets make it cleaner using high order functions (functional)

def findDups(input: List[Int]) : Set[Any] = {
 input.map(x => 
  if(input.filter(_ == x).size > 1) x else "").
  filter(_ != "").
  toSet
}
findDups(List(1,2,3,4,2,5,5,3,5))

Now it looks cleaner but still iterates twice, one for map and one for filter.
We can make it even one liner.

def findDups(input: List[Int]) = list.diff(list.distinct).distinct
findDups(List(1,2,3,4,2,5,5,3,5))

Now that’s super clean. Remember its optional to mention the return type in Scala.

This is how one question can be made more efficient and cleaner. There might be better/alternate solution available (for example using group by), please feel free to leave a comment!