Solution to Ayende's Blog Post http://ayende.com/blog/163394/new-interview-question

AyendeRuns

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

namespace kygeek.AyendeRuns
{
	class Program
	{
		static void Main(string[] args)
		{
			var limit = 1000;
			//var input = GetRandomInput(limit, 1, limit*6);
			int[] input = new[] {1, 59, 12, 43, 4, 58, 5, 13, 46, 3, 6};
			
			var sw = System.Diagnostics.Stopwatch.StartNew();
			var bucketContainer = new BucketContainer();
			for (int i = 0; i < input.Length; i++)
			{
				bucketContainer.Insert(input[i]);
			}
			var results = bucketContainer.GetBuckets().Select(b => Enumerable.Range(b.Start, b.End - b.Start + 1).ToArray()).ToArray();
			sw.Stop();
			
			var buckets = bucketContainer.GetBuckets();
			foreach (var bucket in buckets)
			{
				Console.WriteLine("Start: {0}, End: {1}, Total: {2}", bucket.Start, bucket.End, bucket.End-bucket.Start+1);
			}
			Console.WriteLine(sw.Elapsed.TotalMilliseconds + "ms");
			
		}

		private static int[] GetRandomInput(int count, int min, int max)
		{
			var r = new Random();
			var values = new int[count];
			for (var i = 0; i < count; i++)
			{
				var value = r.Next(min, max);
				while (values.Contains(value))
					value = r.Next(min, max);
				values[i] = value;
			}
			Console.WriteLine("Got random input...");
			return values;
		}
	}

	public class Bucket
	{
		public int Start { get; set; }
		public int End { get; set; }
	}

	public class BucketContainer
	{
		private readonly List<Bucket> _items;

		public BucketContainer()
		{
			_items = new List<Bucket>();
		}

		public void Insert(int value)
		{
			if (_items.Count==0)
				_items.Insert(0, new Bucket() { Start = value, End = value });
			else 
				Insert(value,0,_items.Count-1);
		}

		private void Insert(int value, int start, int end)
		{
			var midpoint = (end + start) / 2;
			var midPointStart = _items[midpoint].Start;
			if (start == end)
			{
				if (value < midPointStart)
				{
					_items.Insert(start, new Bucket() {Start = value, End = value});
					Merge(start);
				}
				else
				{
					_items.Insert(start + 1, new Bucket() {Start = value, End = value});
					Merge(start+1);
				}
				return;
			}

			// let's cut the list in half
			if (value < midPointStart)
			{
				Insert(value, start, midpoint);
			}
			else
			{
				Insert(value, midpoint+1, end);
			}
		}


		private void Merge(int bucket)
		{
			if (bucket < _items.Count - 1)
			{
				if (_items[bucket].End == _items[bucket + 1].Start-1)
				{
					_items[bucket].End = _items[bucket + 1].End;
					_items.RemoveAt(bucket + 1);
				}
			}
			if (bucket > 0)
			{
				if (_items[bucket].Start == _items[bucket - 1].End+1)
				{
					_items[bucket].Start = _items[bucket - 1].Start;
					_items.RemoveAt(bucket - 1);
				}
			}
		}
		
		public List<Bucket> GetBuckets()
		{
			return _items;
		}
	}
}