Computer science resources

Computer science resources

• Book: Cracking the coding interview
• https://sites.google.com/site/steveyegge2/five-essential-phone-screen-questions
• Book: Head First - design patterns
• people.cs.clemson.edu/~bcdean/dp_practice/
• http://www.usaco.org/
• http://courses.csail.mit.edu/iap/interview/materials.php
• https://github.com/prakhar1989/awesome-courses
• https://www.quora.com/How-much-time-did-you-spend-preparing-for-Googles-interviews
• http://www.quora.com/What-are-5-essential-skills-every-Web-Developer-should-have
• http://qr.ae/69WtZ
• http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=findSolution
• https://github.com/andreis/interview#articles
• http://prismoskills.appspot.com
• http://www.quora.com/What-are-the-good-resources-to-learn-about-distributed-scalable-robust-software-architecture-infrastructure-building
• https://www.quora.com/What-should-I-learn-to-become-a-very-good-developer-How-and-from-where

Architecture:

http://qr.ae/QcxsuFrontend:

http://qr.ae/BCOyF

Bucket sort in C#

Bucket sort - overview

Bucket sort is a good example of a distribution sort algorithm. It is closely related to Radix sort and counting sort.

Description of the bucket sort algorithm

Bucket sort is a sorting algorithm that distributes all values in an array into a number of so called buckets. Then each bucket is sorted by a different algorithm or by applying the same algorithm recursively. Finally the separate buckets are concatenated to get the final sorted array.

The algorithm works like this:

1. Initialize a list of empty buckets.
2. Loop through the input array and put each object in a corresponding bucket. This step is called "scattering".
3. Sort all buckets
4. Go through the sorted buckets in order and put the elements back into the original array. This step is called "gathering".

Computational complexity

Bucket sort has has a worst case performance of O(n²). In average it runs in O(n + k) time.

Example of an implementation of bucket sort in C#

    private void SortArrayWithBucketSort()
    {
        double[] array = { 0.37, 0.25, 0.86, 0.23, 0.09, 0.21, 0.17, 0.71 };
        double[] sortedArray = BucketSort(array);

        // PrintResult(sortedArray);
    }

    public double[] BucketSort(double[] array)
    {
        List<List<double>> buckets = new List<List<double>>();
        InitializeBuckets(buckets);

        Scatter(array, buckets);

        int i = 0;
        foreach (List<double> bucket in buckets)
        {
            double[] arr = bucket.ToArray();
            InsertionSort(arr);

            foreach (double d in arr)
            {
                array[i++] = d;
            }
        }

        return array;
    }

    private void Scatter(double[] array, List<List<double>> buckets)
    {
        foreach (double value in array)
        {
            int bucketNumber = GetBucketNumber(value);
            buckets[bucketNumber].Add(value);
        }
    }

    private void InsertionSort(double[] array)
    {
        int j;
        double temp;

        for (int i = 1; i < array.Length; i++)
        {
            j = i;
            while (j > 0 && array[j] < array[j - 1])
            {
                temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
                j--;
            }
        }
    }

    private int GetBucketNumber(double value)
    {
        double val = value * 10;
        int bucketNumber = (int)Math.Floor(val);
        return bucketNumber;
    }

    private static void InitializeBuckets(List<List<double>> buckets)
    {
        for (int i = 0; i < 10; i++)
        {
            List<double> a  = new List<double>();
            buckets.Add(a);
        }
    }

Counting sort in C#

Counting sort - overview

Counting sort (or histogram sort) is a linear integer sorting algorithm. It counts the number of elements that have the same value in the input array, puts the number of items in a a auxilliary counting array and then uses arithmetic to get the position of each value in the output array. The algorithm was invented by Harold H. Seward in 1954.

Counting sort does not use any comparisons, so it is not a comparison sort. Instead, it uses the values of the elements in the input array as indexes in an array used for counting.

A useful property of counting sort is that it is stable. This property is important when there is satellite data belonging to the elements being sorted.

The stability property is useful for another reason. In radix sort the counting sort algorithm is often used as a subroutine. In order to get Radix sort to work it is required that counting sort is stable. 

Description of the counting sort algorithm

Lets assume that we have an input array containing n values in the range [0..k]. Counting sort first creates an auxilliary counting array (with  k+1 elements) to hold frequencies of the elements in the input array. It then loops through all values in the input array and for each value, it uses that value as index in the counting array and increments that value by 1. For example if the value in the input array is 17, then it would execute countingArray[17]++ for each value.

After this first loop the counting array now holds the frequencies for all values in the input array.

