Scala Mock Coding Test

Scala Mock Interview: Coding Questions

I recently started learning Scala because of its Actor Framework. Over the last few weeks, I've been working my way through the Programming in Scala book. Having done that, I figured I'd test myself out using some of Steve Yegge's Phone Screen Questions. I've had the opportunity to be on both sides of the interview table/phone with Steve's strategy, and both as interviewee and interviewer, I think the approach works much better than the others I have encountered/tried.
I've adapted the strategy somewhat for my own purposes. One, I hardly do any phone screens - almost all the interviews I've done over the past couple of years have been face-to-face. Two, I usually cover 3 areas instead of the 5 Steve advocates - our interviews last about 45 minutes, and 10-15 minutes per question leaves just enough time to answer questions that the candidate may have about us. To get maximum coverage, a few colleagues (who also follow this strategy) and I usually split up the areas amongst ourselves prior to the interview.
In any case, I've noticed that reading a programming language tutorial usually leaves me with just enough knowledge to read code in that language. Writing some code is the only way I actually get to a point where I can program in that language. So if you are like me, reading this post will probably not do you much good - except perhaps to notice the many similarities to Java. However, if you are one of the lucky few who are able to absorb a language by reading code, then this post contains some simple Scala code to implement the coding questions in Steve's page referenced above.
On the other hand, if you are an experienced Scala programmer, I am guessing that much of this code would look very primitive and/or Java-like to you. In that case, I would appreciate your feedback and hints/pointers on better ways to do things in Scala.

Maven Project Setup

The lift Project (a Scala web framework) provides a Maven2 archetype for basic Scala projects, so that you get all the Maven2 goodness and its associated productivity boost for free in your Scala project. To create a basic Scala project, run the command:

sujit@sirocco:~$ mvn archetype:create \
  -DarchetypeGroupId=org.scala-tools.archetypes \
  -DarchetypeArtifactId=scala-archetype-simple \
  -DarchetypeVersion=1.2 \
  -DremoteRepositories=http://scala-tools.org/repo-releases \
  -DgroupId=com.mycompany.smi \
  -DartifactId=scala-examples

Update the scala.version property in the generated POM to suit your setup (I am using Scala 2.7.3). I started out using the Scala Eclipse plugin, so I did mvn eclipse:eclipse to generate my Eclipse IDE descriptors. Then follow instructions on the plugin page to configure the plugin in your IDE.
However, (at least in my case, I was using Eclipse 3.4.1/MyEclipse 7/Scala 2.7.3 with the plugin available from the update site), the Eclipse plugin was so bad as to be almost unusable. There was no code-suggest, editors would freeze and would need to be closed and reopened, etc. I ended up using Netbeans Scala plugin (with Netbeans 6.5), and it is sooo much better. Netbeans also recognizes a Maven project natively, so no descriptors need to be generated. My only gripe with Netbeans is its tendency to randomly freeze up for 30-40s at a time, something I've never seen with Eclipse.
Anyway, here are Steve's questions (and some of my own) and my Scala solutions below.

Reverse a String

This is actually one of my favorites, although its quite sad to see how many people cannot come up with even a single solution. But the nice thing about this one is that it is extendable in so many interesting ways. Here are some of mine.

// Source: src/main/scala/com/mycompany/smi/coding/StringReverser.scala
package com.mycompany.smi.coding

object StringReverser {
  
  // calling the method on String directly
  def reverse1(s: String): String = {
    s.reverse
  }
  
  // iterating backward through the string
  def reverse2(s: String): String = {
    val buf = new StringBuilder
    val len = s.length
    for (i <- 0 until len) {
      buf.append(s.charAt(len - i - 1))
    }
    buf.toString
  }
  
  // recursively
  def reverse3(s: String): String = {
    val len = s.length
    if (len == 1) {
      s
    } else {
      reverse3(s.substring(1, len)) + s.charAt(0)
    }
  }

  // recursively, with tail recursion
  def reverse4(s: String): String = {
    val len = s.length
    if (len == 1) {
      s
    } else {
      s.substring(len-1, len) + reverse4(s.substring(0, len-1))
    }
  }
}

