Friday 15 February 2008

Better then FizzBuzz

Anyone that has done a few interviews has come to conclusion that a lot of people that apply for programming jobs cant program. In response to this usually the first question given to new applicants is a simple programming question like fizzbuzz. FizzBuzz is an interesting problem but there is a lot of other problems out there that are just as simple and can provide much more information.

Collatz conjecture

Take any natural number n (excluding 0). If n is even, halve it (n / 2), otherwise multiply it by 3 and add 1 to obtain 3n + 1. The conjecture is that for all numbers this process converges to 1. It has been called "Half Or Triple Plus One", sometimes called HOTPO.

public static void Calculate(Int64 val)
    if (val > 1)
        if (val % 2 == 0)
            Calculate(val / 2);
            Calculate(val*3 + 1);

public static void CalculateCollatz2(Int64 val)
   while(val != 1)
       if (val % 2 == 0)
           val = val / 2;
           val = val*3 + 1;

This is one of my favourite tests, any programmer should be able to see in seconds that the very nature of this problem lends itself to a recursive solution. They should also see the obvious stackoverflow that is possible. Either solving this recursively(Calculate) or with an iterator(Calculate2) allows you to dig a little further into the candidates programming knowledge.

Reversing a String

Given a string reverse the output

public static string Reverse(string inValue)
    StringBuilder sb = new StringBuilder();
    foreach (char c in inValue.Reverse())
    return sb.ToString();

public static string Reverse2(string inValue)
    int length = inValue.Length;
    char[] charArray = new char[length];
    foreach(char c in inValue)
        charArray[--length] = c;
    return new string(charArray);

public static string Reverse3(string inValue)
    char[] charArray = inValue.ToCharArray();
    return new string(charArray);

public static string Reverse4(string str)
     char[] charArray = str.ToCharArray();
     int len = str.Length - 1;
     for (int i = 0; i < len; i++, len--)
         charArray[i] ^= charArray[len];
         charArray[len] ^= charArray[i];
         charArray[i] ^= charArray[len];
     return new string(charArray);

This question is very open ended and leading. It is open enough to see if you can entice the candidate to ask some questions about the functions possible use. The result is equally as useful. Some will use the C# library(Reverse, Reverse3) to help themselevs out. Others, usually with a C++ background, will code it with a simple for loop like in Reverse2. If they are really creative they will do some XOR Bit Shifting(Reverse4) (as I found demonstrated). Equally, the question can be used to lead to such things as Big O notation or memory footprints etc. It is possible to mix it up a little as well asking them to check if the string is a palindrome etc.

Two lists Problem

Given two lists remove all the values from the first list that are present in the second list.

public static IEnumerable<int> ConvertList(List<int> inMain, List<int> inExclude)
   return inMain.Except(inExclude);

public static List<int> ConvertList2(List<int> inMain, List<int> inExclude)
    foreach (var i in inExclude)
        inMain.Remove(i) ;

    return inMain;

public static List<int> ConvertList3(List<int> inMain, List<int> inExclude)
    bool found;
    List<int> newList = new List<int>();
    foreach (var im in inMain)
        found = false;
        foreach (var ie in inExclude)
            if (im == ie)
                found = true;

    return newList;

This is not my favourite question but a lot of candidates either wont be able to answer it or will come up with an implementation like shown in example 3 which is generally a bad sign.

Given an Integer how would you store multiple boolean values.

public enum Permissions
    Read = 1,
    Write = 2,
    Update = 4,
    RunScripts = 8,
    All = Read | Write | Update | RunScripts,

I really don't consider this a very good opening question but it could be asked at some point during the interview process to get an idea of overall knowledge.

I think the idea behind FizzBuzz is a great one, however, if you are truly interested in not wasting time then it isn't enough to just find out if they can code a simple problem. You need to use that simple problem to extract as much information as possible in the shortest amount of time.

The Evils of regions#region

