A problem that I was given during a recent interview was to combine two sorted integer arrays. I added short circuits if one of the provided arrays did not have an elements. I then create a loop and iterators to track the progress of working through each array independently.

Solution:

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CombineArrays
{
public class CombArrays
{
public int[] GetArays(int[] a, int[] b)
{
int[] combinedArray = new int[a.Length + b.Length];

if (b.Length > 0 && a.Length < 1)
return b;
else if (a.Length > 0 && b.Length < 1)
return a;
else if(a.Length < 1 && b.Length < 1)
throw new ArgumentException("The arrays should contain values.");
else
{
int aCounter = 0;
int bCounter = 0;
int cArrayCount = 0;
int last = -1;

while (cArrayCount < combinedArray.Length)
{

int aValue = -1;
int bValue = -1;

if (aCounter < a.Length)
aValue = a[aCounter];
if (bCounter < b.Length)
bValue = b[bCounter];

if (aValue >= last || bValue >= last)
{

if ((aValue >= bValue && bValue >= last) || (aValue == -1 && bValue >= last))
{
combinedArray[cArrayCount] = bValue;
last = bValue;
bCounter++;
}
else if ((bValue >= aValue && aValue >= last) || (bValue == -1 && aValue >= last))
{
combinedArray[cArrayCount] = aValue;
last = aValue;
aCounter++;
}
}
cArrayCount++;

}
}

return combinedArray;
}
}
}

```

Unit Tests:

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using NUnit.Framework;
using CombineArrays;

namespace CombineArraysTests
{
[TestFixture]
public class CombineArraysTests
{
[Test]
public void A_ArrayOnly()
{
int[] a = { 2, 5, 6, 9, 10 };
int[] b= new int[]{};

CombArrays ca = new CombArrays();
int[] actual = ca.GetArays(a, b);
int[] expected = { 2, 5, 6, 9, 10};

Assert.AreEqual(expected, actual);

}

[Test]
public void B_ArrayOnly()
{
int[] a =  new int[] { };
int[] b = { 2, 5, 6, 9, 10 };

CombArrays ca = new CombArrays();
int[] actual = ca.GetArays(a, b);
int[] expected = { 2, 5, 6, 9, 10 };

Assert.AreEqual(expected, actual);

}

[Test]
public void No_Good_Arrays()
{
int[] a = new int[] { };
int[] b = new int[] { };

CombArrays ca = new CombArrays();

var ex = Assert.Catch<ArgumentException>(() => ca.GetArays(a, b));

StringAssert.Contains("The arrays should contain values.", ex.Message);

}

[Test]
public void Combine2Arrays_AShorter()
{
int[] a = { 3, 7, 8 };
int[] b = { 2, 5, 6, 9, 10 };

CombArrays ca = new CombArrays();
int[] actual = ca.GetArays(a, b);
int[] expected = { 2, 3, 5, 6, 7, 8, 9, 10 };

Assert.AreEqual(expected, actual);

}

[Test]
public void Combine2Arrays_BShorter()
{
int[] a = { 2, 5, 6, 9, 10 };
int[] b = { 3, 7, 8, 12 };

CombArrays ca = new CombArrays();
int[] actual = ca.GetArays(a, b);
int[] expected = { 2, 3, 5, 6, 7, 8, 9, 10, 12 };

Assert.AreEqual(expected, actual);

}

[Test]
public void Combine2Arrays_AllSameValues()
{
int[] a = { 2,2,2,2,2 };
int[] b = { 2,2,2,2 };

CombArrays ca = new CombArrays();
int[] actual = ca.GetArays(a, b);
int[] expected = { 2, 2, 2, 2, 2, 2, 2, 2, 2 };

Assert.AreEqual(expected, actual);

}

}
}

```

For this post I thought I would spend a little bit of time looking at two basic search algorithms. The first is a simple sequential search, the second is a binary search.

For a simple sequential search I implemented it to perform a search on an integer array. The search method returns a bool indicating if the value was found or not. This will return true on the first element that has a match. The implementation of this search is a single iteration through the array to see if the element exists. Not complicated but not very efficient.

1/31/2014 – Edit: Added a break when item is found on the sequential search.

```    public class Searches
{
public bool BasicSequentialSearch(int[] array, int value)
{
bool isFound = false;

for (int i = 0; i < array.Length; i++)
{
if (array[i] == value)
{
isFound = true;
break;
}
}
return isFound;
}
}
```

So now the question is what can we do with this? Well we could adapt it to return the number of instances of a value found:

```        public int BasicSequentialSearchCounter(int[] array, int value)
{
int count = 0;

for (int i = 0; i < array.Length; i++)
{
if (array[i] == value)
count++;
}
return count;
}
```

Another thing might be to tweak it to show the min or max values of a given array. Two things of note, one is that I start the array loop a position 1 since I already use the 0 position as the seed value for the min or max check.

```        public int BasicSequentialSearchMax(int[] array)
{
int max = array[0];

for (int i = 1; i < array.Length; i++)
{
if (array[i] > max)
max = array[i];
}
return max;
}

public int BasicSequentialSearchMin(int[] array)
{
int min = array[0];

for (int i = 1; i < array.Length; i++)
{
if (array[i] < min)
min = array[i];
}
return min;
}
```

So fun and potentially useful particularly for small datasets if you need something quick and dirty.

Another basic search is the Binary Search. The binary search works by splitting the determining the mid point of an array and looking above or below it. One of the key rules to note on this is that this type of search will only work on a sorted dataset (preferably ascending). We can approach this in two ways. One is iteratively and one is using recursion. Both of these searches will return the position in the array the value is located at or return a -1.

Iterative Binary Search.

```        public int InterativeBinarySearch(int[] array, int searchValue)
{
int upperLimit = array.Length - 1;
int lowerLimit = 0;
int mid;

while (lowerLimit <= upperLimit)
{
mid = (upperLimit + lowerLimit) / 2;
if (array[mid] == searchValue)
return mid;
else if (searchValue <= array[mid])
upperLimit = mid - 1;
else
lowerLimit = mid + 1;
}

return -1;
}
```

