“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!

Exceptions and error logging

Posted on Updated on

At my current work I see an awful lot of code that looks like this:

public class ServiceA : IServiceA
    private readonly ILogger _logger;

    public ServiceA(ILogger logger)
        _logger = logger;

    public void DoIt()
            // Do something...
        catch(Exception e)

At first blush this looks reasonable: it has constructor-based dependency injection, an abstraction, error logging… What could my issue be?

Read the rest of this entry »

Tabs or Spaces?

Posted on Updated on

Tabs are blatantly the correct answer.

Tabs separate code content from presentation. Indentation style becomes entirely personal, and each dev can adjust to their own tastes without affecting anyone else. Imagine that I have my editor set to tabs as four spaces. Then, I open a file from another developer who has tabs set as two spaces. Now, in order to write into his file, I have to go into my editor’s options and change my settings to reflect his convention otherwise the code that I’ve written will not match the code that he’s written. Bad times.

Read the rest of this entry »

A functional Fizzbuzz

Posted on Updated on

After reading Scott Wlashin’s post (http://fsharpforfunandprofit.com/posts/railway-oriented-programming-carbonated/) on writing FizzBuzz in a more functional style and with the ability to have more rules (other than 3 => fizz, 5 => buzz, etc) I decided to give it a go myself. This represents the most idiomatic F# I could come up with, and I think it reads pretty well. It uses partial application, list operations, shorthand match-expressions-as-functions and option types.

let carbonate rules i =    
    |> List.choose (fun (divisor, replacement) ->
        if i % divisor = 0 then Some replacement else None)
    |> function [] -> string i | list -> String.concat "" list
let carbonateAll rules = List.map (carbonate rules)
let fizzbuzzbazz = carbonateAll [3, "fizz"; 5, "buzz"; 7, "bazz"]

fizzbuzzbazz [100..110] |> printfn "%A"

See if you can follow how it works.

Testing the queries in your data access layer

Posted on Updated on

When it comes to writing automated tests I have, in the past, tended to ignore the data access layer. Do you really need to test your queries? As long as the code was loosely coupled and I could test everything else, I was happy. After talking at work I was convinced that, in some cases, it might be worth testing your queries themselves in order to check that they’re returning the data that they should be.

This provided a dilemma, because I will always try to avoid writing integration/database tests if I can help it, but how do you test queries without a database? A possible answer is as follows, taken from my post on StackOverflow:


After some deliberation, my colleague and I came up with a way to separate the query from the persistence layer. I threw together a quick example below:

Read the rest of this entry »

Automatically finding missing and duplicate files in CSProj (Revisited)

Posted on Updated on

As promised in I have come back to the problem of detecting errors in Visual Studio project files. I have updated the script to now report CS files that are on disk that do not appear in the list of included (and compiled) files in the Project. This has a few limitations, including that it only works with CS files (although the script could be easily amended to look for any file extension you like).

Read the rest of this entry »

Starting afresh

Posted on Updated on

Some of you may know that I recently started a new position at asos.com. I meant to write about my experiences here a lot earlier, but free time has not exactly been in abundance these last two months. In short: the codebase has its problems but I’m really enjoying it.

First of all: the environment. The ASOS offices are located in Camden, London. This is a cool place to be (the eating to be had around here is simply amazing) and is a convenient 10-minute walk > 15-minute train ride > 10-minute walk from my house (not a bad commute for central London!). The offices are not quite as nice as those at my last company, but that place was pretty hard to top:


Asos looks more like this:

Read the rest of this entry »

Automatically finding missing and duplicate files in CSProj

Posted on Updated on

It’s not uncommon for your CSProj files to become corrupted, or at least invalidated, during a merge. This typically happens when merging two relatively large pieces of work and often takes the form of:

  1. Files referenced in the CSProj that do not exist on disk
  2. Files that exist on disk, are needed for the project to compile but are not included in the CSProj
  3. Files that are on disk and are included, but multiple times

Since this can be quite a pain to fix (the process involves loading the project in Visual Studio and trying to build, getting an error in the concerned project, fixing and trying again) I wrote a simple Powershell script that will analyse your CSProj file and will return all the duplicate file includes as well as all the included files that do not exist on disk. This is a solution for points 1 and 3 above only, as point 2 (finding files on disk that are not included in the CSProj) is a slightly harder problem. I will come back to that in a later revision of the script.

This works well (it’s extremely simple) at displaying errors in your Proj file, but so far you must actually solve the problems manually. It strikes me that actually fixing the CSProj file could also be done automatically, so I am going to revisit this soon (any automatic fixes will, of course, be displayed before they are actually performed and will require the user’s consent to continue).

Here’s the script, I’ll see you back here soon for the two extra features mentioned above.

  [string]$filePath = $(throw "You must supply a file path")

$xml = ([xml] ( gc $filePath ))

$filesIncluded = $xml.Project.ItemGroup.Compile | select -ExpandProperty Include

$invalidPaths = foreach($path in $filesIncluded)
    $fullPath = Join-Path (split-path $filePath) $path

    if(-not (test-path $fullPath)){

$uniquePaths = $filesIncluded | select –unique

$duplicatePaths = Compare-object –referenceobject $uniquePaths –differenceobject $filesIncluded `
| select -ExpandProperty InputObject

    "---- Invalid paths ----"

    "---- Duplicate paths ----"

if((-not $invalidPaths) -and (-not $duplicatePaths))
    "=> No errors found in $filePath"


Converting decimal integers to binary strings in different languages

Posted on

This is a fun post, telling the tale of a simple programming challenge taken in a number of different languages to learn those languages. The challenge is simple: write a function that, given an integer input, will return the binary representation of that number. To start you can assume that the number you have been given is positive, but you can handle negative numbers for extra credit.

Let’s start with C#:

public static string IntToBinary(int i)
	var resultBuilder = new StringBuilder();
		var bit = i % 2;
		resultBuilder.Insert(0, bit.ToString());
		i = i / 2;
	while (i > 0);
	return resultBuilder.ToString();

As you can see, this is a very procedural way of thinking. It’s got a StringBuilder, a conventional loop… Not that pretty. We can do this much more succinctly, but it illustrates the basic procedure for converting a number to binary. You can find the final (right-most) bit of the binary representation by modding the number by 2. To find the right-most-but-one bit, you divide the number by 2 (discarding any result) and then mod the result by 2. Continue until you eventually end up with zero.

Let’s switch language. How about something more functional, like F#?

let rec intToBinary i =
	match i with
	| 0 | 1 -> string i
	| _ ->
		let bit = string (i % 2)
		(intToBinary (i / 2)) + bit

This looks better! What’s different here? First of all we have changed the function to a recursive one.

What about a language like CoffeeScript or, even better, Livescript?

int-to-binary = (i) ->
| i in [0, 1] => i
| _ => "#{int-to-binary i .>>. 1}#{i % 2}"

As usual Livescript produces the shortest code.

Var: Possibly the most contraversial language feature ever?

Posted on Updated on

I’ve been prompted to write this post after it cropped up in my office recently, and I was reminded of a job interview I had a couple of years ago. I’ve also seen some discussions online, and wow, some people hate var. I mean really, really hate it. I even saw one guy in a post saying that if he saw a job applicant using var in an interview he would instantly refuse to hire the guy.

Now, I understand the points that the opponents of var are making, but I don’t agree. I accept that in the case of:

var data = GetData();

we can’t tell what type “data” is, but this is one of the few examples where this is the case. You might also argue that the method “GetData” has been atrociously named (okay, no arguing, it has been atrociously named), but following most programming rules I’d expect that method to return an object of type “Data”. In this example that’s probably not the case, but it does highlight my point, that this:

Read the rest of this entry »