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);
        else
            Calculate(val*3 + 1);
}

public static void CalculateCollatz2(Int64 val)
{
   while(val != 1)
   {
       if (val % 2 == 0)
           val = val / 2;
       else
           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())
        sb.Append(c);  
    
    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();
    Array.Reverse(charArray);
    
    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;
            
        }
        if(!found)
            newList.Add(im);

    }
    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.

Bonus
Given an Integer how would you store multiple boolean values.

[Flags]
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.

No comments:

Post a comment