The maximum-subarray problem

write a program to find the nonempty, contiguous subarray of an Array whose values have the largest sum.This contiguous subarray is called the maximum subarray.
/*
 * Brute Force
 */
int * FindMaxSubArray0(int A[], int n)
{
    int i,j,sum,high,low;
    int *max = (int *)malloc(n*sizeof(int));
    int *end_pos = (int *)malloc(n*sizeof(int));
    int *p = (int *) malloc(3* sizeof(int));
    for(i = 0; i < n; i++) {
          max[i] = A[i];
          end_pos[i] = i;
          sum = max[i];
          for(j = i+1; j < n; j++) {
                sum = sum + A[j];
                if(sum > max[i]) {
                        max[i] = sum;
                        end_pos[i] = j;
                }
          }
    }
    p[0] = 0;
    p[1] = end_pos[0];
    p[2] = max[0];
    for(i = 1; i < n; i++) {
          if(max[i] > p[2]) {
                  p[2] = max[i];
                  p[0] = i;
                  p[1] = end_pos[i];
          }
    }
    return p;
}
/*
 * Divide-and-Conquer strategy
 */
int * FindMaxCrossSubArray(int A[],int low,int high,int mid)
{
     int i,sumleft = A[mid],sumright = A[mid+1], sum,left,right;
     int *p =(int *)malloc(sizeof(int) * 3);
     sum = sumleft;
     left = mid;
     for(i = mid-1; i > low; i--) {
           sum = sum+ A[i];
           if(sum > sumleft) {
                   sumleft = sum;
                   left = i;
           }
     }
     sum=sumright;
     right = mid+1;
     for(i = mid+2; i < high; i++) {
           sum = sum + A[i];
           if(sum > sumright) {
                   sumright = sum;
                   right = i;
           }
     }
     p[0] = left;
     p[1] = right;
     p[2] = sumleft+sumright;
     return p;
}
int * FindMaxSubArray1(int A[], int low, int high)
{
     int mid, *left=NULL, *right=NULL, *cross=NULL, *p = NULL;
     if(low == high) {
            p =(int *)malloc(sizeof(int) * 3);
            p[0] = p[1] = low;
            p[2] = A[low];
            return p;
     } else {
            mid = (low+high)/2;
            left = FindMaxSubArray1(A,low,mid);
            right = FindMaxSubArray1(A,mid+1,high);
            cross = FindMaxCrossSubArray(A,low,high,mid);
            if(left[2] >= right[2] && left[2] >= cross[2]) {
                       return left;
            } else if(right[2] >= left[2] && right[2] >= cross[2]) {
                   return right;
            } else {
                   return cross;
            }
     }
}
/*
 * Dynamic Programmming Methodology
 */
int * FindMaxSubArray2(int A[], int n)
{
    int *max, *end_pos, sum=0,*p,i;
    max = (int*) malloc(sizeof(int)*n);
    end_pos = (int*) malloc(sizeof(int)*n);
    p = (int*) malloc(sizeof(int)*3);
    for(i = 0; i < n; i++) {
          max[i] = A[i];
          end_pos[i] = i;
    }
    for(i = 1; i < n; i++) {
          sum = max[i-1] + max[i];
          if(sum > max[i]) {
                  max[i] = sum;
                  end_pos[i] = i;
          }
    }
    p[2] = max[0];
    for(i = 1; i < n; i++) {
          if(max[i] > p[2]) {
                    p[2] = max[i];
                    p[1] = i;
          }
    }
    for(i = p[1]; i > 0; i--) {
          if(end_pos[i] == i) {
                        p[0] = i;
                        break;
          }
    }
}

Inversion

Let A[1..n] be an array of n distinct numbers.If i < j and A[i] > A[j], then the pair (i,j) is called an inversion of A.
Consider the array (2,3,8,6,1). Inversions in array are (8,6), (2,1), (3,1) , (8,1), (6,1).

Write program to count the number of inversion in array.

/*
 * CountInverion0 : This is modified version of insertion sort. Time Complexity : O(n^2)
 */
int CountInversion0(int a[], int n)
{
    int i,j,count=0;
    for(i=1; i<n; i++) {
             for(j=0; j<i; j++)
                      if(a[j] > a[i])
                              count++;
    }
    return count;
}

/*
 * CountInversion1 : Modifed version of Merge sort. Uses Divide and Conquer Methodlogy.
 * TimeComplexity: O(n*log(n)).
 */
