Monday, January 19, 2009

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:

1
2
3
4
5
6
7
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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 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).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 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.

15 comments (moderated to prevent spam):

James Iry said...

Be prepared for functional programmers, too :-). I didn't do all of them, but a couple are worth highlighting.

def flip[A,B,C](f : (A,B)=>C) = (b:B,a:A) => f(a,b)
def reverse3(s : String) = (s foldLeft "")(flip(_ + _))



import scala.io.Source.fromFile
def computeSumOfValues3(file : String) = (fromFile(file).getLines foldLeft 0)(_ + _.toInt)

Sujit Pal said...

Thanks for the code, James, and yes, my objective in learning Scala is to learn functional programming techniques in a language that will hopefully become popular in the mainstream. I am hoping that by the time that happens, I will know enough to grok the functional solutions provided by programmers in interview settings :-).

Your first solution is really cool, btw, but took me a while to get. This post from Tony Morris's blog helped clear things up a bit. Once I understood the usage of foldLeft, of course, the second one was pretty self explanatory.

Thanks again.

Fanf said...

I just looked at the first question (reverse a String), and James comment (James, how can you post so many comments :)

He used a flip method, but as Strings are just a sequence of Char, and char can already by concatenated to string, it could be avoid (moreover, Char concatenation is not too expensive):

===
def reverseFold(s:String) = (""/:s)( (l:String, c:Char) => c+l)
===

I will spend a little time exercices you pointed, they are cool :)

Gabriel C. said...

I keep in my blog afold/reduce 'cheat sheet', maybe you find it useful too:

For the list (a,b,c,d) fold/reduce is:
reduceLeft(f) => f(f(f(a,b),c),d)
foldLeft(Z)(f) => f(f(f(f(Z,a),b),c),d)
("applies the function from the left")

reduceRight(f) => f(a,f(b,f(c,d)))
foldRight(Z)(f) => f(a,f(b,f(c,f(d,Z))))
("applies the function from the right")

Sujit Pal said...

@Fanf: Thanks for the code, its basically walking a string backward (my preferred approach, although I do it in a for loop :-)). I am just beginning to learn about the fold/reduce|left/right methods.

@Gabriel: Thanks for the link to your cheat sheet. Very useful.

Germán said...

Hi!
Here's how you get the max value functionally:

(0 /: myArray)(_ max _)

where /: is syntax sugar for a foldLeft.

Sujit Pal said...

Thanks German, at the time I wrote this post, foldLeft and foldRight were still a bit fuzzy to me, but subsequently I have learned...although I still prefer to explicitly spell them out :-).

Anonymous said...

@German - your method fails if all of the integers are negative. Try reduceLeft and hold the sugar.

@Sujit - I think you need to revisit your answers in a week or two. In particular, none of your answers seem to use higher order functions, pattern matching, the enhanced for loop. You also don't touch on mixins, mutability vs. immutability of data structures, parametric types. While your solutions work, they don't make a compelling case for the language over Java.

I am in the process of learning the language myself, and as a long time Java user found it relatively painless (except the Eclipse plugin. Ouch!) to get started. When I tried to write code like they do in the book, I realized how much I had to learn. Good hunting!

Germán said...

@Anonymous: good point... I only bothered to rewrite Sujit's solution which has the same problem. There's no need for an "initial value" here.

Sujit Pal said...

@Anonymous: Thanks for the comment, and yes, its always a good idea to revisit ones own code in order to see how dumb it looks :-). However...

1) Most of the questions are fairly basic, in the sense that being able to answer them does not imply that one is a good programmer, merely that one is /not/ a bad (or non) programmer. So while there are definitely ways to write the solutions in a more Scala-esque manner, there isn't always a justification for throwing Scala's kitchen sink of features at such problems (sometimes at the expense of readability, see below).
2) I try to write code that I can read (easily), and as you pointed out, my level of maturity in Scala at the time is reflected by the code I wrote in here. Since then, though, I have progressed a bit more, as you can see from the code in here. This attempts a slightly larger problem than these coding examples, and uses all the Scala features you mention.
3) My post does not attempt to make a case (or otherwise) for Scala, I am merely trying to learn the language, and I learn better by doing, so even if the end result is half-baked, I am better off than before I started. Posting these half-baked results also enables me to get help from several kind folks who've been down the road before me, as you can see from the comments to this post (including yours :-)). In some cases, it provides pointers to people who are trying to get into what I did already.

I read my post again following your comment, and I see that in a lot of cases, commenters have jumped in and provided the Scala way to solve the problems (thanks again to all who commented, btw). So I am not sure if I should post an updated version of the solutions, since these appear to be (mostly) taken care of.

Are you still using the Eclipse plugin? I tried using it, but it would freeze on me and eat up characters, so I switched to using Netbeans (for Scala only) and its much better.

Ittay Dror said...

I don't think that StringReverser#reverse4 does a tail recursion. the '+' method is called after the recursion finished, so all the stack needs to be kept. To get tail recursion you usually need to pass in an accumulator as an argument.

Sujit Pal said...

Hi Ittay, I think you are right, my mistake... I based my conclusion on the Fibonacci example I saw somewhere, but there the last call was a standalone call to a recursive fib(). So in this case, we would need to pass in an accumulator in the call to reverse4.

Anonymous said...

one I just picked up recently was a more functional way to obtain min / max from a collection:

MAX:
List(0.0 to 10.0 by 0.1: _*).sort(_>_).head

MIN:
List(0.0 to 10.0 by 0.1: _*).sort(_<_).head

Sujit Pal said...

Very nice, thanks.

kata said...

Hi

Tks very much for post:

I like it and hope that you continue posting.

Let me show other source that may be good for community.

Source: Mock interview questions

Best rgs
David