Algorithms in C#

This is part 3 of Algorithms questions in Interviews.(Part 1 | Part 2 )

In this post we will write an algorithm that finds an element in an array of infinite size.
How to find an element position from an array?

Below function takes an infinite size array and a key to be searched and returns first index position if found else -1. Here, we don’t know size of array and we can assume size to be infinite in this function.

Please note I am assuming the array is a sorted array. For (Quicksort) sorting the array you can refer to part 2 of this blog series.

First Occurence of element

private int FirstOccurrenceBinarySearch(int arr[], int low, int high, int data)
{
	int mid; 
	// A simple implementation of Binary Search
	if(high >= low)
	{
		mid = low + (high - low)/2; // To avoid overflow
		if((mid == low && arr[mid] == data) || (arr[mid] == data && arr[mid-1] < data)) 		{ 			return mid; 		} 		 		else if(arr[mid] >= data)
		{
			// We need to give preference to left part of the array
			// since we are concerned with the first occurrence
			return FirstOccurrenceBinarySearch(arr, low, mid-1, data);
		}
		else // We need to search in the right half
		{			
			return FirstOccurrenceBinarySearch(arr, mid+1, high, data);
		}
	}	
	return -1;
}

Last Occurence of element

		
private int LastOccurrenceBinarySearch(int[] array, int low, int high, int data)
{
	int mid;
	// A simple implementation of Binary Search
	if (high >= low)
	{
		mid = low + (high - low) / 2; // To avoid overflow
		if ((mid == high && array[mid] == data) || (array[mid] == data && array[mid + 1] > data))
			return mid;

		// We need to give preference to right part of the array
		// since we are concerned with the last occurrence
		else if (array[mid] <= data)
			return LastOccurrenceBinarySearch(array, mid + 1, high, data);
		else
			// We need to search in the left half
			return LastOccurrenceBinarySearch(array, low, mid - 1, data);
	}
	return -1;
}
Advertisements

Algorithms in C#

This is part 2 of Algorithms questions in Interviews.(Part 1| Part 3)
quick_sort

Quicksort Algorithm

public void QuickSort(int[] array, int left, int right)
{
	int i = left;
	int j = right;
	int pivot = array[(left + right) / 2];
	while (true)
	{
		while (array[i] < pivot)
			i++;
		while (pivot < array[j])
			j--;
		if (i <= j)
		{
			Swap(array, i, j);
			i++;
			j--;
		}
		if (i > j) 
			break;
		if (left < j)
			QuickSort(array, left, j);
		if (i < right)
			QuickSort(array, i, right);
	}
}

private void Swap(int[] array, int a, int b)
{
	var temp = array[a];
	array[a] = array[b];
	array[b] = temp;
}

That code is actually a fairly clear implementation of quicksort.
The key to understanding this particular program is that every recursive function call receives the same full string. So the function has to set its own boundaries, i.e., “left” and “right” and ignore the remainder of the string. Every recursive function call only deals with partitioning a small part of the string.

The original function call partitions the string into portions less than the pivot (lower portion) and greater than the pivot (upper portion), leaving any string values equal to the pivot in a “no man’s land” somewhere in between the left and right portions.

As soon as it gets to the recursive function calls, it gets a bit more murky, and it is important to understand that these lower and upper portions are different from the “left” and “right” variables. The “left” variable is the original position of the left boundary of the entire string that the function call is supposed to operate on, and similarly for the “right” variable.

The key to the algorithm is understanding that the first function call leaves nothing necessarily sorted in the upper or lower portions. However, it removes one or more partition values from consideration and ensures that they are above all lower string values, and below all upper string values, i.e., in the “middle” of the string.

This process is repeated recursively on both of the unsorted upper and lower portions of the string until eventually reaching an upper or lower portion size of two or fewer values, which must be sorted already as a result of being partitioned.

The quicksort algorithm has a worst case performance of O(N^2) if the pivot value is always an extreme value, and a best case performance of O(N log N) if the pivot value is close to the middle of the string. For instance, when sorting 31 characters and assuming a perfect median choice of pivot,

first stage:

lower 15, pivot, upper 15

second stage:

(lower 7, pivot, upper 7), pivot, (lower 7, pivot, upper 7)

third stage:

((lower 3, pivot, upper 3), pivot, (lower 3, pivot, upper 3)), pivot, ((lower 3, pivot, upper 3), pivot, (lower 3, pivot, upper 3))

fourth stage:

(((lower 1, pivot, upper 1), pivot, (lower 1, pivot, upper 1)), pivot, ((lower 1, pivot, upper 1), pivot, (lower 1, pivot, upper 1))), pivot, (((lower 1, pivot, upper 1), pivot, (lower 1, pivot, upper 1)), pivot, ((lower 1, pivot, upper 1), pivot, (lower 1, pivot, upper 1)))

Four stages is less than or equal to the base-two logarithm of 31, and at every stage the algorithm is linear (although performed in multiple distinct recursive function calls at each level), so 31 steps are performed, i.e., N steps.

So the total order of the algorithm is 4 stages times 31, or approximately N times log N.

In reality, sometimes a pivot is not the median, and may even be an extreme value, in which case the “lower” or “upper” portions are empty. The algorithm might remove only one value from consideration at each stage, resulting in a total of N-1 stages to complete the algorithm. At every stage, there would be N steps of work, so the total order would be N times (N-1), which is O(N^2) since there is a product of N with N.

All in all, quicksort is a very good algorithm, and very hard to improve, as long as one’s algorithm avoids deliberate pernicious cases which could otherwise be exploited to feed a known codebase with input which produces a pivot sequence of extreme values.

Algorithms in C#

After spending 9 years in IT finally I am being asked to show my skills on Algorithms. On my first interview I could solve 90% not completely. Then I thought to revive something which I had been doing throughout my career.

In this series I will be posting some commonly asked Algorithms in Interviews. Part 2 | Part 3

How to find second highest number from an array?

public int FindSecondHighest(int[] array)
{
	int first = 0;
	int second = 0;
	foreach(var item in array)
	{
		if(item > first)
		{
			second = first;
			first = item;
		}
		else if(item > second)
		{
			second = item;
		}
	}
	return second;
}

How to find second lowest number from an array?

public int FindSecondLowest(int[] array)
{
	var firstlowest = Int32.MaxValue;
	var secondLowest = Int32.MaxValue;

	if (array.Length > 2)
	{
		for (int i = 0; i < array.Length; i++)
		{
			if (array[i] < firstlowest)
			{
				secondLowest = firstlowest;
				firstlowest = array[i];
			}
			else if (array[i] < secondLowest && array[i] > firstlowest)
				secondLowest = array[i];
		}
	}
	return secondLowest;
}