Level Order Traversal in a Binary Tree from Bottom to Top

    public void LevelOrderReverse()    {
        System.out.println(LevelOrderReverse(this));
    }
    private String LevelOrderReverse(BinarySearchTree T)    {
        StringBuffer sb = new StringBuffer();
        if(T!=null)    {
            Queue<BinarySearchTree> Q = new LinkedList<BinarySearchTree>();
            Stack<BinarySearchTree> S = new Stack<BinarySearchTree>();
            Q.add(T);
            while(Q.size() > 0)    {
                BinarySearchTree C = Q.remove();
                if (C.right != null)
                    Q.add(C.right);
                if (C.left != null)
                    Q.add(C.left);
                S.push(C);
            }
            while(S.size() > 0)
                sb.append(S.pop().data).append(", ");
        }
        return sb.toString();
    }

Amazon Question: +1 or -1 Array Searching

Given an array, next element is either +1 or -1 of previous element then find any number k ?

    public int getIndex(int element, int[] input) { //element = k
        int size = input.length;
        for(int i=0; i < size;) {
            if(input[i]==element)
                return i;
            i=i+getPositive(element - input[i]);
        }
        return -9999; // element not found
    }
    private int getPositive(int i)    {
        if (i>0) return i;
        return (i * -1);
    }

Example 1:
Input: 4 5 4 5 6 7 8 9 8 9 10 11
k = 8
Output = 6

Example 2:
Input: 11 10 9 8 7 6 5 4 5 6 7 8 9 10 11
k = 4
Output = 7

Bucket Sort

Amazon Question: Given an array with 3 distinct elements, sort the elements in O(n) complexity
Input: 1,3,1,2,3,1,2,2,3
Output: 1, 1, 1, 2, 2, 2, 3, 3, 3


import java.util.ArrayList;

public class BucketSort {
    ArrayList> bucket;
    private int count;
    public BucketSort(int unique_int_count) {
        this.count = unique_int_count;
        this.bucket = new ArrayList>();
        for(int i=0; i < this.count; i++) {
            bucket.add(new ArrayList());
    }
    public ArrayList Sort(ArrayList input)    {
        for(int c:input)    {
            if(c==1)    {
                bucket.get(0).add(c);
            }    else if(c==2)    {
                bucket.get(1).add(c);
            }    else    {
                bucket.get(2).add(c);
            }
        }
        ArrayList sorted_output = new ArrayList<>();
        for(int i=0; i < count; i++) {
            sorted_output.addAll(bucket.get(i));
        return sorted_output;
    }
    @Override
    protected void finalize() throws Throwable {
        bucket=null;
        super.finalize();
    }
}
//----------------------Main Method------------------------
    public static void main(String[] args) {
        BucketSort b = new BucketSort(3);
        ArrayList input = new ArrayList();
        input.add(1);
        input.add(3);
        input.add(1);
        input.add(2);
        input.add(3);
        input.add(1);
        input.add(2);
        input.add(2);
        input.add(3);
        System.out.println(b.Sort(input));
    }

Amazon Question: Print Last N nodes of Linked List in reverse

Given a singly linked list's head and an integer N, print last N nodes of the list in reverse order.
Example:
List = 1->2->3->4->5->6->7->8
N = 3
Output = 8, 7, 6,

    public void printRev(int count)    { // count = N
        temp = count;
// this here is the head node
        System.out.println(printRev(this, new StringBuffer()));
    }
    private int temp;
    private String printRev(LinkedList L, StringBuffer sb)    {
        if(L.next!=null)
            printRev(L.next, sb);
        if(temp>0)    {
            sb.append(L.data).append(", ");
            temp--;
        }
        return sb.toString();
    }

Tamil Kumari FM Talk about Birds

This is a talk about Birds which I gave 3 years ago in Kumari FM about Origin of Birds, Living Birds, Conservation of Birds.

Find if a Tree is a Binary Search Tree

public boolean isBinarySearchTree() {
return isBinarySearchTree(this, -99999, 99999);
}
public boolean isBinarySearchTree(BinarySearchTree T, int min, int max) {
if(T==null)return true;
if(T.data>min && T.data<max 
&& isBinarySearchTree(T.left, min, T.data) && isBinarySearchTree(T.right, T.data, max))
return true;
return false;
}

Find Maximum Sum of a SubArray

Example Input: -1,2,6,4,-4,-5,56,78,-2,9
Desired Output: 134 

    public int MaxSumOfSubArray(int... input)    {
        int size = input.length;
        int max = 0;
        boolean isIn = false;
        int current_sum = 0;
        int previous = -1;
        for(int i=0; i<size; i++)    {
            if(!isIn) current_sum = 0;
            if(input[i]>=0)    {
                isIn = true;
                current_sum = current_sum+input[i];
            }    else if(previous>=0 && max<current_sum)    {
                max = current_sum;
                isIn = false;
            }
            previous = input[i];
        }
        return max;
    }

Rotate an Array

    public int[] rotate(int count, int... input)    {
        for(int i=0; i&lt;count; i++)    {
            input = rotate(input);
        }
        return input;
    }
    private int[] rotate(int... input)    {
        int s =  input.length-1;
        int[] output = new int[input.length];
        for(int j=0; j < s; j++)    {
            output[j+1]=input[j];
        }
        output[0]=input[s];
        return output;
    }