Recursive Binary Search:

```        public int RecursiveBinarySearch(int[] array, int searchValue, int upperLimit, int lowerLimit)
{
int mid = -1;
if (lowerLimit > upperLimit)
return mid;
else
{
mid = (upperLimit + lowerLimit) / 2;
if (array[mid] == searchValue)
return mid;
else if (searchValue <= array[mid])
mid = RecursiveBinarySearch(array, searchValue, mid - 1, lowerLimit);
else
mid = RecursiveBinarySearch(array, searchValue, upperLimit, mid + 1);
}
return mid;

}

```

Now lets look a bit at the performance for some of these two binary search implementations. I am going to build a harness similar to the one I did for the Sorts example I put together previously. I want to create several arrays of different sizes and search them for a given value.

Test Harness:

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using BasicSearches;

namespace BinarySearchHarness
{
class Program
{
static void Main(string[] args)
{
int iterationCount = 0;
int arraySize = 10000;

while (iterationCount < 3)
{

int[] orderedArray = CreateOrderedArray(arraySize);

RunIterativeBinarySearch(orderedArray);
RunRecursiveBinarySearch(orderedArray);

arraySize *= 10;
iterationCount++;
}
}

private static void RunRecursiveBinarySearch(int[] orderedArray)
{
Stopwatch timer = new Stopwatch();
Searches search = new Searches();
Console.WriteLine("------------------- Start Recursive Search test for {0} values.--------------", orderedArray.Length);
for (int i = 1; i <= 4; i++)
{
int searchValue = (orderedArray.Length / i) -4;

timer.Start();
search.RecursiveBinarySearch(orderedArray, searchValue, orderedArray.Length,0);
timer.Stop();
Console.WriteLine("Seach value: {0} was found in {1} ticks.", searchValue, timer.ElapsedTicks);
timer.Reset();

}
}

private static void RunIterativeBinarySearch(int[] orderedArray)
{
Stopwatch timer = new Stopwatch();
Searches search = new Searches();
Console.WriteLine("------------------- Start Interative Binary Search test for {0} values.--------------", orderedArray.Length);
for (int i = 1; i <= 4; i++)
{
int searchValue = (orderedArray.Length / i) - 4;

timer.Start();
search.InterativeBinarySearch(orderedArray, searchValue);
timer.Stop();
Console.WriteLine("Seach value: {0} was found in {1} ticks.", searchValue, timer.ElapsedTicks);
timer.Reset();

}
}

private static int[] CreateOrderedArray(int arraySize)
{
int[] array = new int[arraySize];
int seed = 1;
for(int i = 0; i < arraySize; i++)
{
array[i] = seed;
seed++;
}

return array;
}
}
}
```

The harness creates the following output. You can see the initial cost of the initialization and the slight increase in cost for searching as the array size increased:

Unit Tests:

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using NUnit.Framework;
using BasicSearches;

namespace BasicSearchTests
{
[TestFixture]
public class BasicSearchTests
{
[Test]
public void RunSearchThatReturnsTrue()
{
int searchValue = 10;
int[] arrayToSearch = { 3, 6, 1, 50, 23, 3, 56, 3, 10 };
bool expected = true;
Searches mySearch = new Searches();
bool actual = mySearch.BasicSequentialSearch(arrayToSearch, searchValue);

Assert.AreEqual(expected, actual);
}

[Test]
public void RunSearchThatReturnsFalse()
{
int searchValue = 15;
int[] arrayToSearch = { 3, 6, 1, 50, 23, 3, 56, 3, 10 };
bool expected = false;
Searches mySearch = new Searches();
bool actual = mySearch.BasicSequentialSearch(arrayToSearch, searchValue);

Assert.AreEqual(expected, actual);
}

[Test]
public void RunSearchThatReturns_NonZero()
{
int searchValue = 3;
int[] arrayToSearch = { 3, 6, 3, 50, 23, 3, 56, 3, 10 };
int expected = 4;
Searches mySearch = new Searches();
int actual = mySearch.BasicSequentialSearchCounter(arrayToSearch, searchValue);

Assert.AreEqual(expected, actual);
}

[Test]
public void RunSearchThatReturns_Zero()
{
int searchValue = 68;
int[] arrayToSearch = { 3, 6, 3, 50, 23, 3, 56, 3, 10 };
int expected = 0;
Searches mySearch = new Searches();
int actual = mySearch.BasicSequentialSearchCounter(arrayToSearch, searchValue);

Assert.AreEqual(expected, actual);
}

[Test]
public void RunMaxSearchThatReturns_FirstPosition()
{
int[] arrayToSearch = { 60, 6, 3, 50, 23, 3, 56, 3, 10 };
int expected = 60;
Searches mySearch = new Searches();
int actual = mySearch.BasicSequentialSearchMax(arrayToSearch);

Assert.AreEqual(expected, actual);
}

[Test]
public void RunMaxSearchThatReturns_LastPosition()
{
int[] arrayToSearch = { 60, 6, 3, 50, 23, 3, 56, 3, 65 };
int expected = 65;
Searches mySearch = new Searches();
int actual = mySearch.BasicSequentialSearchMax(arrayToSearch);

Assert.AreEqual(expected, actual);
}

[Test]
public void RunMinSearchThatReturns_TwoFromLastPosition()
{
int[] arrayToSearch = { 60, 6, 3, 50, 23, 3, 56, 3, 2 };
int expected = 2;
Searches mySearch = new Searches();
int actual = mySearch.BasicSequentialSearchMin(arrayToSearch);

Assert.AreEqual(expected, actual);
}

[Test]
public void RunMinSearchThatReturns_NegOne()
{
int[] arrayToSearch = { 60, 6, -1, 50, 23, 3, 56, 3, 65 };
int expected = -1;
Searches mySearch = new Searches();
int actual = mySearch.BasicSequentialSearchMin(arrayToSearch);

Assert.AreEqual(expected, actual);
}

[Test]
public void RunInterativeBinarySearchThatReturnsNegOne()
{
int searchValue = 0;
int[] arrayToSearch = { 2,3,4,5,6,7,8,9,10,11 };
int expected = -1;
Searches mySearch = new Searches();
int actual = mySearch.InterativeBinarySearch(arrayToSearch,searchValue);

Assert.AreEqual(expected, actual);
}

[Test]
public void RunInterativeBinarySearchThatReturnsThree()
{
int searchValue = 4;
int[] arrayToSearch = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
int expected = 2;
Searches mySearch = new Searches();
int actual = mySearch.InterativeBinarySearch(arrayToSearch, searchValue);

Assert.AreEqual(expected, actual);
}

[Test]
public void RunRecursiveBinarySearchThatReturnsNegOne()
{
int[] arrayToSearch = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
int searchValue = 0;
int upperLimit = 9;
int lowerLimit = 0;
int expected = -1;
Searches mySearch = new Searches();
int actual = mySearch.RecursiveBinarySearch(arrayToSearch, searchValue, upperLimit, lowerLimit);

Assert.AreEqual(expected, actual);
}

[Test]
public void RunRecursiveBinarySearchThatReturnsThree()
{
int[] arrayToSearch = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
int searchValue = 4;
int upperLimit = 9;
int lowerLimit = 0;
int expected = 2;
Searches mySearch = new Searches();
int actual = mySearch.RecursiveBinarySearch(arrayToSearch, searchValue, upperLimit, lowerLimit);

Assert.AreEqual(expected, actual);
}

[Test]
public void RunRecursiveBinarySearchThatReturnsNine()
{
int[] arrayToSearch = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
int searchValue = 11;
int upperLimit = 9;
int lowerLimit = 0;
int expected = 9;
Searches mySearch = new Searches();
int actual = mySearch.RecursiveBinarySearch(arrayToSearch, searchValue, upperLimit, lowerLimit);

Assert.AreEqual(expected, actual);
}

}
}
```