I still remember when I first used the region field, it was a happier time, I was blissfully unaware of the problems that regionalizing your code was creating, I think everyone was. I picture the region directive being added as almost an after thought. I see someone at Microsoft saying "wow this tool sure generated so butt ugly code cant we hide that?" Regions to the rescue! A region is a preprocessor directive that allows programmers to hide sections of there code by using #region and #endregion syntax.
MSDN says:
#region lets you specify a block of code that you can expand or collapse when using the outlining feature of the Visual Studio Code Editor.
For example:

#region MyClass definition
public class MyClass 
static void Main() 

Regions the clean solution
Now I know what you might be thinking. What is so bad about that? How could that little region be causing so many problems? It is only there to help clean up your code a little. Ahh but wait. Lets take a closer look at that. It helps clean up your code. Does it? Or does it just make the code LOOK cleaner.

Regions making the ugly look pretty

Sadly, the same thing that spawned the region directive is the same thing it is being misused for now. I will just make a little hack here or there add a region directive and everything will be OK. The sooner everyone stops using regions the sooner developers will stop thinking its Okay to sweep their hacks under a rug that I find myself constantly cleaning.

BOO Who?

Anybody that reads Ayede Rahien's blog will notice that he is writing a book called Building Domain Specific Languages with BOO. What? BOO? What the hell is BOO? I am a big fan of Anede and quickly wanted to get up to speed with BOO and what it is all about. Most of the my initial reading was taken right off the BOO website.

Boo is a new object oriented statically typed programming language for the Common Language Infrastructure with a python inspired syntax and a special focus on language and compiler extensibility.
GREAT! I Love python's syntax! Who needs all those brackets anyway. But why do we need a whole new language to do Domain Specific Programming? And wait, what's up with Iron Python are these two not destine to clash? What am I not understanding here?

IronPython is not a take on Python it is just a reimplementation of python, where as BOO is completely different Language that is based off python syntax. Boo is statically typed, while IronPython is dynamical typed. OK, they are not even close to the same thing. Its another one of the those classic programming examples where upon first glance something that looks like a snake and moves like a snake but is actually some type of Duck.

OK! Then the difference has to be with the fact it is a Domain Specific Language. Hmmm "Domain Specific" I think I know what that means... but do I?? I mean I have heard the term thrown around and thought I had a grasp on it. I must still be missing something.....

Martin Fowler says
Domain specific language (DSL) is a computer language that's targeted to a particular kind of problem, rather than a general purpose language that's aimed at any kind of
software problem.
OK well that is kind of what I thought. SO if company XYZ has a corporate policy that all phone numbers have to be 3 digits, why wouldn't I just create a method or an even better an extension method. Seems pretty straight forward...

But Wait is that really a DSL? If you dig into it there are 4 types of DSL(From Chapter one of building DSL's) External, Graphical, Fluent and Internal/Embedded. OK now we are getting into it.

  • External is specifying everything from how an If statement works to operator semantics.
  • Graphical is a DSL that is not textual, but rather uses shapes and lines in order to express intent
  • Fluent - are interfaces are a way to structure your API in such a fashion that operations flow in a natural manner.
  • Embedded - Internal DSL are built on top of an existing language, but they don’t try to remain true to the original programming language syntax. They try to express things in a way that would make sense to both the author and the reader, not to the compiler.
Ayede Says:
Extension methods and lambda expression will certainly help, but they will not change the fundamental syntax too much. There are better alternatives for writing Domain Specific Languages than C#.
A DSL should be readable for someone who is familiar with the domain, not the programming language. A DSL built on top of an existing language can also be problematic, since you want to limit the options of the language, in order to make it clearer in what is going on, rather than turn the DSL into a fully fledged programming language; we already have that in the base language, after all. The main purpose of an internal DSL is to reduce the amount of stuff that you need to make the compiler happy, and increase the clarity of the code in question.

So what does this all mean? Well it means he sold another book....