Interview Problems for goCatch

Introduction

These interview problems were designed to test your ability to:

Read Scala code
Understand the intent of Scala code
Recognise common functional programming idioms
Think laterally
Write efficient code

Preparation

Install SBT version 0.13.x.
Install git.
Clone this project.

Instructions

cd into project directory
Run sbt ~test. sbt will wait for changes to scala code in the project and recompile and run tests in response to each change.
These tests will fail because some functions have been left unimplemented. Your task is to implement these functions so that the tests pass.
Open each file in src/test/scala and implement those functions marked with ??? with the required implementation.

Question 1

Please complete the three functions foo0, foo1 and foo2 to pass all the tests!

The functions are defined as:

def foo0(xs: List[Int]): Int = ???

def foo1(xs: List[Int]): Int = ???

def foo2(xs: List[Int]): Int = ???

Please replace the ??? with your implementation. You will need to read and understand the ScalaCheck properties lower down in the file to figure out what these functions should do.

Question 2

A binary tree is a tree which contains a root node which contain some value and two subtree, left subtree and right subtree, which are also binary tree, for example

        root
       /    \
left tree   right tree

A binary tree is a binary search tree (BST) if all the values in the left subtree being lower than the value of root and all the values being higher than the value of root.

Assuming you are given a N nodes whose values range from [1, N], how many different binary search tree can be created using all of them.

You need to write a function:

def bstCount(n: Int): BigDecimal

which counts how many unique BSTs can be constructed.

For example:

bstCount(1) = 1
Explanation : We have only one tree.
1

bstCount(2) = 2
Explanation : Two trees can be created using two nodes.
1          2
 \        /
  2      1

bstCount(3) = 5
Explanation : Five trees can be created using three nodes.
1          1         2         3        3
 \          \       / \       /        /
  2          3     1   3     1        2
   \        /                 \      /
    3      2                   2    1

Submitting your solutions

To submit your solution, you will need to commit your changes to your local git repository and then generate a patch.

A patch can be generated by running the following git command:

git format-patch origin/master --stdout > solutions.patch

Once you have your patch, attach it to an email.

If you are applying this for a position at goCatch directly, please send the email with your solution to jason@gocatch.com, otherwise send the email to your recruitment agent.