Check for children sum property in a binary tree

Problem: Given a binary tree, write a function that returns true if the tree satisfies below property:
For every node, data value must be equal to sum of data values in left and right children. Consider data value as 0 for NULL children.

Algorithm: Traverse the given binary tree. For each node check (recursively) if the node and both its children satisfy the Children Sum Property, if so then return true else return false.

Implementation:

bool isSumProperty(Node* node)
{
  int left_data = 0,  right_data = 0;
  if(node == NULL || (node->left == NULL && node->right == NULL))
    return true;
  else
  {
    if(node->left != NULL)
      left_data = node->left->data;
    if(node->right != NULL)
      right_data = node->right->data;
    if((node->data == left_data + right_data)&&
        isSumProperty(node->left) &&
        isSumProperty(node->right))
      return true;
    else
      return false;
  }
}

Range Minimum Query(RMQ)

Range Minimum Query (RMQ) is used on arrays to find the position of an element with the minimum value between two specified indices i.e. Given an array A[0,n-1] of n objects, Range Minimum Query from i to j asks for the position of a minimum element in the sub-array A[i, j].             

                

 
                                    

Preprocess RMQ:

             

The best approach  is to preprocess RMQ for sub arrays of length 2^k using dynamic programming. Keep an array M[ 0, N-1 ] [ 0, logN ] where M[ i ] [ j ] is the index of the minimum value in the sub array starting at i having length 2^j. Here is an example:

     

For computing M [ i ] [ j ] we must search for the minimum value in the first and second half of the interval. It's obvious that the small pieces have 2^{j - 1} length, so the recurrence is:

Implementation of the preprocessing function is as follows:

int** preprocess(int *A, int size)

{

    int **M = new int*[size];

    int logN = logbase2(size);

    for(int i=0; i<10; M[i++] = new int[logN]);

   

    // Generating Table of M[n][log(n)]

    for(int i=0; i<10; ++i)

        M[i][0] = i;

   

    for(int j=1; (1<<j) <= 10; ++j)

    {

        for(i=0; i+(1<<j)-1 < 10; ++i)

        {

            if(A[M[i][j-1]] <= A[M[i+(1<<(j-1))][j-1]])

                M[i][j] = M[i][j-1];

            else

                M[i][j] = M[i+(1<<(j-1))][j-1];

        }

      }

    return M;

}

RMQ Function:

Once we have these values preprocessed, We can use them to calculate RMQ_A(i, j). The idea is to select two blocks that entirely cover the interval [i..j] and  find the minimum between them. Let k = [log(j - i + 1)]. For computing RMQ_A(i, j) we can use the following formula:

Implementation of RMQ function is as follows:

int* RMQ(int *A, int size, int i, int j)
{

    int **M = preprocess(A, size);

    int k=0;

    while((1<<k++) < (j-i));

    --k;

    if(A[M[i][k]] <= A[M[j-(1<<k)+1][k]])

        return A[M[i][k]];

    else

        return A[M[j-(1<<k)+1][k]];

}

You can see the complexity of preprocess( ) function is O(nlogn) and complexity of RMQ function is O(1).

Knuth-Morris-Pratt(KMP)

String Matching Problem:

             

            Suppose a Text is an array T[1..n] of length n and pattern is also an array P[1..m] (m <= n). We say pattern P occurs with shift s in Text T if 0 <= s <= n-m and T[s+1..s+m] = P[1..m] i.e. T[s + j] = P[j] for all 1 <= j <=m.

             

                 If P occurs with shift s in T the s is a valid shift otherwise it is an invalid shift.The string matching problem is the problem of finding all valid shifts with which a given Pattern P occurs in a given Text T.

 
                                   

Notation and Terminology:

Prefix : W is a prefix of string x if x = wy for some string y.

Suffix : W is suffix of string x if x = yw for some string y.

xy – string concatenation   | x | - length of string x

Knuth-Morris-Pratt Algorithm:

Knuth, Morris and Pratt proposed a linear time algorithm for the string matching problem.

A matching time of O(n) is achieved by avoiding comparisons with elements of T that have previously been involved in comparison with some elements of the pattern P to be matched. i.e., backtracking on the string T never occurs.

Components of KMP Algorithm:

Prefix Function Π: Prefix function Π for a pattern encapsulate knowledge about how the pattern matches against shifts of itself.

         

Knowing these q text characters allows us to determine immediately that certain shifts are invalid since the first character a would be aligned with a text character that is known to match with second pattern character b. So next shift should be s = s + 2.

           

 Given P[1..q] matches T[s+1..s+q] what is the least shift s1 > s such that

 P[1..k] = T[s1+1 . . s1+k] where s1 + k = s + q

Prefix function Π [q] = max ( k : k < q and P_k is suffix of P_q  ) where P_k  is P[1..k] i.e.  " Π[q] is the length of longest prefix of P that is a proper suffix P_q ."

My implementation of Prefix function is as follows:

int* Prefix(char *pattern)

{

    int len = strlen(pattern);

    int *pre = new int[len];

    pre[0] = 0;

    int k = 0;

    for(int i=1; i<len; ++i)

    {

        while(k>0 && pattern[k] != pattern[i])

            k = pre[k];

        if(pattern[k] == pattern[i])

            ++k;

        pre[i] = k;

    }

    return pre;

}

