Solution for http://ayende.com/blog/163394/new-interview-question

Demo.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace Demo
{
    public static class Algorithm
    {
        public static IEnumerable<long> GetRuns(this int[] n)
        {
            Array.Sort(n);
            int pos = 0;
            while (pos < n.Length - 1)
            {
                int i, j, first = n[pos];
                for (j = pos + 1; j < n.Length; j++)
                {
                    if ((i = n[j]) == first + 1)
                        first = i;
                    else
                        break;
                }
                // store Start and End array position of Run
                yield return Pack(pos, j);
                pos = j;
            }
        }
 
        public static long Pack(int start, int end)
        {
            long run = end;
            run = run << 32;
            run = run | (uint)start;
            return run;
        }
 
        public static void Unpack(long run, out int start, out int end)
        {
            start = (int)(run & uint.MaxValue);
            end = (int)(run >> 32);
        }
    }

    static class Program
    {
        static void Main(string[] args)
        {
            int[] n1 = { 1, 59, 12, 43, 4, 58, 5, 13, 46, 3, 6 };
            int[] n2 = { 1, 2, 3, 5, 6, 7 };

            Console.WriteLine("Test: n1");
            Test(n1);
            Console.WriteLine("");

            Console.WriteLine("Test: n2");
            Test(n2);
            Console.WriteLine("");

            TestRandom(10 * 1000 * 1000);

            Console.ReadLine();
        }

        static void Test(int[] n)
        {
            var runs = n.GetRuns();
            foreach (var run in runs)
                PrintRun(n, run);
            Console.WriteLine("Runs: " + runs.Count().ToString());
        }
 
        static void PrintRun(int[] n, long run)
        {
            bool first = true;
            int start, end;
            // get Start and End array position of Run
            Algorithm.Unpack(run, out start, out end);
            Console.Write('{');
            for (int i = start; i < end; i++)
            {
                if (!first) 
                    Console.Write(',');
                else 
                    first = false;
                Console.Write(n[i]);
            }
            Console.WriteLine('}');
        }
 
        static int[] GetRandomNumbers(int size)
        {
            int[] n = new int[size];
            var rand = new Random();
            for (int i = 0; i < size; i++) n[i] = rand.Next();
            return n;
        }

        static void DummyPrintRun(int[] n, long run) { }

        static void TestRandom(int size)
        {
            Console.WriteLine("TestRandom: " + size);
            int[] n = GetRandomNumbers(size);
            var sw = System.Diagnostics.Stopwatch.StartNew();
            var runs = n.GetRuns();
            foreach (var run in runs)
                DummyPrintRun(n, run);
            sw.Stop();
            Console.WriteLine("Runs: " + runs.Count().ToString());
            Console.WriteLine("Elapsed: " + sw.Elapsed.TotalMilliseconds + "ms");
        }
    }
}