The rather long and verbose class (and object) names in my post is in keeping with Steve's post about Java being the Kingdom of Nouns, and because I guess I've worked too long with Spring :-).
The first answer is correct, but probably not quite what most interviewers are looking for. The second one is usually what I get from a majority of people, with minor variations (I like reading the string backwards when I do this in Java, for one). The third and fourth versions are almost always the result of asking if there are other ways to do the same thing. Here is the JUnit test harness to run this code.

// Source: src/test/scala/com/mycompany/smi/coding/StringReverserTest.scala
package com.mycompany.smi.coding

import org.junit._
import org.junit.Assert._

@Test
class StringReverserTest {

  @Test
  def testReverse1() = {
    assertEquals("madA m'I madaM", StringReverser.reverse1("Madam I'm Adam"))
  }

  @Test
  def testReverse2() = {
    assertEquals("madA m'I madaM", StringReverser.reverse2("Madam I'm Adam"))
  }

  @Test
  def testReverse3() = {
    assertEquals("madA m'I madaM", StringReverser.reverse3("Madam I'm Adam"))
  }

  @Test
  def testReverse4() = {
    assertEquals("madA m'I madaM", StringReverser.reverse4("Madam I'm Adam"))
  }
}

Compute the n-th Fibonacci Number

The objective here is to compute the n-th Fibonacci number, where n is provided in the target method's parameter list. I provide two versions of a Fibonacci Number generator below. The recursive version is more intuitive, although someone may ask you do this using iteration, so its probably good to know.

// Source: src/main/scala/com/mycompany/smi/coding/FibonacciGenerator.scala
package com.mycompany.smi.coding

object FibonacciGenerator {

  // iterative version
  def generate1(n: Int): Int = {
    if (n < 0) {
      throw new IllegalArgumentException(
        "Invalid Argument, n must be >= 0")
    }
    if (n == 0) 0
    else if (n == 1) 1
    else {
      var prev2 = 0
      var prev1 = 1
      var sum = 0
      for (i <- 2 to n) {
        sum = prev1 + prev2
        prev2 = prev1
        prev1 = sum
      }
      sum
    }
  }

  // recursive version
  def generate2(n: Int): Int = {
    if (n == 0) 0
    else if (n == 1) 1
    else {
      generate2(n - 2) + generate2(n - 1)
    }
  }
}

Notice that you are calling the same function with the same argument twice multiple times in the recursive version, so caching the results of the calls may result in some improvement in the algorithm. The JUnit test harness is shown below:

// Source: src/test/scala/com/mycompany/smi/coding/FibonacciGeneratorTest.scala
package com.mycompany.smi.coding

import org.junit._
import org.junit.Assert._

class FibonacciGeneratorTest {

  val first8Fibs = List[Int] (0,1,1,2,3,5,8,13)

  @Test
  def testGenerate1() = {
    var results = List[Int]()
    for (i <- 0 until 8) {
      results += FibonacciGenerator.generate1(i)
    }
    assertEquals(results, first8Fibs)
  }

  @Test
  def testGenerate2() = {
    var results = List[Int]()
    for (i <- 0 until 8) {
      results += FibonacciGenerator.generate2(i)
    }
    assertEquals(results, first8Fibs)
  }
}

Print Multiplication Table of 12

The objective here is to print multiplication tables uptil the number provided. There are 4 implementations provided. The first three do exactly what is asked, in slightly different ways, and that is a good thing. The last one actually introduces complexity without any gain, and that was me pandering to the CS person in me, and hopefully I will not get my head cut off for it :-). Actually, I wanted to play with classes, and populating and printing a 2 dimensional array seemed to be a good idea to be able to do that.

// Source: src/main/scala/com/mycompany/smi/coding/MultiplicationTableGenerator.scala
package com.mycompany.smi.coding

import org.apache.commons.lang._

object MultiplicationTableGenerator {

  // just print it out in rows and columns, no formatting
  def generate1(n: Int): Unit = {
    for (i <- 1 to n) {
      for (j <- 1 to n) {
        print("  " + (i * j))
      }
      println
    }
  }

  // print with formatting
  def generate2(n: Int): Unit = {
    val maxwidth = String.valueOf(n * n).length
    for (i <- 1 to n) {
      for (j <- 1 to n) {
        print("  " + lpad(String.valueOf(i * j), maxwidth))
      }
      println
    }
  }