int CountInversion1(int A[], int start, int end)
{
    int i,x,y;
    int z=0;
    if((end-start) == 0) return 0;
    else if(start < end) {
        i = (start+end)/2;
        x = CountInversion1(A, start , i);
        y = CountInversion1(A, i+1, end);
        z = CountSplitInversion(A,start,end,i);
        return x+y+z;
    }
}
/*
 * Helper function: sorts array and also count the number of inversion.
 * Hint : in case of merge sort, while merging if we copy the number from 2nd array to array,
 * number of elements lefts in first array adds to the number of inversions.
 */
int CountSplitInversion(int a[],int start, int end, int div)
{
    int i,j,k,lc = (div-start)+1,rc = (end-div),*l,*r,count = 0;
    l = (int *) malloc(sizeof(int) * (lc+1));
    r = (int *) malloc(sizeof(int) * (rc+1));
    for(i=0; i < lc; i++)
        l[i] = a[start + i];
    for(i=0; i < rc; i++)
        r[i] = a[div+i+1];
    for(k=start,i=0,j=0; k <= end && (i < lc) && (j <rc) ;k++)
    {
        if(l[i] <= r[j]) {
            a[k] = l[i]; i++;
        }
        else {
            a[k] = r[j]; j++;
            count +=  (lc - i);
        }
    }
    if(i < lc) {
        for(;k<=end && i<lc ;k++)
            a[k] = l[i];
    }
    if(j < rc) {
        for(;k<=end && j<rc ;k++)
            a[k] = r[j];
    }
    return count;
}

Write a recursive procedure for Insertion Sort

Do recursion and after that insert the value.
/*
 * Helper function, Insert val at proper position
 */ 
void insert(int a[], int n, int val)
{
     int i;
     for(i=n-1; i >= 0  && a[i] < val; i--)
                a[i+1] = a[i];
     a[i+1] = val;
}
/*
 * Recursive version of Insertion Sort
 */
void insertRsort(int a[], int n)
{
     if(n>0) {
             insertRsort(a, n-1);
             insert(a, n, a[n]);
     }
}

Print a singly-linked list backwards, in linear time

/*
 * Print a singly-linked list backwards in linear time.
 */
void print(nodeptr head)
{
        if(head == NULL) return;
        print(head->next);
        printf("%d  ",head->data);
}

Tree - List Problem

Write a recursive function treeToList(Node root) that takes an ordered binary tree and rearranges the internal pointers to make a circular doubly linked list out of the tree nodes.

/********************************************************
 ****      The Great Tree List Recursion Problem     ****
 *******************************************************/
struct node;

typedef struct node *nodeptr;

struct node {
    nodeptr left;
    int data;
    nodeptr right;
};

/*
 * given two list nodes, join them together so the second
 * immediately follows the first.
 */
void join(nodeptr a, nodeptr b)
{
    a->right = b;
    b->left = a;
}
/*
 * given two circular doubly linked lists, append them
 * and return the new list.
 */
nodeptr append(nodeptr a, nodeptr b)
{
    nodeptr aLast, bLast;

    if(a == NULL) return b;
    if(b == NULL) return a;
   
    aLast = a->left;
    bLast = b->left;

    join(aLast,b);
    join(bLast,a);

    return a;
}
/*
 * Convert given BST to linked list
 */
nodeptr treeToList(nodeptr root)
{
    nodeptr aList, bList;
    if(root == NULL)
        return NULL;
    else {
        aList = treeToList(root->left);
        bList = treeToList(root->right);
       
        root->left = root;
        root->right = root;
       
        aList = append(aList, root);
        aList = append(aList, bList);

        return aList;
    }
}
/*
 * print circular doubly linked list
 */
void printList(nodeptr head)
{
    nodeptr temp = head;
    if(head != NULL) {
        while(head->right != temp) {
            printf("%d ", head->data);
            head = head->right;
        }
        printf("%d ", head->data);
    }
    printf("\n");
}

Given a Binary Tree check whether it is Binary Search Tree or not

Write an isBST() function that returns true if a tree is a binary search tree
and false otherwise.

/*
 * Is BST helper function
 */
int isBSTUtil(nodeptr node, int min, int max)
{
    if(node != NULL)
        return (node->data >= min && node->data <=max) &&
            isBSTUtil(node->left, min, node->data) &&
            isBSTUtil(node->right, node->data, max);
    return 1;
           
}
/*
 * determine given binary tree is BST
 */
int isBST(nodeptr node)
{
    int min,max;
    if (node != NULL) {
        min = minValue(node);
        max = maxValue(node);
        return isBSTUtil(node, min, max);
    }
    return 1;
}