I wanted to take a step beyond just solving a problem and also look at how I might test some of these libraries I was creating. In this case I wanted to play around with some of the basic sorting algorithms and then utilize a custom harness to test it against a variety of different sized arrays.

The sorts that I implemented are the following:

I am not going to go into the good, the bad and the ugly about these since what I really wanted to do was to build a harness for them. First off I had to implement them.

Sorts:

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BasicSorts
{
public class Sorts
{
public int[] BubbleSortAsc(int[] arrayToSort)
{
int arrayLength = arrayToSort.Length;
int[] sortedArray = arrayToSort;
int temp;
for (int i = arrayLength; i > 0; i--)
{
for(int j = 0; j < i-1; j++)
{
if(sortedArray[j] > sortedArray[j+1])
{
temp = sortedArray[j];
sortedArray[j] = sortedArray[j+1];
sortedArray[j+1] = temp;
}
}

}

return sortedArray;
}

public int[] InsertionSortAsc(int[] arrayToSort)
{
int[] sortedArray = arrayToSort;
int arrayLength = sortedArray.Length;
int temp, inner;

for(int i = 0; i < arrayLength; i++)
{
temp = sortedArray[i];
inner = i;
while (inner > 0 && sortedArray[inner - 1] >= temp)
{
sortedArray[inner] = sortedArray[inner - 1];
inner -= 1;
}
sortedArray[inner] = temp;
}
return sortedArray;

}

public int[] SelectionSortAsc(int[] arrayToSort)
{
int[] sortedArray = arrayToSort;
int arrayLength = sortedArray.Length;
int temp, min;

for (int i = 0; i < arrayLength; i++)
{
min = i;
for (int j = i + 1; j < arrayLength; j++)
{
if (sortedArray[j] < sortedArray[min])
{
min = j;
}
}
temp = sortedArray[i];
sortedArray[i] = sortedArray[min];
sortedArray[min] = temp;
}

return sortedArray;
}
}
}

