Claudio Cherubino's blog Life of a Googler


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.

Comments (1) Trackbacks (0)
  1. I think you can make that simpler still by using a Seq.fold and letting that do the parsing of the state down the sequence. That way you can get rid of all the list processing stuff from you function. The trick to do grouping is cool.

    type lineType = ANIMALS | NUMBERS
    let processLine (state, animals, numbers) line =
        match line, state with
        | "ANIMALS", _ -> (ANIMALS, animals, numbers)
        | "NUMBERS", _ -> (NUMBERS, animals, numbers)
        | _, ANIMALS -> (state, line::animals, numbers)
        | _, NUMBERS -> (state, animals, line::numbers)
    let (_, animals, numbers) =
        System.IO.File.ReadAllLines("input.txt") |> Seq.fold processLine (ANIMALS, [], [])
    let groupList = Set.of_list >> Set.to_list
    let sortedAnimals = animals |> groupList |> List.sort
    let sortedNumbers = numbers |> groupList |> List.sort
    printf "There are %d animals which are: %A\r\n" (List.length sortedAnimals) sortedAnimals
    printf "There are %d numbers which are: %A\r\n" (List.length sortedNumbers) sortedNumbers
    System.Console.ReadLine() |> ignore

Leave a comment


No trackbacks yet.