Check given two binary trees are same or not

Given two binary trees, return true if they are structurally identical -- they are made of nodes with the same values arranged in the same way.



/*
 * Compare two binary tree and return true if they are
 * structurally identical.
 */
int sameTree(nodeptr a, nodeptr b)
{
    if(a == NULL && b == NULL)
        return 1;
    else if((a == NULL && b != NULL) || (a != NULL && b == NULL))
        return 0;
    else {
        return (a->data == b->data && sameTree(a->left, b->left) &&
                sameTree(a->right, b->right));
    }
}

mirror()

Change a tree so that the roles of the left and right pointers are swapped at every node.




/*
 * Mirror image of given tree
 */
void mirror(nodeptr node)
{
    nodeptr temp;
    if(node != NULL)
    {
        temp = node->left;
        node->left = node->right;
        node->right = temp;
        mirror(node->left);
        mirror(node->right);
    }
}

Print all paths of Binary Tree

Given a binary tree, print out all of its root-to-leaf paths.

/*
 * Print array
 */
void printArray(int *path, int pathlen)
{
    int i;
    for(i = 0; i < pathlen; i++) {
        printf("%d ",path[i]);
    }
    printf("\n");
}
/*
 * Helper function to print all paths
 */
void printPathsRecur(nodeptr node, int path[], int pathLen)
{
    path[pathLen] = node->data;
    pathLen++;
    if(node->left == NULL && node->right == NULL) {
        printArray(path, pathLen);
    } else {
        printPathsRecur(node->left, path, pathLen);
        printPathsRecur(node->right, path, pathLen);
    }
}
/*
 * Print all paths
 */
void printPaths(nodeptr node)
{
    int path[200];
    if(node != NULL)
    {
        printPathsRecur(node, path, 0);
    }
}

hasPathSum - Binary Tree

Given a binary tree and a sum, return true if the tree has a root-to-leaf path such that adding up all the values
along the path equals the given sum. Return false if no such path can be found.

So for example, the following tree has exactly four root-to-leaf paths:
                       5
                   /        \
                4           8
              /          /       \         
          11         13        4
         /     \                     \
       7       2                    1

Root-to-leaf paths:
path 1: 5 4 11 7
path 2: 5 4 11 2
path 3: 5 8 13
path 4: 5 8 4 1
For this problem, we will be concerned with the sum of the values of such a path -- for example, the sum of the values on the 5-4-11-7 path is 5 + 4 + 11 + 7 = 27.

/*
 * "root-to-leaf path" to be a sequence of nodes in a tree
 * starting with the root node and proceeding downward to a leaf.
 */
int hasPathSum(nodeptr node, int sum)
{
    int subsum;
    if(node == NULL) {
        return (sum == 0);
    } else {
        subsum = sum - node->data;
        return (hasPathSum(node->left, subsum) ||
                hasPathSum(node->right, subsum));
    }
}

Intersection of two lists

Given two lists sorted in increasing order, create and return a new list representing the intersection of the two lists. The new list should be made with its own memory — the original lists should not be changed.

/*
 * Insert an element in linked list
 */
void Insert(nodeptr* head, int data) {
     nodeptr newNode = (nodeptr) malloc(sizeof(struct node));
     if(newNode == NULL)
                return;
     newNode->data = data;
     newNode->next = *head;
     *head = newNode;
}
/*
 * Compute a new sorted list that represents the intersection
 * of the two given sorted lists.
 */
nodeptr SortedIntersect(nodeptr a, nodeptr b)
{
    nodeptr newList = NULL,temp;
    if(a == NULL || b == NULL) return NULL;
    else {
        while(a != NULL) {
            temp = b;
            while(temp != NULL && a->data < temp->data)
                temp = temp->next; 
            if(temp != NULL) {
                if(a->data == temp->data){
                    Insert(&newList, a->data);
                }
            }
            a = a->next;
        }
        return newList;
    }
}

Sort a List using Merge Sort

Write Merge sort routine for sorting linked list

/*
 * Merge Sort
 */
void MergeSort(nodeptr* headRef) {
    nodeptr head = *headRef;
    nodeptr a;
    nodeptr b;

    if ((head == NULL) || (head->next == NULL)) {
        return;
    }

    FrontBackSplit(head, &a, &b); // Split list into 'a' and 'b' sublists

    MergeSort(&a); // Recursively sort the sublists  'a' and 'b'
    MergeSort(&b);

    *headRef = SortedMerge(a, b); //merge the two sorted lists together
}

