Claudio Cherubino's blog Life of a Googler

26Aug/091

Functional programming interview question

I think that examining the hiring process of a company you can understand a lot of what would be working there.

As Joel Spolsky wrote, you should only hire people who are Smart and Get Things Done and a good way to be sure that a candidate belongs to this category is testing his/her skills with a good programming exercise, one easy enough to be solved in 15 minutes but that requires the use of brain.

Starling Software clearly describes its interview process on a page of its website and proposes a couple of sample programs for the potential applicants. In the first problem you are asked to use Haskell to process a given file (obviously we will use F#):

The file input.txt contains lists of words, one per line, in two categories, NUMBERS and ANIMALS. A line containing just a category name indicates that the words on the following lines, until the next category name, belong to that category. Read this file as input (on stdin) and print out a) a sorted list of the unique animal names encountered, and b) a list of the number words encountered, along with the count of each. Feel free to chose your output format.

The algorithm to solve the exercise is easy: we read the file line by line and remember the current category (NUMBERS or ANIMALS) in order to add the next words to the appropriate list. When the file is over, we filter duplicates and sort the list of animals and group the numbers together with their counts.

The only problem is knowing how to manage the concept of state of the application in a functional way. In the imperative paradigm you define a variable to keep the state and change its value when you find a new category in the input file. In functional programming you don't use state variables instead you use function parameters and recursive calls:

open System
open System.IO

let animals_and_number filename =
  let rec process_line lines category animals numbers =
    match lines with
    | [] -> (animals, numbers)
    | x::xs -> match x with
               | "NUMBERS" -> process_line xs "NUMBERS" animals numbers
               | "ANIMALS" -> process_line xs "ANIMALS" animals numbers
               | x -> match category with
                      | "NUMBERS" -> process_line xs category animals (x :: numbers)
                      | "ANIMALS" -> process_line xs category (x :: animals) numbers
                      | _ -> process_line xs category animals numbers
  let all_lines = File.ReadAllLines(filename) |> Seq.to_list
  process_line all_lines "" [] []

let filename = "input.txt"
let (animals, numbers) = animals_and_number filename
let sorted_animals = animals |> Seq.distinct |> Seq.sort |> Seq.to_list
let counted_words = numbers |> Seq.countBy (fun x -> x) |> Seq.to_list

printf "Animals: %A\n" sorted_animals
printf "Numbers: %A" counted_words

The recursive process_line function has four parameters: the list of lines to be processed, the current category (initially an empty string) and the two lists of animals and numbers found so far.

For each new line we first check if it represents one of the categories. In this case we have to change state, i.e. discard the element and recursively call the same function with the correct category parameter.

If the element processed is not a category we only have to add it to the animals or number list, according to the value of the category parameter.

At the end of the animals_and_number function (when lines is empty) we return a tuple made of the two lists created.
The rest of the job is calling some standard library functions to filter duplicates, sort and count the elements of the sequences.

13Jun/0911

Merging arrays

Thanks to interviewpattern.com I discovered that one of the classical Amazon interview questions is writing a snippet of code to merge two sorted arrays:

"Suppose we have two sorted arrays A[] of m elements and B[] of n elements. Write a function merge which would merge this two arrays into new sorted array C[] in O(n) time as shown on the picture".

MergeArrays

This problem is also a classical exercise for functional programming learners that shows the conciseness of functional code in comparison with imperative one.

The solution presented on the original page is written in C# and is longer than 40 lines of code, while we can solve the same problem in F# with less than 10 lines:

let rec merge_arrays a b =
  match (a, b) with
  | (a, []) -> a
  | ([], b) -> b
  | (x::xs, y::ys) -> if (x < y) then
                        (x :: (merge_arrays xs (y::ys)))
                      else
                        (y :: (merge_arrays (x::xs) ys))

Besides being shorter, I also find the functional code to be much easier to understand. Do you agree with me?

23Jan/093

Facebook FizzBuzz

Have you ever tried looking for "FizzBuzz" on a search engine?

If you do, you'll surely land on this page on Coding Horror, the blog written by Jeff Atwood.

To make a long story short, Jeff states that the vast majority of the developers is unable to write a tiny program that should take no more than 10 minutes to code.

This is the famous FizzBuzz problem:

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

You should be outraged now, if you aren't I hope you don't make a living as a developer! :)

I found out that Facebook also considers FizzBuzz as a good starting test for job applicants. There is a programming puzzles page, where you can find a set of good problems, ranging from blindingly easy to very hard.

The first one is called HoppityHop! and it is just a variation of the good old FizzBuzz:

The program should iterate over all integers (inclusive) from 1 to the number expressed by the input file. For example, if the file contained the number 10, the submission should iterate over 1 through 10. At each integer value in this range, the program may possibly (based upon the following rules) output a single string terminating with a newline.

