Claudio Cherubino's blog Life of a Googler

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
7Feb/086

Project Euler in F# – Problem 5

The exercise we are going to face today is ranked as one of the easiest of Project Euler's, so I don't think you will have any problem in solving it.

However, it allows me to discuss a little bit on algorithm optimization and how to refine a working solution to obtain a better one.

The text of the exercise says:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

Some programming languages (for instance Haskell) provide a native function for evaluating the least common multiple (LCM) of two numbers, i.e. the smallest positive integer that is multiple of both numbers.

In F# we don't have this function, hence we have to write our own code to perform this calculation, and we need it to be able to find the LCM of a set of numbers and not only two.

Let's see the implementation of my algorithm:

#light
open System

let nums = 1 |> Seq.unfold (fun i -> Some (i, i + 1))

let divisibleByList list n =
    Seq.for_all (fun x -> n % x = 0) list

let answer = nums |> Seq.first (fun i -> if divisibleByList [1 .. 20] i then Some (i) else None)

My solution will simply take the integers starting from 1 and check if they are evenly divisible by all numbers from 1 to 20.

We don't know when to stop, so at line 4 we have to create an infinite list of integers.
To do so, we use the unfold function, which allows us to create a lazy list by passing another function to be repeatedly evaluated to provide the elements of the list.

In our case we start from 1 and for each iteration we add one to the previous value, without an upper limit.

At line 6 we have the definition of the divisibleByList function, which takes a list of numbers and an integer n and checks if n is evenly divisible by all the elements of the given list.

This is done by using Seq.for_all, which tests if all the elements of the sequence satisfy the given predicate.

We have now everything we need to find our solution.
Let's just feed the divisibleByList function with the elements of the infinite list of integers and stop when we find the first that satisfy our conditions, thanks to Seq.first.

The solution is complete, but it is not very fast, since it takes about 8 minutes to run in my computer.

We can improve this time by using some very simple math.
First of all, we are sure that the number we are looking for will be a multiple of 2, so we can skip all odd numbers, by changing line 4 with:

let nums = 2 |> Seq.unfold (fun i -> Some (i, i + 2))

With this simple change the execution time drops to 4 minutes, as the amount of integers to check is is actually halved.

I want to go a little further and instead of checking all even numbers we can just test the multiples of 20.
To do so, we change again line 4 with this new one:

let nums = 20 |> Seq.unfold (fun i -> Some (i, i + 20))

Now I can be proud of myself as the execution time is reduced to 25 seconds, twenty times less than the original solution!

Obviously this is not the only solution and there are smarter approaches, maybe we can see them in a future post.

25Jan/080

Project Euler in F# – Problem 9

Today's exercise is Project Euler Problem 9, that says:

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Therefore this time we have to find a triplet (a, b, c), but a brute-force approach would require a billion combinations, since the three numbers can range from 1 to 1000.

However, we can reduce the number of tests exploiting a little algebra.

First of all, c = 1000 - a - b, so only two variables are in play, leading us to a million choices.

Then we go down to half a million, thanks to the constraint that a < b.

According to these premises, here is the F# code:

#light
let sq x = x * x

let ab =
    { for a in 1 .. 1000
      for b in a .. 1000 -> a,b } |> Seq.filter (fun (a,b) -> sq a + sq b = sq (1000 - a - b) ) |> Seq.hd

let answer =
    let a = fst ab
    let b = snd ab
    let c = 1000 - a - b
    a * b * c

At line 5 we enumerate all items of a collection created with list comprehension, i.e. the numbers between 1 and 1000.

Inside this loop we have another loop, but in this case we are interested in all numbers bigger than the current item of the outer collection, i.e. all numbers between a and 1000.

Then, we filter all couples (a, b) keeping only those for which we have: a² + b² = (1000 - a - b)².

According to the text of the exercise, there exists exactly one Pythagorean triplet that satisfies the equation a + b + c = 1000, so we can apply the Seq.hd (head) function to take the first (and only) element of the generated sequence.

At lines 9, 10 and 11 we evaluate a, b and c and finally we multiply them to get the answer.

20Jan/081

Project Euler in F# – Problem 1 (alternative solution)

In the last article I presented a naive solution for the first Project Euler problem, that asks us to "find the sum of all the multiples of 3 and 5 below 1000".

There are many different solutions for the same problem and today I want to show an alternative approach, which is based on a mathematical formula for an arithmetic series.

In our first solution we examined all numbers between 1 and 999 and only kept the multiples of 3 and 5, skipping all the others.

Instead of doing this, we just need to generate the multiples of 3 and 5 and sum them, subtracting the multiples of 15 because they will be included twice.

Remembering that the sum of the first n integer numbers is equal to n * (n+1) / 2, we need to adapt this formula to sum the multiples of a given number, i.e. 3, 5 and 15.

Let's call n the the result of the integer division between the maximum value (in our case 999) and step, where step is 3, 5 or 15.

According to this naming, the sum of multiples will be step * n * (n + 1) / 2, and this formula is very easy to translate in F#:

#light
let sum_mult max step =
  let n = max / step
  step*n*(n + 1)/2

let max = 999
let sum = sum_mult max 3 + sum_mult max 5 - sum_mult max 15
print_any sum

At line 2 we define the sum_mult function, which takes two integer arguments this time: max and step.

The next line shows how to define a local identifier called n, whose scope is limited to the sum_mult function.

The rest of the code is straightforward, we apply the formula to sum the multiples of 3 and 5 and subtract those of 15.

Comparing the complexity of this solution with the previous one we can easily see that we moved from O(n), i.e. going through all the elements of the array, to O(1).

In fact, with this approach the number of evaluations is always fixed to 3, regardless of the maximum number to take into account.

Next time we'll face a new problem, I look forward to receiving your comments.