  def lpad(s: String, width: Int): String = {
    val maxpad = " " * width
    val maxpadded = maxpad + s
    val maxlen = maxpadded.length
    maxpadded.substring(maxlen - width, maxlen)
  }

  // use StringUtils.lpad for formatting
  def generate4(n: Int): Unit = {
    val maxwidth = String.valueOf(n * n).length
    for (i <- 1 until n) {
      for (j <- 1 until n) {
        print(StringUtils.leftPad(String.valueOf(i, j), maxwidth))
      }
      println
    }
  }

  // store and print
  def generate4(n: Int): Unit = {
    printFormatted(build(12))
  }

  private def build(n: Int): Matrix[Int] = {
    var matrix = new Matrix[Int](n, n)
    for (i <- 0 until n) {
      for (j <- 0 until n) {
        matrix.set(i, j, ((i + 1) * (j + 1)))
      }
    }
    matrix
  }

  private def printFormatted(matrix: Matrix[Int]): Unit = {
    val maxwidth = String.valueOf(matrix.rows * matrix.cols).length
    for (i <- 0 until matrix.rows) {
      for (j <- 0 until matrix.cols) {
        print("  " + lpad(String.valueOf(matrix.get(i, j)), maxwidth))
      }
      println
    }
  }
}

// only used for generate4()
class Matrix[T](nrows: Int, ncols: Int) {
  val rows = nrows
  val cols = ncols
  private var elements = new Array[T](rows * cols)

  def set(x:Int, y:Int, value:T): Unit = {
    if ((x < cols) && (y < rows)) {
      elements((y * cols) + x) = value
    } else {
      throw new IllegalArgumentException(
        "(" + x + "," + y + ") should be in range (0,0) to (" +
        cols + "," + rows + ")")
    }
  }

  def get(x:Int, y:Int): T = {
    if ((x < cols) && (y < rows)) {
      elements((y * cols) + x)
    } else {
      throw new IllegalArgumentException(
        "(" + x + "," + y + ") should be in range (0,0) to (" +
        cols + "," + rows + ")")
    }
  }
}

The JUnit test is similar to the ones shown already, and is shown below. The only difference is that it doesn't do asserts.

// Source: src/test/scala/com/mycompany/smi/coding/MultiplicationTableGeneratorTest.scala
package com.mycompany.smi.coding

import org.junit._
import org.junit.Assert._

class MultiplicationTableGeneratorTest {

  @Test
  def testGenerate1() = {
    println(">> generate1")
    MultiplicationTableGenerator.generate1(12)
  }

  @Test
  def testGenerate2() = {
    println(">> generate2")
    MultiplicationTableGenerator.generate2(12)
  }

  @Test
  def testGenerate3() = {
    println(">> generate3")
    MultiplicationTableGenerator.generate3(12)
  }

  @Test
  def testGenerate4() = {
    println(">> generate4")
    MultiplicationTableGenerator.generate4(12)
  }
}

Sum up Integers from Text File