```

Once I was done and satisfied with the implementation I wanted to create a harness to test how long it took to perform the sort under different conditions. To do this I added a console project to my solution and added a reference to the Sort library. I ended up creating a method to randomly generate my integer arrays based on the size passed in. I adjusted the size of the array an looping through it twice more multiplying the starting size of the array by 10. This allowed me to generate larger data sets to run the sorts through and compare times.

I also utilized the Stopwatch class in .Net to capture times. This lives in the System.Diagnostics namespace. Another approach might have been to implement Perfmon counters to capture the method execution data but that seemed like overkill for this particular project.

I chose to break out the execution of the different sorts by how the data was set up (unsorted, presorted ascending, presorted descending) before being passed into the sorting methods. The way I have it setup allowed me to use the same base data setup for each sort method and each data order. The console output looked like:

Test Harness:

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using BasicSorts;

namespace SortsTimingHarness
{
class Program
{
static void Main(string[] args)
{
int arraySize = 100;
int counter = 0;

while (counter < 3)
{
Console.WriteLine("-----------------------------------------------------------------");
Console.WriteLine("The array size is {0}", arraySize);

int[] unsortedArray = CreateArray(arraySize);
int[] ascSortedArray = new int[arraySize];
Array.Copy(unsortedArray, ascSortedArray,arraySize);
Array.Sort(ascSortedArray);

int[] descSortedArray = new int[arraySize];
Array.Copy(unsortedArray, descSortedArray, arraySize);
Array.Sort(descSortedArray);
Array.Reverse(descSortedArray);

Console.WriteLine("Times when running an randomly set unsorted array");
RunUnSortedArrays(unsortedArray);
Console.WriteLine("Times when running an sort an an array that has already had an ascending sort applied.");
RunAscSortedArrays(ascSortedArray);
Console.WriteLine("Times when running an doing an ascending sort on an array already descending sorted.");
RunDescSortedArrays(descSortedArray);
Console.WriteLine();

counter++;
arraySize *= 10;
}

}

private static int[] CreateArray(int arraySize)
{
int[] array = new int[arraySize];
Random rand = new Random(7);
for (int i = 0; i < arraySize; i++)
array[i] = rand.Next();

return array;
}

private static void RunUnSortedArrays(int[] unSortedArray)
{
int arraySize = unSortedArray.Length;

int[] bubbleUnsorted = new int[arraySize];
int[] instertionUnsorted = new int[arraySize];
int[] selectionUnsorted = new int[arraySize];
Array.Copy(unSortedArray, bubbleUnsorted, arraySize);
Array.Copy(unSortedArray, instertionUnsorted, arraySize);
Array.Copy(unSortedArray, selectionUnsorted, arraySize);

Sorts sort = new Sorts();

Stopwatch timer = new Stopwatch();

timer.Start();
sort.BubbleSortAsc(bubbleUnsorted);
timer.Stop();
Console.WriteLine("The bubble sort took {0} ticks for a {1} element unsorted array.", timer.ElapsedTicks, arraySize);

timer.Reset();

timer.Start();
sort.InsertionSortAsc(instertionUnsorted);
timer.Stop();
Console.WriteLine("The insertion sort took {0} ticks for a {1} element unsorted array.", timer.ElapsedTicks, arraySize);

timer.Reset();

timer.Start();
sort.SelectionSortAsc(selectionUnsorted);
timer.Stop();
Console.WriteLine("The selection sort took {0} ticks for a {1} element unsorted array.", timer.ElapsedTicks, arraySize);
}

private static void RunAscSortedArrays(int[] ascSortedArray)
{
int arraySize = ascSortedArray.Length;

int[] bubbleAscSorted = new int[arraySize];
int[] instertionAscUnsorted = new int[arraySize];
int[] selectionAscUnsorted = new int[arraySize];
Array.Copy(ascSortedArray, bubbleAscSorted, arraySize);
Array.Copy(ascSortedArray, instertionAscUnsorted, arraySize);
Array.Copy(ascSortedArray, selectionAscUnsorted, arraySize);

Sorts sort = new Sorts();

Stopwatch timer = new Stopwatch();

timer.Start();
sort.BubbleSortAsc(bubbleAscSorted);
timer.Stop();
Console.WriteLine("The bubble sort took {0} ticks for a {1} element ascending sorted array.", timer.ElapsedTicks, arraySize);

timer.Reset();

timer.Start();
sort.InsertionSortAsc(instertionAscUnsorted);
timer.Stop();
Console.WriteLine("The insertion sort took {0} ticks for a {1} element ascending sorted array.", timer.ElapsedTicks, arraySize);

timer.Reset();

timer.Start();
sort.SelectionSortAsc(selectionAscUnsorted);
timer.Stop();
Console.WriteLine("The selection sort took {0} ticks for a {1} element ascending sorted array.", timer.ElapsedTicks, arraySize);
}

private static void RunDescSortedArrays(int[] descSortedArray)
{
int arraySize = descSortedArray.Length;

int[] bubbleDescSorted = new int[arraySize];
int[] instertionDescUnsorted = new int[arraySize];
int[] selectionDescUnsorted = new int[arraySize];
Array.Copy(descSortedArray, bubbleDescSorted, arraySize);
Array.Copy(descSortedArray, instertionDescUnsorted, arraySize);
Array.Copy(descSortedArray, selectionDescUnsorted, arraySize);

Sorts sort = new Sorts();

Stopwatch timer = new Stopwatch();

timer.Start();
sort.BubbleSortAsc(bubbleDescSorted);
timer.Stop();
Console.WriteLine("The bubble sort took {0} ticks for a {1} element descending sorted array.", timer.ElapsedTicks, arraySize);

timer.Reset();

timer.Start();
sort.InsertionSortAsc(instertionDescUnsorted);
timer.Stop();
Console.WriteLine("The insertion sort took {0} ticks for a {1} element descending sorted array.", timer.ElapsedTicks, arraySize);

timer.Reset();

timer.Start();
sort.SelectionSortAsc(selectionDescUnsorted);
timer.Stop();
Console.WriteLine("The selection sort took {0} ticks for a {1} element descending sorted array.", timer.ElapsedTicks, arraySize);
}

}
}

```

A couple interesting things to note was looking at how the size of the data set had a significant impact on the difference in the amount of time each of these sorts took.

It would be very easy to take this test harness an modify the output to write to a log or text file so the results could be more easily shared.

Sort Unit Tests:

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using BasicSorts;
using NUnit.Framework;