/*
 * Takes two lists sorted in increasing order, and splices their 
 * nodes together to make one big sorted list which is returned.
 */
nodeptr SortedMerge(nodeptr a, nodeptr b)
{
    nodeptr result = NULL;
    nodeptr* lastPtrRef = &result;

    while (1) {
        if (a == NULL) {
            *lastPtrRef = b;
            break;
        }
        else if (b == NULL) {
            *lastPtrRef = a;
            break;
        }
        if (a->data <= b->data) {
            MoveNode(lastPtrRef, &a);
        } else {
            MoveNode(lastPtrRef, &b);
        }
        lastPtrRef = &((*lastPtrRef)->next);
    }
   
    return(result);
}

/*
 * Split the nodes of the given list into front and back halves,
 * and return the two lists using the reference parameters.
 * If the length is odd, the extra node should go in the front list.
 */
void FrontBackSplit(nodeptr source, nodeptr* frontRef, nodeptr* backRef)
{
    nodeptr singlestep = NULL;
    nodeptr doublestep = NULL;
    if(source == NULL) {
        *frontRef = NULL;
        *backRef = NULL;
    } else {
        *frontRef = source;
        doublestep = source->next;
        singlestep = source;
        while(doublestep != NULL) {
            if(doublestep->next != NULL)
                doublestep = doublestep->next->next;
            else 
                break;
            singlestep = singlestep->next;
        }
        *backRef = singlestep->next;
        singlestep->next = NULL;
    }
}

Reverse a given Linked List

Write an Reverse() function which reverses a list by rearranging all the .next pointers and the head pointer.
 

/* 
 * Iteratively reverse the given linked list by changing its .next pointers and
 * its head pointer. Takes a pointer (reference) to the head pointer.
 */
void Reverse(nodeptr* headRef)
{
    nodeptr current = *headRef, nextNode, tempNode;
    if(current == NULL || current->next == NULL) return;
    else {
        nextNode = current->next;
        current->next = NULL;
        while(nextNode != NULL) {
            tempNode = nextNode->next;
            nextNode->next = current;
            current = nextNode;
            nextNode = tempNode;
        }
        *headRef = current;
    }
}

/*
 * Recursively reverses the given linked list by changing its .next
 * pointers and its head pointer. Takes a pointer (reference) to the
 * head pointer.
 */
void RecursiveReverse(nodeptr* headRef)
{
    nodeptr current, rest;
    if(current == NULL) return;
    current = *headRef;
    rest = current->next;
    if(rest == NULL) return;
    RecursiveReverse(&rest);
    current->next->next = current;
    current->next = NULL;
    *headRef = rest;
}

Suffle Merge

Given two lists, merge their nodes together to make one list, taking nodes alternately between the two lists. So ShuffleMerge() with {1, 2, 3} and {7, 13, 1} should yield {1, 7, 2, 13, 3, 1}.

/*
 * Merge the nodes of the two lists into a single list taking a
 * nodes alternately from each list, and return the new list.
 */
nodeptr ShuffleMerge(nodeptr a, nodeptr b)
{
    nodeptr current = NULL, tempnode = NULL;
    if (a == NULL && b == NULL) return NULL;
    else if (a == NULL) return b;
    else if (b == NULL) return a;
    else {
        current = a;
        tempnode = current->next;
        while(current->next != NULL && b->next != NULL)
        {
            current->next = b;
            b = b->next;
            current = current->next;
            current->next = tempnode;
            current = current->next;
            tempnode = current->next;
        }
        if(b)
            current->next = b;
        if(current)
            current->next = tempnode;
        return a;
    }
}

Split list into two sublists

Write a function AlternatingSplit() which takes one list and divides up its nodes to make two smaller lists. The sublists should be made from alternating elements in the original list. So if the original list is {a, b, a, b, a}, then one sublist should be {a, a, a} and the other should be {b, b}.

/*
 * Give the source list, split its nodes into two shorter lists.
 * aRef should be set to point to the list of odd position elements,
 * and bRef should be set to point to the list of even position elements.
 * The elements in the new lists may be in any order.
 */
void Split(nodeptr source, nodeptr* aRef, nodeptr* bRef)
{
    nodeptr current , next, temp;
    if(source == NULL) {
        *aRef = NULL;
        *bRef = NULL;
    } else {
        current = source;
        next = current->next;
        *aRef = current;
        *bRef = next;
        while(next != NULL) {
            temp = next->next;
            current->next = temp;
            current = temp;
            if(current != NULL) {
                next->next = current->next;
                next = current->next;
            } else {
                next->next = NULL;
                next = NULL;
            }
        }
        if(current != NULL)
            current->next = NULL;
    }
}