The objective here is to read a text file of numbers, one number to a line, and print out the sum of these numbers. There are two implementations of this solution, the first one does it the Java way (with looping), and the second one does it the Scala way (with a foreach over a List. I also have a method to return an Iterator of lines given a file name (which is reused in some related questions, see below).

// Source: src/main/scala/com/mycompany/smi/coding/FileOperator.scala
package com.mycompany.smi.coding

import scala.io._
import scala.collection.mutable.Map
import scala.collection.mutable.LinkedHashMap

object FileOperator {

  // the java way
  def computeSumOfValues1(file: String): Int = {
    var sum = 0
    var lno = 0
    for (line <- lines(file)) {
      lno = lno + 1
      try {
        sum += Integer.parseInt(chomp(line))
      } catch {
        case ex: NumberFormatException => {
          println("ERROR on line " + lno + ", " + chomp(line) + 
            " not number")
        }
      }
    }
    sum
  }

  // the scala way
  def computeSumOfValues2(file: String): Int = {
    var sum = 0
    lines(file) foreach (sum += toNumber(_))
    sum
  }

  private def lines(file: String): Iterator[String] = {
    Source.fromFile(file).getLines
  }

  private def toNumber(s: String): Int = {
    try {
      Integer.parseInt(chomp(s))
    } catch {
      case ex: NumberFormatException => 0
    }
  }

  // maybe just simpler to use StringUtils.chomp()
  private def chomp(s: String): String = {
    try {
      if ((s.charAt(s.length - 1) == '\n') ||
          (s.charAt(s.length - 1) == '\r')) {
        s.substring(0, s.length - 1)
      } else if (s.substring(s.length - 2, s.length) == "\r\n") {
        s.substring(0, s.length - 2)
      } else {
        s
      }
    } catch {
      case ex: StringIndexOutOfBoundsException => s
    }
  }
  ...
}

One thing to note that you should not call any of your application packages java or scala. Because of the way Scala namespaces work, IDEs (and possibly the scala compiler) will get confused about which namespace you are importing from. I initially had com.mycompany.scala as part of my package name, but changed it to com.mycompany.smi in response to the problem described above.
Here are a couple of my own questions. I try and ask different questions from whats on Steve's list, just because, although I am guessing someone who reads Steve's post is probably capable of solving problems of similar complexity.

Compute Word Frequency from Text File

The objective here is to find the word frequency for a given file full of words. The output is a Map of words and their frequencies. As before, the first implementation is in the Java style, and the second one is in the Scala style. The second implementation uses two nested generators with a predicate on the second generator. These two functions are part of the same FileOperator object for the last question.

// Source: src/main/scala/com/mycompany/smi/coding/FileOperator.scala
// (cont'd)
...
object FileOperator {
  ...
  def computeWordFrequencyMap1(file: String): Map[String,Int] = {
    var wordcounts = Map.empty[String,Int]
    for (line <- lines(file)) {
      val words = line.split("[ ,;.!?-]+")
      for (word <- words) {
        if (word.trim.length > 0) {
          addWord(chomp(word), wordcounts)
        }
      }
    }
    wordcounts
  }

  // multiple generators version
  def computeWordFrequencyMap2(file: String): Map[String,Int] = {
    var wordcounts = Map.empty[String,Int]
    for (line <- lines(file);
         word <- line.split("[ ,;.!?]+")
         if (word.trim.length > 0)) {
      addWord(chomp(word), wordcounts)
    }
    wordcounts
  }

  // refactored out to make the second version easier to write
  def addWord(word: String, map: Map[String,Int]): Unit = {
    val origCount = if (map.contains(word)) map(word) else 0
    map + (word -> (origCount + 1))
  }
  ...
}

Sort a Map[String,Int] by Value

Now that we have a Map of word frequencies, we want to know the highest occuring words, so that involves sorting the Map by its value. The code below uses a Scala style comparator function in the keys.sort() call.

// Source: src/main/scala/com/mycompany/smi/coding/FileOperator.scala
// (cont'd)
...
object FileOperator {
  ...
  def sortByValue(unsorted: Map[String,Int]): Map[String,Int] = {
    val sortedMap = new LinkedHashMap[String,Int]()
    val keys = unsorted.keys.toList
    // sort in descending order of value
    val sortedKeys = keys.sort((a,b) => {unsorted(a) > unsorted(b)})
    sortedKeys.foreach(key => sortedMap + (key -> (unsorted(key))))
    sortedMap
  }
}

The JUnit test for the last 3 questions (in FileOperator) are shown below. It uses two test data files, test1.txt, which contains integers, one per line, and test2.txt, which contains free form text spread across multiple lines.

// Source: src/main/scala/com/mycompany/smi/coding/FileOperatorTest.scala
package com.mycompany.smi.coding

import org.junit._
import org.junit.Assert._

class FileOperatorTest {

  @Test
  def testComputeSumOfValues1() = {
    println(">> sumOfValues1 [test1.txt]")
    val sum = FileOperator.computeSumOfValues1(
      "src/test/resources/test1.txt")
    println(sum)
    assertEquals(2667, sum)
  }

  @Test
  def testComputeSumOfValues2() = {
    println(">> sumOfValues2 [test1.txt]")
    val sum = FileOperator.computeSumOfValues2(
      "src/test/resources/test1.txt")
    println(sum)
    assertEquals(2667, sum)
  }

  @Test
  def testComputeWordFrequencyMap1() = {
    println(">> wordFrequencyMap1 [test2.txt]")
    val map = FileOperator.computeWordFrequencyMap1(
      "src/test/resources/test2.txt")
    println(map)
    assertEquals(2, map("morning"))
    assertEquals(1, map("breakfast"))
  }

  @Test
  def testComputeWordFrequencyMap2() = {
    println(">> wordFrequencyMap2 [test2.txt]")
    val map = FileOperator.computeWordFrequencyMap2(
      "src/test/resources/test2.txt")
    println(map)
    assertEquals(2, map("morning"))
    assertEquals(1, map("breakfast"))
  }

  @Test
  def testSortByValue() = {
    println(">> sortByValue")
    val sortedMap = FileOperator.sortByValue(
      FileOperator.computeWordFrequencyMap2("src/test/resources/test2.txt"))
    println(sortedMap)
  }
}

Print out Odd Numbers from 1-99

The objective is pretty clear from the heading. The next 3 questions have single implementations each, mostly focusing on (what I believe are) the Scala way of doing things. They are all contained in a single file Misc.scala, relevant portions of which are split up among the next three sections.

// Source: src/main/scala/com/mycompany/smi/coding/Misc.scala
package com.mycompany.smi.coding

import java.util.Random
import org.apache.commons.lang.StringUtils

object Misc {

  def printOdds(min: Int, max: Int): List[Int] = {
    val range = new Range(min, max, 1)
    range.toList filter (_ % 2 == 1)
  }
  ...
}

Find largest int value in an int array

Given an int array (our method actually populates it first using java.util.Random), find the maximum value in the array.

// Source: src/main/scala/com/mycompany/smi/coding/Misc.scala
...
object Misc {
  ...
  def max(n: Int): Int = {
    // populate
    val randomizer = new Random(n)
    var arr = new Array[Int](n)
    for (i <- 0 until n) {
      arr(i) = randomizer.nextInt(n)
    }
    println(">> input: " + arr.toList)
    // find max in list
    var max = 0
    arr.foreach(elem => if (max < elem) max = elem else max = max)
    max
  }
  ...
}

Format RGB value as a 6 digit Hex String

The objective here is to return a hexadecimal RGB string given three bytes representing the R, G, and B portions of a color. The approach here is not Scala specific, a Java version of this would probably look quite similar.

// Source: src/main/scala/com/mycompany/smi/coding/Misc.scala
...
object Misc {
  ...

  def toHexString(r: Byte, g: Byte, b: Byte): String = {
    val rgb = (r << 16) + (g << 8) + b
    "0x" + StringUtils.leftPad(Integer.toHexString(rgb), 6, '0')
  }
}

And here is the JUnit test for the 3 methods described above.

// Source: src/test/scala/com/mycompany/smi/coding/MiscTest.scala
package com.mycompany.smi.coding

import org.junit._
import org.junit.Assert._

class MiscTest {

  @Test
  def testPrintOdds() = {
    println(">> printOdds")
    println(Misc.printOdds(0, 99))
  }

  @Test
  def testMax() = {
    println(">> max")
    println(Misc.max(10))
  }

  @Test
  def testToHexString() = {
    println(">> toHexString")
    println("RGB(0x00, 0x00, 0x00)=" + Misc.toHexString(0x00, 0x00, 0x00))
    println("RGB(0x11, 0x11, 0x11)=" + Misc.toHexString(0x11, 0x11, 0x11))
    println("RGB(0x11, 0x00, 0x00)=" + Misc.toHexString(0x11, 0x00, 0x00))
    println("RGB(0x00, 0x11, 0x00)=" + Misc.toHexString(0x00, 0x11, 0x00))
    println("RGB(0x00, 0x00, 0x11)=" + Misc.toHexString(0x00, 0x00, 0x11))
    println("RGB(0x11, 0x00, 0x11)=" + Misc.toHexString(0x11, 0x00, 0x11))
  }
}

My take after going this far with Scala is that for an average Java programmer such as myself, learning to use Scala seems to be fairly simple. The map, foreach, etc. methods seem intuitive, but hard to grasp and to apply correctly at first, but become easier with repeated usage. There are also some aspects, such as discussions on currying, covariance, contravariance, etc, that I haven't fully gotten as yet, but hopefully they will also be understandable as I work more with Scala.