In the next step the counting array is recalculated so that at position i, the value holds information about how many input elements that are less than or equal to the element i. In other words, the element at index=i holds the index position j of where the value i should be put in the output array. If using a zero indexed array we take the number j and decrease by 1, and then we get the final position.

Next an array for the output is created. The input array is then looped through, and for each value v it retrieves the position of where v should be placed in the output array. The value is retrieved from the recalculated counting array. Then it decreases the value in the counting array by 1.

Computational complexity

Counting sort has has a complexity of  O(n + k), where n is the size of the sorted array and k is the size of the helper array.

Example of an implementation of counting sort in C#

    private void SortArrayWithCountingSort()
    {
        int[] arrayToSort = { 2, 6, 6, 10, 10, 3 };
        int[] sorted = CountingSort(arrayToSort);

        // PrintResult(sorted);
    }

    private int[] CountingSort(int[] array)
    {
        int[] count = new int[11];

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

        for (int i = 1; i < count.Length; i++)
        {
            count[i] = count[i] + count[i - 1];
        }

        int[] sorted = new int[array.Length];

        for (int i = array.Length - 1; i >= 0; i--)
        {
            int value = array[i];
            int position = count[value] - 1;
            sorted[position] = value;

            count[value]--;
        }

        return sorted;
    }

Heapsort in C#

Heapsort - overview

Heapsort is a comparison based and in-place sorting algorithm. It was invented by John Williams in 1964.

What is a heap?

A heap is a tree-based data structure that must satisfy two properties to be a valid heap. First it must be a complete binary tree and secondly it must satisfy the heap property.

• In a complete binary tree each node has exactly two children. So a heap is entirely filled except for the lowest level. In the lowest level the leaves must be filled from left to right.
• The heap-order property says that: "Every node in the heap is <= to its children" (This is valid for min-heaps. For max-heaps we simply change "<=" against ">=").

A heap can be represented in an array. See the following illustration:

An example of a min-heap structure and its corresponding representation in array form. Note
 that this heap consists of a binary tree that is complete and that each node is <= its children.

Since a heap has the property of completeness, we know that there are no "holes" in the array. At each position in the array from 0 to n-1 we will have a valid value.

To find the index of the first child of a node with index i, we just need to use the formula 2i  + 1. The second child index is found at 2i  + 2. On the other hand, if we want to get the index of the parent, we would instead use floor((i - 1) / 2). Since integer division always results in an integer we can simply use (i-1) / 2.

Description of the heapsort algorithm

Heapsort consists of two parts. First a heap structure is constructed from the input data. For a min-heap the root value now is the smallest value in the heap, and for a max-heap it would be the largest.

In the second step the root value is removed from the heap by swapping the first with the last value. The root value is inserted into the right part of the array and is now considered sorted. Now the heap is one element smaller than before.

Next the algorithm will adjust the heap to restore the heap property and then remove the next smallest value and insert into the right sorted part of the array, by swapping first and last vaues. Then it will again adjust the heap and remove the next smallest value and so on. This will go on until all values in the heap has been moved to the right part. At that point the values in the array are sorted.

Computational complexity

Worst, best and average case performance are all O(n log n).