Remove Duplicates from list

Write a RemoveDuplicates() function which takes a list sorted in increasing order and deletes any duplicate nodes from the list. Ideally, the list should only be traversed once.
 

/*
 * Remove duplicates from a sorted list
 */
void RemoveDuplicates(nodeptr head)
{
    nodeptr current = head;
    nodeptr tempnode;
    while(current != NULL) {
        if(current->next != NULL) {
            if(current->data == current->next->data) {
                tempnode = current->next;
                current->next = tempnode->next;
                free(tempnode);
            }
        }
        current = current->next;
    }
}

Split given list into two sublists

Given a list, split it into two sublists — one for the front half, and one for the back half. If the number of elements is odd, the extra element should go in the front list. So FrontBackSplit() on the list {2, 3, 5, 7, 11} should yield the two lists {2, 3, 5} and {7,11}.

Trickier way to do this problem is to have two pointers which traverse the list. One pointer advances two nodes at a time, while the other goes one node at a time. When the leading pointer reaches the end, the trailing pointer will be about half way.

/*
 * Split the nodes of the given list into front and back halves,
 * and return the two lists using the reference parameters.
 * If the length is odd, the extra node should go in the front list.
 */
void FrontBackSplit(nodeptr source, nodeptr* frontRef, nodeptr* backRef)
{
    nodeptr singlestep = NULL;
    nodeptr doublestep = NULL;
    if(source == NULL) {
        *frontRef = NULL;
        *backRef = NULL;
    } else {
        *frontRef = source;
        doublestep = source->next;
        singlestep = source;
        while(doublestep != NULL) {
            if(doublestep->next != NULL)
                doublestep = doublestep->next->next;
            else 
                break;
            singlestep = singlestep->next;
        }
        *backRef = singlestep->next;
        singlestep->next = NULL;
    }
}

Sorting List using Insertion Sort

Write a program to sort a list using insertion sort.

/*

 * Node of list

 */

struct node {
       int data;
       struct node* next;
};
typedef struct node* nodeptr;

/*
 * Insert a node into its sorted position
 */
void SortedInsert(nodeptr* head, nodeptr newNode)
{
    nodeptr currentNode = *head;
    nodeptr prevNode = NULL;
    while(currentNode != NULL && currentNode->data < newNode->data) {
        prevNode = currentNode;
        currentNode = currentNode->next;
    }
    newNode->next = currentNode;
    if(prevNode == NULL)
        *head = newNode;
    else
         prevNode->next = newNode;
} 

/* 
 * Insert Sort List
 */
void InsertSort(nodeptr* head)
{
    nodeptr current = *head;
    nodeptr list = NULL;
    nodeptr next = NULL;
    while(current!= NULL)
    {
        next = current->next;
        SortedInsert(&list,current);
        current = next;
    }
    *head = list;
}

Make a copy of Linked List

Write a procedure to make a copy of given Linked List.

Below we have both iterative and recursive procedure. But recursive procedure is not good as it requires extra stack space proportional to its length.

/*
 * Node of Linked List
 */
struct node {
       int data;
       struct node* next;
};
typedef struct node* nodeptr;

/*
 * Make a duplicate copy of given linked list(Iterative Procedure)
 */
nodeptr CopyListIterative(nodeptr head)
{
        nodeptr current = head;
        nodeptr newList = NULL;
        nodeptr tail = NULL;
        while(current != NULL) {
                      if(newList == NULL) {
                                 newList = (nodeptr) malloc(sizeof(struct node));
                                 newList->data = current->data;
                                 newList->next = NULL;
                                 tail = newList;
                      } else {
                                 tail->next = (nodeptr) malloc(sizeof(struct node));
                                 tail = tail->next;
                                 tail->data = current->data;
                                 tail->next = NULL;
                      }
                      current = current->next;
        }
        return newList;
}

/*
 * Make a duplicate copy of given linked list(Recursive Procedure)
 */
nodeptr CopyListRecursive(nodeptr head)
{
        if(head == NULL) return NULL;
        else {
             nodeptr current = head;
             nodeptr newList = (nodeptr) malloc(sizeof(struct node));
             newList->data = current->data;
             newList->next = CopyList(current->next);
             return newList;
        }
}