Iterative or non-recursive version of Binary Tree Inorder, Preorder & Postorder

 public void nonRecursiveInorder(TNode root) {
        NodeStack s = new NodeStack(this.totNode);
        while (true) {
            while (root != null) {
                s.push(root);
                //System.out.println()
                root = root.left;
            }
            if (s.isEmpty()) {
                break;
            }
            root = s.pop();
            if (root == null) {
                break;
            }
            System.out.print(root.data + " ");
            root = root.right;
        }
    }

    public void nonRecursivePreorder(TNode root) {
        NodeStack s = new NodeStack(this.totNode);
        while (true) {
            while (root != null) {
                System.out.print(root.data + " ");
                s.push(root);
                //System.out.println()
                root = root.left;
            }
            if (s.isEmpty()) {
                break;
            }
            root = s.pop();
            if (root == null) {
                break;
            }
            root = root.right;
        }
    }

    public void nonRecursivePostorder(TNode root) {
        NodeStack s = new NodeStack(this.totNode);
        while (true) {
            while(root != null){
                if(root.right != null)
                    s.push(root.right);
                s.push(root);
                root = root.left;
            }
            if(s.isEmpty())
                break;
            root = s.pop();
            if(root == null)
                break;
            if(root.right != null && s.top() == root.right){
                s.pop();
                s.push(root);
                root = root.right;
            }else{
                System.out.print(root.data + " ");
                root = null;
            }
        }
    }

[Reference: http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/]

For TNode definition, please check my previous post.

Largest Sum Contiguous Subarray..

Reference: http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

public class MaxSubArray {

    /*
    Notes: Algorithm doesn't work for all negative numbers. It simply returns 0
    if all numbers are negative. For handling this we can add an extra phase
    before actual implementation. The phase will look if all numbers are negative,
    if they are it will return maximum of them (or smallest in terms of absolute
    value). There may be other ways to handle it though.
    */
    public int findMaxSubArray(int a[]){
        int max_so_far = 0;
        int max_ending_here = 0;
        for(int i=0; i<a.length; i++){
            max_ending_here += a[i];
            if(max_ending_here < 0)
                max_ending_here = 0;
            if(max_so_far < max_ending_here)
                max_so_far = max_ending_here;
        }
        return max_so_far;
    }
 
    /*
     * Another implementation which takes care of all +ve as well as -ve value.
     */
    public int findMaxSubArray2(int a[]){
        int max_so_far = a[0];
        int current_max = a[0];
        for(int i=1; i<a.length; i++){
            current_max = Math.max(a[i], current_max+a[i]);
            max_so_far = Math.max(max_so_far, current_max);
        }
        return max_so_far;
    }
 
    public static void main(String args[]){
        MaxSubArray msa = new MaxSubArray();
        int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
        int res = msa.findMaxSubArray(a);
        System.out.println("MaxSum: " + res);
        int b[] = {-2, -3, -4, -1, -2, -1, -5, -3};
        res = msa.findMaxSubArray2(b);
        System.out.println("MaxSum2: " + res);
    }
}

# Output

MaxSum: 7

MaxSum2: -1

To divide an array such that the sum of left half and right half is minimum.

/*
Prob: To divide an array such that the sum of left half and right half is minimum or partition an array in equal halves with minimum sum difference.
A = 1,2,3,4,5,6,7,8,9,10 #Array is not sorted
left=1,4,5,8,9,1 (sum=27) right=2,3,6,7,10(sum=28)
Complexity: O(n^2) Type: GREEDY
*/

public class DivideArray {

    int A[];
    boolean used[];
    int partition[];
    int left = 0;
    int right = 0;

    DivideArray() {
        A = null;
        used = null;
        partition = null;
        left = -1;
        right = -1;
    }

    DivideArray(int N) {
        A = new int[N];
        used = new boolean[N];
        partition = new int[N];
        left = 0;
        right = N - 1;
    }

