Month: August 2014

SOLID, CQRS and functional dependency injection

Posted on Updated on

I was prompted to write this after reading Mark Seemann’s post (


Fol­low­ing Sin­gle Respon­si­bil­ity Prin­ci­ple will lead you down the road of hav­ing plenty of small classes.

Open Close Prin­ci­ple will lead you down the way of encap­su­lat­ing the core logic of each type in it, and then del­e­gat­ing all other work to its depen­den­cies, caus­ing most of those small classes to have mul­ti­ple dependencies.

Read the rest of this entry »

“The missing number” programming exercise

Posted on

This is another entry in the brain teaser / programming exercise / interview question collection. It goes like this:

Imagine a list of consecutive numbers. The list is, however, unsorted and one number is missing. Write a function that finds which number is missing with the constraint that you may only allocate O(1) memory (i.e. the amount of memory you use cannot vary with the size of the list).

The fact that the list is unsorted means that you cannot step through in a pairwise fashion and compare each element of the list to the next to see if they are consecutive. Sure, we could sort the array first but the fact that you cannot allocate memory according to the size of the array means that you cannot create a helper array in the solution and certain sorting algorithms are ruled out. An in-place sorting algorithm such as quicksort would do it, but I don’t think that sorting the array is the best way to go.

What if we sum the list? We’re talking about a sequence of integers, after all. It turns out that there is a linear formula for calculating the sum of a sequence of consecutive integers: sum(1..n) = n(n+1) / 2.

This means that you can work out what the sum of the input list should be; all we must do it actually sum the list and the difference between the two will be the missing number. Our implementation then looks like this:

let findMissing (list : int array) =
    let n = list.Length + 1
    let expectedSum = n * (n + 1) / 2
    let actualSum = Seq.sum list
    expectedSum - actualSum

Note the let n = list.Length + 1. We have to add one to the length of the list to get the max element in the list because one element is missing. After that it’s pretty simple!