* For integers that are evenly divisible by three, output the exact string Hoppity, followed by a newline.
* For integers that are evenly divisible by five, output the exact string Hophop, followed by a newline.
* For integers that are evenly divisble by both three and five, do not do any of the above, but instead output the exact string Hop, followed by a newline.

Being a developer myself I couldn't resist writing a solution for this problem, obviously in F#:

#light

let HoppityHop n =
  let printHop x =
    match x with
    | x when (x % 15 = 0)-> printfn "Hop"
    | x when (x % 3 = 0) -> printfn "Hoppity"
    | x when (x % 5 = 0) -> printfn "Hophop"
    | _ -> ()
  [1 .. n] |> Seq.iter printHop

I know many of you will feel the urge to suggest a better solution, you're welcome, the comment area is yours to use!

1Jul/0812

The missing number

There is an interesting series of programming job interview challenges proposed by Dev102.com, which is now at its tenth puzzle:

This week question is pretty easy. Your input is an unsorted list of n numbers ranging from 1 to n+1, all of the numbers are unique, meaning that a number can’t appear twice in that list. According to those rules, one of the numbers is missing and you are asked to provide the most efficient method to find that missing number. Notice that you can’t allocate another helper list, the amount of memory that you are allowed to allocate is O(1). Don’t forget to mention the complexity of your algorithm…

I'm not sure I understood correctly the constraint related to the memory allocation.

In my opinion, when they say we are limited to O(1), they mean that we can only allocate a single numeric variable and not any other data structure.

According to this interpretation, the solution is quite easy.

First of all, we take our only variable and store into it the sum of all the numbers between 1 and n + 1, which can be easily computed remembering that 1 + 2 + ... + n = n (n + 1) / 2.

Then, we subtract each element of the array from this value, eventually the result is actually our missing number.

The functional implementation of this imperative algorithm is straightforward:

#light

let sum n = ((n + 1) * (n + 2)) / 2

let answer nums = (nums |> List.length |> sum) - (List.reduce_left (+) nums)

Let's talk about the complexity of the algorithm.

If the length of the input list list is known, evaluating the sum of the first n natural numbers takes O(1), otherwise we have to scan the entire list, i.e. O(n).

Then we have to subtract each element of the list, and this takes another iteration, so another O(n).

Therefore we have O(n) + O(n), which is definitely O(n), and can be easily optimized a little by scanning the list only once.

The only problem left is: "am I following the instructions"?

10Jun/088

Google Interview Question: Product of other Elements in an Array in O(n)

Last time I was interviewed for a software development engineer position, the recruiter asked me some of the classical Microsoft interview questions, such as "How Would You Move Mount Fuji?" or "How many gas station are there in your country?".

It was the first time for me to be asked such questions but having obtained the job I think my answers were good enough.

After that day, I looked for other well-known interview questions and I discovered that Google has a totally different approach, focusing on algorithms, data structures and complexity.

For instance, one of Google interview questions says:

There is an array A[N] of N integers. You have to compose an array Output[N+1] such that Output[i] will be equal to the product of all the elements of A[] except A[i].

Example:
INPUT:[4, 3, 2, 1, 2]
OUTPUT:[12, 16, 24, 48, 24]

Solve it without division operator and in O(n).

Without the two constraints at the end of the puzzle it would have been straightforward, but now we have to be smart.

Actually, the product of all elements of A[] except A[i] is equal to the product of all elements before A[i] and those after A[i].

We can traverse A[] twice, once from left to right and once in the opposite way and multiply all the elements we find before A[i].

We'll pretend to have a new array called Output[] to store the output of the first pass, assigning Output[i] the product of all elements preceding A[i]:

let rec firstpass product input =
    match input with
    | [] -> []
    | x::xs -> product :: firstpass (product * x) xs

For the second pass we need to move from right to left, but this can be done by reversing the input arrays and moving as usual:

let secondpass product input arr =
    let rev_input = List.rev input
    let rev_arr = List.rev arr
    let rec rev_secondpass product (input:list<int>) arr =
      match arr with
      | [] -> []
      | x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]

    rev_secondpass product rev_input rev_arr

Both firstpass and secondpass expect an integer argument called product, which will be always be 1 at the beginning and will be used to store the intermediate products during the recursive calls.

With these functions we can just define an input array and apply them to get the result.

The following is the complete F# code:

#light

let input = [ 4; 3; 2; 1; 2 ]

let answer values =

  let rec firstpass product input =
    match input with
    | [] -> []
    | x::xs -> product :: firstpass (product * x) xs

  let secondpass product input arr =
    let rev_input = List.rev input
    let rev_arr = List.rev arr
    let rec rev_secondpass product (input:list<int>) arr =
      match arr with
      | [] -> []
      | x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]

    rev_secondpass product rev_input rev_arr

  values |> firstpass 1 |> secondpass 1 values