    public int findNearest(int A[], boolean used[], int idx) {
        int min = 99999999;
        int minIndex = -1;
        for (int i = 0; i < A.length; i++) {
            if (i == idx) {
                continue;
            }
            if (used[i]) {
                continue;
            }
            int diff = Math.abs(A[idx] - A[i]);
            if (diff < min) {
                min = diff;
                minIndex = i;
            }
        }
        return minIndex;
    }

    public void partitionArr(int A[], boolean used[], int partition[]) {
        for (int i = 0; i < A.length; i++) {
            if (used[i]) {
                continue;
            }
            int j = findNearest(A, used, i);
            used[i] = true;
            if (j >= 0) {
                used[j] = true;
                if (sumLeft(partition, left) <= sumRight(partition, right)) {
                    partition[left++] = Math.max(A[i], A[j]);
                    partition[right--] = Math.min(A[i], A[j]);
                } else {
                    partition[left++] = Math.min(A[i], A[j]);
                    partition[right--] = Math.max(A[i], A[j]);
                }
            } else {
                // if size of array is odd
                if (sumLeft(partition, left) <= sumRight(partition, right)) {
                    partition[left++] = A[i];
                } else {
                    partition[right--] = A[i];
                }

            }
        }
        this.partition = partition;
    }

    public int sumLeft(int par[], int left) {
        int sum = 0;
        for (int i = 0; i <= left; i++) {
            sum += par[i];
        }
        return sum;
    }

    public int sumRight(int par[], int right) {
        int sum = 0;
        for (int i = right; i < par.length; i++) {
            sum += par[i];
        }
        return sum;
    }

    public static void main(String args[]) {

        Scanner sin = new Scanner(System.in);
        int N = sin.nextInt();
        DivideArray da = new DivideArray(N);

        for (int i = 0; i < N; i++) {
            da.A[i] = sin.nextInt();
        }
        // call partition function
        da.partitionArr(da.A, da.used, da.partition);
        System.out.print("LeftArray: ");
        for (int i = 0; i < da.left; i++) {
            System.out.print(da.partition[i] + " ");
        }
        System.out.print("\t(sum=" + da.sumLeft(da.partition, da.left - 1) + ")\nRightArray: ");
        for (int i = da.right + 1; i < N; i++) {
            System.out.print(da.partition[i] + " ");
        }
        System.out.println("\t(sum=" + da.sumRight(da.partition, da.right + 1) + ")");

    }
}


## Output
10
1 2 3 4 5 6 7 8 9  10
LeftArray: 2 3 6 7 10     (sum=28)
RightArray: 9 8 5 4 1     (sum=27)

9
9
1 2 3 4 5 6 7 8 9
LeftArray: 2 3 6 7 9     (sum=27)
RightArray: 8 5 4 1     (sum=18)

Quick Sort (in java)

public class QuickSort {

    public int A[] = null;

    public int partition(int A[], int low, int high) {
        int left, right, pivot_item = A[low];
        left = low;
        right = high;

        while (left < right) {
       
            while (left < right && A[left] <= pivot_item) {
                left++;
            }
            while (A[right] > pivot_item) {
                right--;
            }

            if (left < right) {
                int temp = A[right];
                A[right] = A[left];
                A[left] = temp;
            }
        }
     
        A[low] = A[right];
        A[right] = pivot_item;
        return right;
    }

    public void printArr() {
        System.out.print("Sorted: ");
        for (int i = 0; i < this.A.length; i++) {
            System.out.print(this.A[i] + ", ");
        }
        System.out.println();
    }

    public void quickSort(int A[], int low, int high) {
        int pivot;
        if (high > low) {
            pivot = partition(A, low, high);
           // System.out.println("Pivot: " + pivot);
            quickSort(A, low, pivot - 1);
            quickSort(A, pivot + 1, high);
        }
       // this.printArr();
    }