namespace BasicSortsTests
{
[TestFixture]
public class SortTests
{
[Test]
public void SortFiveElemntMixedArray_withBubbleSort()
{
int[] unsortedArray = {5,1,0,3,-1};
Sorts sort = new Sorts();
int[] expectedSortedArray = { -1, 0, 1, 3, 5 };
int[] actualSortedArray = sort.BubbleSortAsc(unsortedArray);
Assert.AreEqual(expectedSortedArray, actualSortedArray);

}

[Test]
public void SortFiveElemntSortedArray_withBubbleSort()
{
int[] unsortedArray = { 10, 20, 30, 40, 50 };
Sorts sort = new Sorts();
int[] expectedSortedArray = { 10, 20, 30, 40, 50 };
int[] actualSortedArray = sort.BubbleSortAsc(unsortedArray);
Assert.AreEqual(expectedSortedArray, actualSortedArray);

}

[Test]
public void SortFiveElemntSorted_DecendingArray_withBubbleSort()
{
int[] unsortedArray = { 9, 8, 7, 6, 5 };
Sorts sort = new Sorts();
int[] expectedSortedArray = { 5, 6, 7, 8, 9 };
int[] actualSortedArray = sort.BubbleSortAsc(unsortedArray);
Assert.AreEqual(expectedSortedArray, actualSortedArray);

}

[Test]
public void SortFiveElemntMixedArray_withInsertionSort()
{
int[] unsortedArray = { 5, 1, 0, 3, -1 };
Sorts sort = new Sorts();
int[] expectedSortedArray = { -1, 0, 1, 3, 5 };
int[] actualSortedArray = sort.InsertionSortAsc(unsortedArray);
Assert.AreEqual(expectedSortedArray, actualSortedArray);

}

[Test]
public void SortFiveElemntSortedArray_withInsertionSort()
{
int[] unsortedArray = { 10, 20, 30, 40, 50 };
Sorts sort = new Sorts();
int[] expectedSortedArray = { 10, 20, 30, 40, 50 };
int[] actualSortedArray = sort.InsertionSortAsc(unsortedArray);
Assert.AreEqual(expectedSortedArray, actualSortedArray);

}

[Test]
public void SortFiveElemntSorted_DecendingArray_withInsertionSort()
{
int[] unsortedArray = { 9, 8, 7, 6, 5 };
Sorts sort = new Sorts();
int[] expectedSortedArray = { 5, 6, 7, 8, 9 };
int[] actualSortedArray = sort.InsertionSortAsc(unsortedArray);
Assert.AreEqual(expectedSortedArray, actualSortedArray);

}

[Test]
public void SortFiveElemntMixedArray_withSelectionSort()
{
int[] unsortedArray = { 5, 1, 0, 3, -1 };
Sorts sort = new Sorts();
int[] expectedSortedArray = { -1, 0, 1, 3, 5 };
int[] actualSortedArray = sort.SelectionSortAsc(unsortedArray);
Assert.AreEqual(expectedSortedArray, actualSortedArray);

}

[Test]
public void SortFiveElemntSortedArray_withSelectionSort()
{
int[] unsortedArray = { 10, 20, 30, 40, 50 };
Sorts sort = new Sorts();
int[] expectedSortedArray = { 10, 20, 30, 40, 50 };
int[] actualSortedArray = sort.SelectionSortAsc(unsortedArray);
Assert.AreEqual(expectedSortedArray, actualSortedArray);

}

[Test]
public void SortFiveElemntSorted_DecendingArray_withSelectionSort()
{
int[] unsortedArray = { 9, 8, 7, 6, 5 };
Sorts sort = new Sorts();
int[] expectedSortedArray = { 5, 6, 7, 8, 9 };
int[] actualSortedArray = sort.SelectionSortAsc(unsortedArray);
Assert.AreEqual(expectedSortedArray, actualSortedArray);

}
}
}

```

This was another one suggested to my by a friend. Take an int and convert it to the corresponding roman numeral string. For grins and giggles I limited the valid inputs to integers between 1 and 3999. This way I did not have to figure out how to add the overline and underline for larger numbers. I am not sure this is as tight as it might be but I did get the numeral assignment down to a single method after a few false starts.

Solution:

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RomanNumerals
{
public enum Numerals
{
I = 1,
V = 5,
X = 10,
L = 50,
C = 100,
D = 500,
M = 1000
}

public class IntToRomanNumerals
{
public string ConvertIntToRomanNumerals(int number)
{
int[] digits = new int[4];
StringBuilder romanNumeralParts = new StringBuilder();

if (number <= 0 || number >= 4000)
throw new ArgumentException("Accepted values are between 1 and 3999");

GetDigits(number, digits);

for (int i = 0; i < digits.Length; i++)
{
if(digits[i] != 0)
GetNumbers(digits[i], i, romanNumeralParts);
}

return romanNumeralParts.ToString();
}

private void GetNumbers(int digit, int i, StringBuilder romanNumeralParts)
{
if (i == 0)
GetThousands(digit, romanNumeralParts);
else if (i == 1)
GetNumeral(digit, 100, romanNumeralParts);
else if (i == 2)
GetNumeral(digit, 10, romanNumeralParts);
else
GetNumeral(digit, 1, romanNumeralParts);
}

private void GetThousands(int digit, StringBuilder romanNumeralParts)
{
for (int i = 1; i <= digit; i++)
{
romanNumeralParts.Append(Enum.GetName(typeof(Numerals), 1000));
}
}

private void GetNumeral(int digit, int multiplier, StringBuilder romanNumeralParts)
{
string startsWithOnes = Enum.GetName(typeof(Numerals), 1 * multiplier);
string startsWithFives = Enum.GetName(typeof(Numerals), 5 * multiplier);

if (digit < 4)
{
for (int i = 1; i <= digit; i++)
{
romanNumeralParts.Append(startsWithOnes);
}
}
else if(digit == 4)
romanNumeralParts.Append(startsWithOnes+startsWithFives);
else if(digit > 4 && digit < 9)
{
romanNumeralParts.Append(startsWithFives);
if (digit > 5)
{
for (int i = digit; digit < 9; i++)
{
romanNumeralParts.Append(startsWithOnes);
}
}
}
else
romanNumeralParts.Append(startsWithOnes + Enum.GetName(typeof(Numerals), 10 * multiplier));
}

private void GetDigits(int number, int[] digits)
{
int remainder;
int numToDivide = number;
int divisor = 1000;

for (int i = 0; i < digits.Length; i++)
{
digits[i] = Math.DivRem(numToDivide, divisor, out remainder);
numToDivide = remainder;

divisor /= 10;
}

}
}
}
```

Tests

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using NUnit.Framework;
using RomanNumerals;

