This was a coding interview in Scala. The problem statement was a simple one :
Input = List(10, 10, 10, 10, 20, 30, 30, 10, 10, 40, 50, 50, 50, 50)
Output = List(10, 20, 30, 10, 40, 50)
Kindly eliminate the consecutive duplicates of the elements contained within this list.
Approach 1
My first thought was to implement a temp variable based solution - introduce a “memory” element which keeps updating when encountering a new number and I ended up writing the below code -
val input = List(10, 10, 10, 10, 20, 30, 30, 10, 10, 40, 50, 50, 50, 50)
var memory = -1
val output = input.map(elem => {
if (elem != memory)
elem
if (elem != memory)
memory = elem
})
This was giving me a list of empty values as the output list.
List((), (), (), (), (), (), (), (), (), (), (), (), (), ())
There was a very basic but critical error in my logic - it lacked a return in the map. I was trying to return the elements if they satisfied the criteria of not matching the memory element. And I also wanted to update the memory element. So, my map had no explicit return value for each element, On top of that, it never went inside the if statement which updates the memory. So the map was implicitly returning Empty values (Unit in Scala). I didnt even notice that (elem != memory) is checked twice.
If I wanted to use this approach using map and a memory variable(var), the correct version would have been -
val output = input.map(elem => {
if (elem != memory){
memory = elem
Some(elem)
}else{
None
}
}).flatten
During the interview, I tried a another approach.
Approach 2
I switched to a for loop based solution. Starting with a list, as a mutable variable, to be updated with each element which satisfied the criteria. But I couldnt get the list append syntax to work. The interviewer also didnt offer to help. I was confusing :+ with ::.
I ended up printing out the result list directly.
def keepElement(curr: Int, prev:Int) :String = {
if(curr != prev)
return curr.toString
else
return ""
}
for ( i <- 0 to input.size - 1) {
if(i == 0){
println(input(i))
}
else{
println(keepElement(input(i), input(i-1)))
}
}
This time I did get the correct output but the solution was dirty. The output was not stored in a list and was getting printed out.
[10
20
30
10
40
50
]
The solution was also not pure scala. The method I defined could have been done inline. The correct syntax would have been -
var output = List[Int]()
output = output :+ input(0)
for( i <- 1 until input.length){
if(input(i) != input(i-1)) {
output = output :+ input(i)
}
}
At this point, I felt there is no way to do this without using a dirty “var”. It had already taken me 30 mins to compile and run my 2 attempts, so the interviewer let me go. I looked up the solution after the call. The correct way to do it was only a few lines as below -
val output = input.foldRight(List[Int]()) { (cur, res) =>
if (res.isEmpty || res.head != cur) cur, :: res
else res
}
Exercises like this make me want to learn and question the idea that the language is just a tool. The approach needs to keep the language also in mind. And a scala minded approach, is very different from a script based or C based approach which I was accustomed to. There are just too many ways to do something, so its very easy to start thinking along some lines which will lead to a suboptimal solution. As someone still in the early stages of learning Scala, mastering the language and its ways seems like a career long commitment.