Example of an implementation of heapsort in C#

    private void SortArrayWithHeapSort()
    {
        int[] array = { 7, 5, 23, 2, 0, 2, 2 };
        BuildHeap(array);

        for (int i = array.Length - 1; i > 0; i--)
        {
            SwapValues(array, 0, i);

            int size = i;
            Heapify(array, size, 0);
        }

        // PrintResult(array);
    }

    private void BuildHeap(int[] a)
    {
        int size = a.Length;

        for (int i = size / 2; i >= 0; i--)
        {
            Heapify(a, size, i);
        }
    }

    private void Heapify(int[] a, int size, int index)
    {
        int value = a[index];

        while (index < size)
        {
            int childPos = index * 2 + 1;

            if (childPos < size)
            {
                if (childPos + 1 < size && a[childPos + 1] < a[childPos])
                {
                    childPos++;
                }

                if (value < a[childPos])
                {
                    a[index] = value;
                    return;
                }
                else
                {
                    a[index] = a[childPos];
                    index = childPos;
                }
            }
            else
            {
                a[index] = value;
                return;
            }
        }
    }

    private void SwapValues(int[] a, int i, int j)
    {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

Selection sort in C#

Selection sort - overview

Selection sort is an in-place comparison sort and it is quite simple and intuitive. It is inefficient for large lists and should thus only be used for arrays with a small numbers of items.

Description of the selection sort algorithm

Selection sort views the input array as two separate sublists. The list to the left contains the values that are already sorted. The values are sorted from left to right.

The list to the right contains the values remaining to be sorted.

Initially the array to the left is empty and the rest of the list constitutes the full input array.

Next, the algorithm will loop through all positions in the array from left to right and for each value it tries to find the smallest value in the right sublist and change places with the value at the current position.

Computational complexity

It is easy to show that selection sort has has a complexity of  O(n²) for all cases.

Example of an implementation of selection sort in C#

    private void SortArrayWithSelectionSort()
    {
        int[] array = { 7, 5, 23, 2, 0 };
        SelectionSort(array);

        // PrintResult(array);
    }

    private void SelectionSort(int[] a)
    {
        int minPos;
        int minVal;

        for (int i = 0; i < a.Length - 1; i++)
        {
            minPos = i;
            minVal = a[i];

            for (int j = i + 1; j < a.Length; j++)
            {
                if (a[j] < a[i] && a[j] < minVal)
                {
                    minPos = j;
                    minVal = a[j];
                }
            }

            SwapValues(a, i, minPos);
        }
    }

    private void SwapValues(int[] a, int i, int j)
    {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

Shell sort in C#

Shell sort - overview

Shell sort is a sorting algorithm developed by Donald Shell in 1959. It is an in-place comparison sort.

Shell noticed that the two other sorting algorithms bubble sort and insertion sort only moved elements one location at a time. It means that each element must move quite far before it finds its correct location. With Shells algorithm it is possible for elements to jump several locations at a time, which improves the execution time.

Shell sort can be viewed as a generalized version of insertion sort.

Description of the Shell sort algorithm

Shell sort works in the same way as insertion sort, but with the difference that the outer loop in insertion sort is surrounded with another loop. This extra loop is called the gap loop.

Instead of sorting values one by one, as in the insertion sort algorithm, we can now perform an insertion sort every g values (where g is equal to the gap value).

After each round of sorting g should be decreased. Shell suggested the following gap sequence:

N/2, N/4, ... , 1

The last round always has a gap size of 1, and that corresponds to a round with the original insertion sort. The previous sorting rounds makes the array almost sorted so that the array is prepared for the final round, so that it does not have to move the elements very far. Insertion sort is namely very quick if the elements in the array are already "roughly" sorted.

Any diminishing sequence can be used as gap sequence as long as the last value is 1. However, the computational complexity is quite dependent on the gap sequence. For example, instead of dividing the value by 2, the value 2.2 could be used. It has been shown that that value gives better performance than 2.

Computational complexity

Worst case performance is O(n²). Best case performance O(n log n). Average case performance depends on selection of gap sequence.

Example of an implementation of Shell sort in C#

    private void SortArrayWithShellSort()
    {
        int[] array = { 7, 5, 17 };
        ShellSort(array);

        // PrintResult(array);
    }
        
    private void ShellSort(int[] array)
    {
        int n = array.Length;
        int gap = n / 2;
        int temp;

        while (gap > 0)
        {
            for (int i = 0; i + gap < n; i++)
            {
                int j = i + gap;
                temp = array[j];

                while (j - gap >= 0 && temp < array[j - gap])
                {
                    array[j] = array[j - gap];
                    j = j - gap;
                }

                array[j] = temp;
            }

            gap = gap / 2;
        }
    }

Insertion sort in C#

Insertion sort - overview

Insertion sort is a sorting algoritm with a simple implementation. It is pretty efficient when the array to be sorted contains a small number of elements. It is also efficient when the array is already almost sorted.

Description of the insertion sort algorithm

Insertion sort works in almost the same way as when a person wants to sort a hand of for example 5 playing cards.

First the left hand holds no cards and the 5 cards are lying face down on the table. Then we pick one card at a time from the table. To find the position of the card we compare it with the cards in the left hand, from the right to the left. Throughout the algorithm the cards in the left hand will always be sorted.

Insertion sort is an in-place algorithm

The sorting is performed in place. It means that the numbers are moved around within the array. Because of that it requires only a constant amount O(1) of memory space.

Computational complexity

The best case performance is when the input array is already sorted. In that case the algorithm only needs to do O(n) work.

For worst and average case the algorithm has a complexity of  O(n²).

Example of an implementation of insertion sort in C#

    private void SortArrayWithInsertionSort()
    {
        int[] array = { 7, 5, 17, 3, 1, 4, 4 };
        InsertionSort(array);

        // PrintResult(array);
    }

    private void InsertionSort(int[] array)
    {
        int j;
        int temp;

        for (int i = 1; i < array.Length; i++)
        {
            j = i;
            while (j > 0 && array[j] < array[j - 1])
            {
                temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
                j--;
            }
        }
    }