namespace RomanNumeralTests
{
[TestFixture]
public class IntToRomanNumeralsTests
{
[Test]
public void CheckExceptionOnZeroValue()
{
int testValue = 0;
IntToRomanNumerals rm = new IntToRomanNumerals();

var ex = Assert.Catch<ArgumentException>(() =>
rm.ConvertIntToRomanNumerals(testValue));

StringAssert.Contains("Accepted values are between 1 and 3999",ex.Message);
}

[Test]
public void CheckExceptionOnUpplerValue()
{
int testValue = 5000;
IntToRomanNumerals rm = new IntToRomanNumerals();

var ex = Assert.Catch<ArgumentException>(() =>
rm.ConvertIntToRomanNumerals(testValue));

StringAssert.Contains("Accepted values are between 1 and 3999", ex.Message);
}

[Test]
public void CheckExceptionOnNegativeValue()
{
int testValue = -1;
IntToRomanNumerals rm = new IntToRomanNumerals();

var ex = Assert.Catch<ArgumentException>(() =>
rm.ConvertIntToRomanNumerals(testValue));

StringAssert.Contains("Accepted values are between 1 and 3999", ex.Message);
}

[Test]
public void Return_I_forOne()
{
int testValue = 1;
IntToRomanNumerals rm = new IntToRomanNumerals();
string expected = "I";
string actual = rm.ConvertIntToRomanNumerals(testValue);
Assert.AreEqual(expected, actual);

}

[Test]
public void Return_III_forThree()
{
int testValue = 3;
IntToRomanNumerals rm = new IntToRomanNumerals();
string expected = "III";
string actual = rm.ConvertIntToRomanNumerals(testValue);
Assert.AreEqual(expected, actual);

}

[Test]
public void Return_IX_forNine()
{
int testValue = 9;
IntToRomanNumerals rm = new IntToRomanNumerals();
string expected = "IX";
string actual = rm.ConvertIntToRomanNumerals(testValue);
Assert.AreEqual(expected, actual);

}

[Test]
public void Return_MMXIV_for2014()
{
int testValue = 2014;
IntToRomanNumerals rm = new IntToRomanNumerals();
string expected = "MMXIV";
string actual = rm.ConvertIntToRomanNumerals(testValue);
Assert.AreEqual(expected, actual);

}

[Test]
public void Return_CMXCIX_for999()
{
int testValue = 999;
IntToRomanNumerals rm = new IntToRomanNumerals();
string expected = "CMXCIX";
string actual = rm.ConvertIntToRomanNumerals(testValue);
Assert.AreEqual(expected, actual);

}

}
}
```

One of my developer friends suggested this one. Without using a built in .net function if it exists remove any duplicate characters from a string. I actually came up with two approaches. I will have to see if I followed the spirit of the rule about built in functions or not. :)

Solution 1: Using Split
The first solutions was to utilized the .Split function (not sure is this was cheating based on his rules but I went with it….) on a string to remove a given character. I tracked what character was used and built a new string from that. I utilized a recursive method to work my way through the remaining strings until there were no characters left. This allowed me to build a new string that retained the order I found the characters in. The interesting thing would have been to sit down and define a little more if he cared what order things came back in.

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RemoveDuplicates
{
public class RemoveDuplicatesFromString
{
public string RemoveDuplicateCharsFromString(string needsScrubbing)
{
string scrubbedString = null;

if (string.IsNullOrEmpty(needsScrubbing))
throw new ArgumentException("The string value passed cannot be null or empty.");
else if (needsScrubbing.Length == 1)
scrubbedString = needsScrubbing;
else
{
StringBuilder scrubbedChars = new StringBuilder();
CharcterDuplicaitonRemoval(needsScrubbing, scrubbedChars);

scrubbedString = scrubbedChars.ToString();
}

return scrubbedString;

}

private void CharcterDuplicaitonRemoval(string needsScrubbing, StringBuilder scrubbedChars)
{
if (needsScrubbing.Length > 1)
{
char charToSplitOn = Convert.ToChar(needsScrubbing[0]);
string[] remainingStrings = needsScrubbing.Split(charToSplitOn);
scrubbedChars.Append(charToSplitOn);
CharcterDuplicaitonRemoval(string.Join("", remainingStrings), scrubbedChars);
}
else if (needsScrubbing.Length == 1)
{
scrubbedChars.Append(needsScrubbing);
}
}
}
}
```

Solution 2 With a loop:
The second solution uses a loop of the char array that was created by the string. This also checks the StringBuilder object to see if a given char has already been used. One time through the loop and we are done.

```    public class RemoveDuplicatesFromString
{
public string RemoveDuplicateCharsFromString(string needsScrubbing)
{
string scrubbedString = null;

if (string.IsNullOrEmpty(needsScrubbing))
throw new ArgumentException("The string value passed cannot be null or empty.");
else if (needsScrubbing.Length == 1)
scrubbedString = needsScrubbing;
else
{
StringBuilder scrubbedChars = new StringBuilder();
CharcterDuplicaitonRemoval(needsScrubbing, scrubbedChars);
scrubbedString = scrubbedChars.ToString();
}

return scrubbedString;
}

private void CharcterDuplicaitonRemoval(string needsScrubbing, StringBuilder scrubbedChars)
{
char[] partsOfTheString = needsScrubbing.ToCharArray();

for (int i = 0; i < partsOfTheString.Length; i++)
{
if (!scrubbedChars.ToString().Contains(partsOfTheString[i]))
scrubbedChars.Append(partsOfTheString[i]);

}
}
}
```

Solution Tests:

Both solutions utilized and passed the same tests.

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using NUnit.Framework;
using RemoveDuplicates;