KMP Matcher:  With text T, pattern P and prefix function Π as inputs, it finds all the occurrence of P  in T and returns the number of shifts of  P after which occurrence is found.

Implementation of KMP Match function is as follows:

 bool Match(char *text, char *pattern, vector<int>& shifts)

{

    int textLength = strlen(text);

    int patrnLength = strlen(pattern);

    int* prefixArray = Prefix(pattern); // Π function

    bool found = false;

    int q = 0;

    for(int i=0; i<textLength; ++i)

    {

        while( q>0 && pattern[q] != text[i])

            q = prefixArray[q-1]; //Next character does not macth

        if(pattern[q] == text[i])

            ++q;  //Next character Matched

        if(q == patrnLength) //All matched

        {

            shifts.push_back(i-patrnLength);

            found = true;

            q = prefixArray[q-1];  //Look for next match

        }

       

    }

    return found;

}

You can see both prefix( ) function and Match function takes linear time to execute.

Count Sort

This sorting algorithm takes advantage of the range of the numbers in the array to be sorted.
Say the range is 0..k then it can sort the array in O(k). If k is less than or equal to n, we are in great advantage because we can sort this array in linear time i.e. O(n).

The algorithm first determine for each element x the number of elements less than x. One of the advantage of this algorithm is its stability.

Following is my implementation:

void countSort(int *a, int size)
{
    int max = Max(a);
    int *c = new int[max+1];
    int *sorted = new int[size];
    for( int i=0; i<size; ++c[a[i++]] );   // Step 1
    for( i=1; i<max; c[i++] += c[i-1] );     // Step 2:Get the number of elements less than each number
    for(i=size-1; i >= 0; --i)    // Step 3
    {
        sorted[c[a[i]]-1] = a[i];
        --c[a[i]];
    }
    for(i=0; i<size; ++i)
        a[i] = sorted[i];
}

Example --

Input Array   

2

5

3

0

2

3

0

3

Step 1: Array C

2

0

2

3

0

1

Step 2: Array C

2

2

4

7

7

8

Step 3:

 a[7] = 3  c[3] = 7 sorted [6] = 3 => c[3] = 6

3

a[6] = 0  c[0] = 2  sorted[1] = 0  => c[0] = 1

0

3

a[5] = 3  c[3] = 6  sorted[5] = 3  => c[3] = 5

0

3

3

.

.

.

.

In the End Sorted array

0

0

2

2

3

3

3

5

Pancake sorting

Given an an unsorted array, sort the given array. You are allowed to do only following operation on array:
rev(arr, i): Reverse arr from 0 to i

Implementation:

void rev(int *arr, int i)
{
     int start = 0;
     while(start < i)
     {
                 swap(arr[start], arr[i]);
                 --i;
                 ++start;
     }
}

int findMaxIndex(int *arr, int n)
{
    int max = 0;
    for(int i = 0; i < n; ++i)
    {
            if(arr[i] > arr[max])
                      max = i;
    }
    return max;
}

void panCakeSort(int *arr, int n)
{
     for(int currSize = n; currSize > 1; --currSize)
     {
             int mi = findMaxIndex(arr, currSize);
             if(mi != currSize - 1)
             {
                   rev(arr, mi);
                   rev(arr, currSize - 1);
             }
     }

}

Microsoft Question: Nuts and Bolts problem

Question: Given an array of nuts of different sizes and array bolts of different sizes. There is a one-one mapping between nuts and bolts. Match nuts and bolts efficiently with the given constraint that comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller.

Solution: Tweak quick sort to achieve it.

Implementation:

int split(int *arr, int low, int high, int pivot)

{

        int j = low;

        for(int i = low; i < high; ++i)

        {

                if(arr[i] < pivot)

                {

                        std::swap(arr[i], arr[j]);

                        ++j;

                }

                else if(arr[i] == pivot)

                {

                        std::swap(arr[i], arr[high]);

                        --i;

                }

        }

        std::swap(arr[j], arr[high]);

        return j;

}

void matchNutsBolts(int *nuts, int *bolts, int low, int high)

{

        if(!nuts || !bolts)

                return;

        if(low < high)

        {

                int pivot = split(nuts, low, high, bolts[high]);

                split(bolts, low, high, nuts[pivot]);

                matchNutsBolts(nuts, bolts, low, pivot - 1);

                matchNutsBolts(nuts, bolts, pivot + 1, high);

        }

}

Complexity: O(nlogn)

Wave sort an array.

Question: Given an unsorted array, sort it in wave form. Wave sorted array looks like as follows:
arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4]...

Solution: Traverse all elements at even positions in the array and compare nth element with it's previous element(n-1th), if it is greater than previous, swap previous and current.
Now, again compare the nth element with its next element(n + 1th), if it is greater than next, swap next and current.

Implementation:

void sortWave(int* arr, int len)

{

        if(arr == NULL || len == 0 || len == 1)

                return;

        for(int i = 0; i < len; i+=2)

        {

                if(i>0 && arr[i-1] > arr[i])

                        std::swap(arr[i], arr[i-1]);

                if(i<len-1 && arr[i] < arr[i+1])

                        std::swap(arr[i], arr[i+1]);

        }

}

Complexity: O(n)

Alternative approach: Sort the array and swap adjacent elements. But the complexity of this approach will be O(nlogn)