    public static void main(String args[]) {
        QuickSort sort = new QuickSort();
        sort.A = new int[]{2, 4, 5, 7, 1, 2, 3, 6};
        sort.quickSort(sort.A, 0, 7);
        // print sorted Array
        sort.printArr();
    }
}

Merge Sort in Java

public class MergeSort {

    public int A[], temp[]; //, size=0;

    MergeSort(int n) {
        A = new int[n];
        temp = new int[n];
        //size = n;
    }

    MergeSort() {
        A = null;
        temp = null;
        //size = 0;
    }

    public void mergeSort(int A[], int left, int right) {
        int mid;
        //System.out.println("A-len: " + this.A.length + " Temp-len: " + this.temp.length);
        if (left < right) {
            mid = (right + left) / 2;
            mergeSort(A, left, mid);
            mergeSort(A, mid + 1, right);
            merge(A, left, mid, right);
        }
    }

    public void merge(int A[], int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int L1[] = new int[n1];
        int L2[] = new int[n2];
     
        for (int i = 0; i < n1; i++) {
            L1[i] = A[left + i];
        }

        for (int i = 0; i < n2; i++) {
            L2[i] = A[mid + i + 1];
        }

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L1[i] <= L2[j]) {
                A[k] = L1[i];
                i++;
            } else {
                A[k] = L2[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            A[k] = L1[i];
            i++;
            k++;
        }

        while (j < n2) {
            A[k] = L2[j];
            j++;
            k++;
        }

    }

    public void printArr() {
        System.out.print("Sorted: ");
        for (int i = 0; i < this.A.length; i++) {
            System.out.print(this.A[i] + ", ");
        }
        System.out.println();
    }

    public static void main(String args[]) {
        MergeSort sort = new MergeSort();
        sort.A = new int[]{2, 4, 5, 7, 1, 2, 3, 6};
        sort.temp = new int[8];
        sort.mergeSort(sort.A, 0, 7);
        // print sorted Array
        sort.printArr();
    }
}

Find if a substring is exist in a given string !!

public class MatchString {
 
    public int matchStr(String str, String sub){
     
        if(str.length() < sub.length())
            return -1;
     
        for(int i=0; i<str.length() && (str.length()-i >= sub.length()); i++){
            String temp = str.substring(i, i+sub.length());
            //System.out.println("temp: " + temp);
            if(temp.equalsIgnoreCase(sub))
                return 1;
        }
     
        return -1;
    }
 
    public static void main(String args[]){
     
        MatchString ms = new MatchString();
        int res = ms.matchStr("abcdefgh", "cdfe");
        if(res < 0)
            System.out.println("Not Found!");
        else
            System.out.println("Match!");
    }
}

Find a number from sorted list where start and end of list is not known

Prob: find a number from a sorted list where start and end of list is not known. The moving pointer will rotate over from max to min and vice versa.

public class FindANumber {

    public int bTreeRotated(int A[], int start, int finish, int data) {
        int mid = start + (finish - start) / 2;
        if (start > finish) {
            return -1;
        }
        if (A[mid] == data) {
            return mid;
        } else if (A[start] <= A[mid]) {
            if (data >= A[start] && data <= A[mid]) {
                return bTreeRotated(A, start, mid - 1, data);
            } else {
                return bTreeRotated(A, mid + 1, finish, data);
            }
        } else //if(A[mid] <= A[finish]){
        if (data >= A[mid] && data <= A[finish]) {
            return bTreeRotated(A, mid + 1, finish, data);
        } else {
            return bTreeRotated(A, start, mid - 1, data);
        }
    }
 
    public static void main(String args[]){
        FindANumber fan = new FindANumber();
        int A[] = new int[]{15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14};
        int res = fan.bTreeRotated(A, 0, 11, 5);
        if(res < 0)
            System.out.println("Not Found!!");
        else
            System.out.println("Fund at " + res);
     
    }
}