namespace RemoveDuplicateTests
{
[TestFixture]
public class RemoveDuplicatesFromStringTests
{
[Test]
public void CheckForNullValue()
{
RemoveDuplicatesFromString rmDup = new RemoveDuplicatesFromString();

var ex = Assert.Catch<ArgumentException>(() =>
rmDup.RemoveDuplicateCharsFromString(null));
Assert.That(ex.Message, Is.StringContaining("The string value passed cannot be null or empty."));
}

[Test]
public void Check_For_Empty_String()
{
RemoveDuplicatesFromString rmDup = new RemoveDuplicatesFromString();

var ex = Assert.Catch<ArgumentException>(() =>
rmDup.RemoveDuplicateCharsFromString(null));
Assert.That(ex.Message, Is.StringContaining("The string value passed cannot be null or empty."));

}

[Test]
public void Check_For_Single_Char_String()
{
RemoveDuplicatesFromString rmDup = new RemoveDuplicatesFromString();
string testString = "a";
string expected = "a";
string actual = rmDup.RemoveDuplicateCharsFromString(testString);

Assert.AreEqual(expected, actual);

}

[Test]
public void Check_For_Two_Char_String_with_Same_Chars()
{
RemoveDuplicatesFromString rmDup = new RemoveDuplicatesFromString();
string testString = "aa";
string expected = "a";
string actual = rmDup.RemoveDuplicateCharsFromString(testString);

Assert.AreEqual(expected, actual);

}

[Test]
public void Check_For_Two_Char_String_with_Different_Chars()
{
RemoveDuplicatesFromString rmDup = new RemoveDuplicatesFromString();
string testString = "ab";
string expected = "ab";
string actual = rmDup.RemoveDuplicateCharsFromString(testString);

Assert.AreEqual(expected, actual);

}

[Test]
public void Check_For_MultiString_Char_String_with_Two_Different_Chars()
{
RemoveDuplicatesFromString rmDup = new RemoveDuplicatesFromString();
string testString = "ababababab";
string expected = "ab";
string actual = rmDup.RemoveDuplicateCharsFromString(testString);

Assert.AreEqual(expected, actual);

}

[Test]
public void Check_For_MultiString_Char_String_with_Upper_and_Lower_Case_Chars()
{
RemoveDuplicatesFromString rmDup = new RemoveDuplicatesFromString();
string testString = "abABAbaABb";
string expected = "abAB";
string actual = rmDup.RemoveDuplicateCharsFromString(testString);

Assert.AreEqual(expected, actual);

}

[Test]
public void Check_For_MultiString_Char_String_with_Spaces_Case_Chars()
{
RemoveDuplicatesFromString rmDup = new RemoveDuplicatesFromString();
string testString = "With a space";
string expected = "With aspce";
string actual = rmDup.RemoveDuplicateCharsFromString(testString);

Assert.AreEqual(expected, actual);

}
}
}
```

After wading into a WCF configuration mess (that I am still trying to master) this is a very simple problem that I did to get my self warmed up this morning.

How do you reverse a string not using a number of the built in .Net Functions. It is very easy to do this with .Net functions. You could do it as a simple 1 liner by combining functions like this:

```string reversed = new string(needsReversing.ToCharArray().Reverse().ToArray());
```

Nice and slick but not exactly forcing me to think too hard.

Instead I went with the following with a small loop following checks for null values and empty strings.

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace StringReversing
{
public class StringReverse
{
public string ReverseAString(string needsReversing)
{
string reversedString = string.Empty;

if (string.IsNullOrEmpty(needsReversing))
throw new ArgumentException("A null or empty value is not valid.");
else if (needsReversing.Length == 1)
reversedString = needsReversing;
else
{
char[] fromString = needsReversing.ToCharArray();

char[] temp = new char[fromString.Length];

int counter = fromString.Length;
for(int i = 0; i < fromString.Length; i++)
{
temp[counter - 1] = fromString[i];
counter--;
}

reversedString = new string(temp);
}

return reversedString;
}
}
}
```

The tests:

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using NUnit.Framework;
using StringReversing;

namespace StringReverseTests
{
public class StringReverseTests
{
[Test]
public void ReverseASingleCharacterString()
{
string toReverse = "a";
string expected = "a";
StringReverse sut = new StringReverse();

string actual = sut.ReverseAString(toReverse);

Assert.AreEqual(expected, actual);

}

[Test]
public void ReverstANullValueString()
{
string message = "A null or empty value is not valid";
StringReverse sut = new StringReverse();

var ex = Assert.Catch<ArgumentException>(() =>
sut.ReverseAString(null));

Assert.That(ex.Message, Is.StringContaining(message));

}

[Test]
public void ReverstAEmptyString_Returns_Exception()
{
string message = "A null or empty value is not valid";
StringReverse sut = new StringReverse();

var ex = Assert.Catch<ArgumentException>(() =>
sut.ReverseAString(string.Empty));

Assert.That(ex.Message, Is.StringContaining(message));

}

[Test]
public void Reverse_A_Two_Character_NonMatching_String()
{
string toReverse = "ab";
string expected = "ba";
StringReverse sut = new StringReverse();

string actual = sut.ReverseAString(toReverse);

Assert.AreEqual(expected, actual);

}

[Test]
public void Reverse_A_Long_String_with_Character_NonMatching_String()
{
string toReverse = "this is a long string to reverse";
string expected = "esrever ot gnirts gnol a si siht";
StringReverse sut = new StringReverse();

string actual = sut.ReverseAString(toReverse);

Assert.AreEqual(expected, actual);

}
}
}

```

One of the things that I have found in the coding that I have done for different test harness and tools that I have done up to know is that there really has never been much of a need (or at least one that I recognized) to utilize an abstract class or interface. While I built classes the were mostly independent objects. I did not have a need to build a base class to be inherited in my applications. This meant I have not spent much time learning about them and getting a feel for the differences. So lets define them to start with.

Base Class - This is a class that encapsulates a common set of properties and methods that would be used be the various derived classes. Technically in C# at least you can inherit from any class that has not been sealed. That may or may not be a good idea depending on what all you have to do. One of the nice things about setting up a base class is that when you inherit from it you get everything in the base class in your new derived class. Here is an example I put together.

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Report
{
public class Report
{

public string ReportHeader { get; private set ; }

public string ReportBody { get; private set; }

public string ReportFooter { get; private set; }

public StringBuilder CombinedReport { get; private set; }

{
}

public void SetBody(string body)
{
this.ReportBody = body;
}

public void SetFooter(string footer)
{
this.ReportFooter = footer;
}

public void CompileReport()
{
this.CombinedReport = new StringBuilder();
CombinedReport.AppendLine();
CombinedReport.AppendLine(ReportBody);
CombinedReport.AppendLine();
CombinedReport.AppendLine(ReportFooter);

}
}

public class CustomReport : Report //inherits from Report
{
public string TPSCoverSheet { get; private set; }

public void SetCoverSheet(string coverSheet)
{
this.TPSCoverSheet = coverSheet;
}

public void CreateReportWithCoverSheet()
{
StringBuilder coverSheet = new StringBuilder();
coverSheet.AppendLine(TPSCoverSheet);
CompileReport();
CombinedReport.Insert(0, coverSheet);
}

}

}
```

