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.