In this example Report is the base class and Custom report inherits from this. This is probably the most basic implementation. You can see in the CreateReportWithCoverSheet() method I make a call into the base class to build the report and then I modify an property (CombinedReport) from the base class as well. Working from in my base class I have access to all of the properties and methods in the base class from any derived class.

Looking at some of the tests we can get a feel for how this might work:

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using NUnit.Framework;
using Report;

namespace ReportTests
{
[TestFixture]
public class ReportTests
{
[Test]
{
CustomReport cr = new CustomReport();

}

[Test]
public void ChildClassSetFooter()
{
CustomReport cr = new CustomReport();
string footer = "This is my footer";
cr.SetFooter(footer);
Assert.AreEqual(footer, cr.ReportFooter);

}

[Test]
public void ChildClassSetBody()
{
CustomReport cr = new CustomReport();
string body = "This is my body";
cr.SetBody(body);
Assert.AreEqual(body, cr.ReportBody);

}

[Test]
public void ChildClassSetCoverSheet()
{
CustomReport cr = new CustomReport();
string coverSheet = "This is my coversheet";
cr.SetCoverSheet(coverSheet);
Assert.AreEqual(coverSheet, cr.TPSCoverSheet);

}

[Test]
{
CustomReport cr = new CustomReport();
string coverSheet = "This is my coversheet";
string footer = "This is my footer";
string body = "This is my body";
cr.SetFooter(footer);
cr.SetBody(body);
cr.SetCoverSheet(coverSheet);
cr.CreateReportWithCoverSheet();

StringAssert.Contains(coverSheet,cr.CombinedReport.ToString());

}

[Test]
public void ChildClassReportCreate_CheckCoverSheet()
{
CustomReport cr = new CustomReport();
string coverSheet = "This is my coversheet";
string footer = "This is my footer";
string body = "This is my body";
cr.SetFooter(footer);
cr.SetBody(body);
cr.SetCoverSheet(coverSheet);
cr.CreateReportWithCoverSheet();

StringAssert.Contains(coverSheet, cr.CombinedReport.ToString());

}

}
}
```

There are a number of other variations when you starting working with different keywords (abstract, virtual, sealed, etc.) that change some of the definition of what can be inherited by other classes and what methods can be overridden, but I am not going to touch that at the moment.

Interfaces - This is another way of approaching this issue. As noted in the below article and others, the interface allows for multiple inheritance. In C# a derived class can only inherit from one class but multiple interfaces.

Take a look at the following articles that explain in much more detail:

http://dotnet.dzone.com/articles/c-interfaces-what-are-they-and

The interface defines what the structure of a class is but not the details of the implementation. Here is an example of what the Report class from above might look like as an interface instead:

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Report
{
public interface IReport
{
string ReportHeader { get; set; }
string ReportBody { get; set; }
string ReportFooter { get; set; }
StringBuilder CombinedReport { get; set; }

void CompileReport();
}
}
```

Next I implemented two classes using the interface. One is a basic report that would match the base class I used, and the second was the custom report with coversheet. You will notice that because the CustomReport class is derived directly from the interface I had to implement all of the same properties as the simple report class I created. The advantage was I was able to implement the CompileReport() method in such a way as to account for the header I wanted to add. Now I could have gone ahead an inherited from the simple report class but I didn’t really want to do that in this case.

```    public class ReportFromInterface : IReport
{

public string ReportHeader { get; set; }
public string ReportBody { get; set; }
public string ReportFooter { get; set; }
public StringBuilder CombinedReport { get; set; }

string body, string footer)
{
this.ReportBody = body;
this.ReportFooter = body;
}

public void CompileReport()
{
this.CombinedReport = new StringBuilder();
CombinedReport.AppendLine();
CombinedReport.AppendLine(ReportBody);
CombinedReport.AppendLine();
CombinedReport.AppendLine(ReportFooter);
}

}

public class CustomReportFromInterface : IReport
{
public string TPSCoverSheet{ get; set; }
public string ReportHeader { get; set; }
public string ReportBody { get; set; }
public string ReportFooter { get; set; }
public StringBuilder CombinedReport { get; set; }

public CustomReportFromInterface(string coverSheet,
string header, string body, string footer)
{
this.TPSCoverSheet = coverSheet;
this.ReportBody = body;
this.ReportFooter = body;
}

public void CompileReport()
{
this.CombinedReport = new StringBuilder();
CombinedReport.AppendLine(TPSCoverSheet);
CombinedReport.AppendLine();
CombinedReport.AppendLine();
CombinedReport.AppendLine(ReportBody);
CombinedReport.AppendLine();
CombinedReport.AppendLine(ReportFooter);
}

}
```

And the tests that implement each class (just as an example).

```    [TestFixture]
public class InterfaceReportTests
{
[Test]
public void BasicReportSimpleTest()
{
string footer = "This is my footer";
string body = "This is my body";

sr.CompileReport();

}

[Test]
public void CustomReportSimpleTest()
{
string coverSheet = "This is my TPS Report Cover Sheet.";
string footer = "This is my footer";
string body = "This is my body";

CustomReportFromInterface cr = new CustomReportFromInterface(coverSheet,