Print all sub-set of a given set

    public HashSet<HashSet<Integer>> getAllSubset(HashSet<Integer> set)    {
        int[] superSet = getHashToIntArray(set);
        double max = Math.pow(2, superSet.length);
        HashSet<HashSet<Integer>> result = new HashSet<HashSet<Integer>>();
        for(int i=1; i<=max; i++)    {
            int n=i;
            HashSet<Integer> subset = new HashSet<Integer>();
            for(int j=0; j<superSet.length; j++)    {
                if(n%2==1)
                    subset.add(superSet[j]);
                n=n/2;
            }
            result.add(subset);
        }
        return result;
    }
   
    private int[] getHashToIntArray(HashSet<Integer> set)    {
        int[] result = new int[set.size()];
        int i=0;
        for(Integer n: set)    {
            result[i]=n;
            i++;
        }
        return result;
    }

Convert Numeric to Binary

With Recursion: 
    public StringBuffer convertToBinary(int n)    {
        if (n<2) return new StringBuffer().append(n);
        return new StringBuffer().insert(0, n%2).insert(0, convertToBinary(n/2));
    }

Without Recursion:
    public String convertToBinary(int n)    {
        StringBuffer result = new StringBuffer();
        while(n>0)    {
            result.insert(0, n%2);
            n=n/2;
        }
        return result.toString();
    }

Reversing Parts of a LinkedList

Initial LinkedList: 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 

Input: count = 3
Output: 3, 2, 1, 6, 5, 4, 9, 8, 7, 0, 

Input: count = 4
Output: 4, 3, 2, 1, 8, 7, 6, 5, 0, 9,

Input: count = 7
Output: 7, 6, 5, 4, 3, 2, 1, 0, 9, 8,


    public void compute(int count)    {
        LinkedList L = this;
        int i=0;
        StringBuffer sb = new StringBuffer();
        Stack<Integer> S = new Stack<Integer>();
        while(L!=null)    {
            if(i<count)    {
                S.push(L.data);
                L=L.next;
                i++;
            }    else    {
                while(!S.isEmpty())
                    sb.append(S.pop()).append(", ");
                i=0;
            }
        }
        while(!S.isEmpty())
            sb.append(S.pop()).append(", ");
        System.out.println(sb.toString());
    }

Inserting an Array of Elements in a Linked List

    public void insert(int... data)    {
        LinkedList L = this;
        while(L.next!=null)    {
            L=L.next;
        }
        int size=data.length;
        for(int i=0; i<size; i++)    {
            L.next=new LinkedList(data[i]);
            L=L.next;
        }
    }

Get All SubArray of a given Array

    public ArrayList<ArrayList<Integer>> getAllSubArray(int[] a)    {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        for(int subarray_size=1; subarray_size<a.length; subarray_size++)    {
            ArrayList<Integer> newList = new ArrayList<Integer>();
            for(int i=0; i<a.length; i++)    {
                if((subarray_size+i)>a.length-1)
                    break;
                newList.add(a[i+subarray_size]);
                result.add(new ArrayList<>(newList));
            }
        }
        return result;
    }

Find if a Tree is a Mirror copy of another Tree

    public boolean isMirrorTrees(BinaryTree T1, BinaryTree T2)    {
        if(T1==null && T2==null)
            return true;
        if(T1.data!=T2.data)
            return false;
        if((T1==null && T2!=null) || (T2==null && T1!=null))
            return false;
        if(isMirrorTrees(T1.left, T2.right)
                && isMirrorTrees(T2.left, T1.right))
            return true;
        return false;
    }

Create a Mirror Copy of a Binary Tree

    public BinaryTree MirorCopyOfTree(BinaryTree T)    {
        BinaryTree newTree = new BinaryTree(T.data);
        if(T.left!=null)
            newTree.right=MirorCopyOfTree(T.left);
        if(T.right!=null)
            newTree.left=MirorCopyOfTree(T.right);
        return newTree;
    }

get Root to given Node path in a Binary Tree

    public void rootToNode(int data)    {
        getRootToNodePath(this, data, new StringBuffer(), false);
    }
    private void getRootToNodePath(BinarySearchTree T, int data, StringBuffer sb, boolean isFound)    {
        if(T!=null && !isFound)    {
            sb.append(T.data).append(", ");
            if(T.data==data)    {
                System.out.println(sb.toString());
                isFound = true;
                return;
            }    else    {
                getRootToNodePath(T.left, data, new StringBuffer(sb), isFound);
                getRootToNodePath(T.right, data, new StringBuffer(sb), isFound);
            }
        }
    }

Check if two Binary Tree are same

    public boolean isTreesSame(BinaryTree T1, BinaryTree T2)    {
        if(T1==null && T2==null)
            return true;
        if(T1==null || T2==null)
            return false;
        if(T1.data==T2.data
                && isTreesSame(T1.left, T2.left)
                && isTreesSame(T1.right, T2.right))
            return true;
        return false;
    }

Delete Node from Binary Search Tree

// Binary Search Tree full program is available here: link

    private BinarySearchTree ParentNode; //Parent Node of the node to delete

    private boolean LeftOrRightFlag; //Deleting node is Left from parent means true, else Right means false

    public void DeleteNode(int data)    {
        DeleteNode(this, data);
    }
    private void DeleteNode(BinarySearchTree T, int data)    {
        if(T==null) return;
        if(data==T.data)    {    //delete root note
            T.data=getMin(T.right).data;
            DeleteNode(T.right, T.data);
        }    else    {
            BinarySearchTree Current = findNode(T, data);
            if(Current.left==null && Current.right==null)
                if(LeftOrRightFlag)
                    ParentNode.left=null;
                else
                    ParentNode.right=null;
            else if(Current.left==null)
                if(LeftOrRightFlag)
                    ParentNode.left=Current.right;
                else
                    ParentNode.right=Current.right;
            else if(Current.right==null)
                if(LeftOrRightFlag)
                    ParentNode.left=Current.left;
                else
                    ParentNode.right=Current.left;
            else    {//Current node has both children
                Current.data=getMin(Current.right).data;
                DeleteNode(T.right, Current.data);
            }
        }
    }

    private BinarySearchTree getMin(BinarySearchTree T)    {
        while(T.left!=null)
            T=T.left;
        return T;
    }

    public BinarySearchTree findNode(BinarySearchTree T,int data)    {    //except root
        if(data==T.data)
            return T;
        else if(data<T.data)    {
            ParentNode=T;
            LeftOrRightFlag=true;
            return findNode(T.left, data);
        }    else    {
            ParentNode=T;
            LeftOrRightFlag=false;
            return findNode(T.right, data);
        }
    }

get InOrder sucessor of a given node in a BST

    private Stack<BinarySearchTree> S;
    public int inOrderSuccessor(int data)    {
        S = new Stack<BinarySearchTree>();
        BinarySearchTree Current = getNode(this, data);
        if(Current.right!=null)    {
            return getMin(Current.right).data;
        }    else    {
            BinarySearchTree parent = S.pop();
            if(parent.left==Current)
                return parent.data;
            else
                return S.pop().data;
        }
    }
    private BinarySearchTree getMin(BinarySearchTree T)    {
        while(T.left!=null)
            T=T.left;
        return T;
    }
    private BinarySearchTree getNode(BinarySearchTree T, int data)    {
        if(T==null)    return null;
        else if(data==T.data)        {
            return T;
        }
        else if(data<T.data) {
            S.add(T);
            return getNode(T.left, data);
        }
        else {
            S.add(T);
            return getNode(T.right, data);
        }
    }

is Binary Tree a Binary Search Tree

    public boolean isBinarySearchTree()    {
        return isBinaryTree(this, (-10^23), 10^23);
    }
    private boolean isBinarySearchTree(BinaryTree T, int min, int max)    {
        if(T==null) return true;
        if(T.data>min && T.data<max
                && isBinaryTree(T.left, min, T.data)
                && isBinaryTree(T.right, T.data, max))
            return true;
        return false;
    }

Insert Sorted Array into a Binary Search Tree with minimum height

public class BinarySearchTree {
    BinarySearchTree left, right;
    int data;
    public BinarySearchTree(int... SortedArrayOfdata) {
        int mid=SortedArrayOfdata.length/2;
        this.left=null;
        this.right=null;
        this.data=SortedArrayOfdata[mid];
        insertSortedArray(SortedArrayOfdata, 0, mid-1);
        insertSortedArray(SortedArrayOfdata, mid+1, SortedArrayOfdata.length-1);
    }
    private void insertSortedArray(int[] a, int startIndex, int endIndex)    {
        if(startIndex<=endIndex)    {
            int mid=(startIndex+endIndex)/2;
            insert(a[mid]); //Insert method is available here: link
            insertSortedArray(a, startIndex, mid-1);
            insertSortedArray(a, mid+1, endIndex);
        }
    }
}

Example Input:
BinarySearchTree BST = new BinarySearchTree(0,1,2,3,4,5,6,7,8,9,10,11,12,13);

Quick Sort

import java.util.Random;

public class QuickSort {
    int[] a;
    public QuickSort(int[] a) {
        this.a = a;
    }
    public int[] QSort()    {
        QSort(this.a, 0, this.a.length-1);
        return a;
    }
    private void QSort(int[] a, int startIndex, int endIndex)    {
        if(startIndex<endIndex)    {
            int PartionIndex = RandomizedPartition(startIndex, endIndex);
            QSort(a, startIndex, PartionIndex-1);
            QSort(a, PartionIndex+1, endIndex);
        }
    }
    private int RandomizedPartition(int startIndex, int endIndex)    {
        /* Worst Case of QuickSort is O(n^2)
        The possibility for WorstCase in QuickSort is very low
        RandomizedPartition will help reducing the probability of the occurrence of worst case*/
        int PivotIndex=new Random().nextInt(endIndex-startIndex)+startIndex;
        swap(PivotIndex, endIndex);
        return Partition(startIndex, endIndex);
    }
    private int Partition(int startIndex, int endIndex)    {
        int Pivot=a[endIndex];
        int PivotIndex=startIndex;
        for(int i=startIndex; i<endIndex; i++)    {
            if(a[i]<=Pivot)    {
                swap(i, PivotIndex);
                PivotIndex++;
            }
        }
        swap(PivotIndex, endIndex);
        return PivotIndex;
    }
    private void swap(int IndexA, int IndexB)    {
        int temp=a[IndexA];
        a[IndexA]=a[IndexB];
        a[IndexB]=temp;
    }
}

Selection Sort

    public int[] SelectionSort(int[] a)    {
        for(int i=0; i<a.length; i++)    {
            int min=i;
            for(int j=i+1; j<a.length; j++)    {
                if(a[j]<=a[min])
                    min=j;
            }
            int temp=a[i];
            a[i]=a[min];
            a[min]=temp;
        }
        return a;
    }

Insertion Sort

    public int[] InsertionSort(int[] input)    {
        for(int i=1; i<input.length; i++)    {
            int val=input[i];
            int hole=i;
            while(hole>0 && val<input[hole-1])    {
                input[hole]=input[hole-1];
                hole--;
            }
            input[hole]=val;
        }
        return input;
    }

Swap Two Integers without Temporary Variable

    public static void DoSwaping(int a, int b)    {
        a=a+b;
        b=a-b;
        a=a-b;
        System.out.println("a: "+a+"\nb: "+b);
    }
    public static void main(String[] args) {
        DoSwaping(5, 9); // Example Input
    }

Bubble Sort

    public int[] BubbleSort(int[] input)    {
        int size=input.length;
        for(int i=0; i<size; i++)    {
            boolean flag = true;
            int s=size-i-1;
            for(int j=0; j<s; j++)    {
                if(input[j]>=input[j+1])    {
                    flag=false;
                    input[j] = input[j]+input[j+1];
                    input[j+1] = input[j]-input[j+1];
                    input[j] = input[j]-input[j+1];
                }
            }
            if(flag) break;
        }
        return input;
    }

Merge Sort

    public int[] MergeSort(int[] a)    {
        int mid = a.length/2;
        if(mid<1)    return a;
        int[] left = new int[mid];
        int i=0;
        for(; i<left.length; i++)
            left[i]=a[i];
        left = MergeSort(left);
        int[] right = new int[(a.length%2==1)?(mid+1):mid];
        for(int j=0; j<right.length; j++)    {
            right[j]=a[i];
            i++;
        }
        right = MergeSort(right);
        return Merge(left, right);
    }
    private int[] Merge(int[] left, int[] right)    {
        int i, j, k;    i=j=k=0;
        int[] merged = new int[left.length+right.length];
        while(i<left.length && j<right.length)    {
            if(left[i]<=right[j])    {
                merged[k]=left[i];
                i++;
            }    else if(left[i]>right[j])    {
                merged[k]=right[j];
                j++;
            }
            k++;
        }
        while(i<left.length)    {
            merged[k]=left[i];
            i++; k++;
        }
        while(j<right.length)    {
            merged[k]=right[j];
            j++; k++;
        }
        return merged;
    }

Chess Knight Move in Board

public class ChessBoard {
    int[][] Board;
    public ChessBoard() {
        Board = new int[8][8];
        for(int i=0; i<8; i++)
            for(int j=0; j<8; j++)
                Board[i][j]='E';//Empty
    }
    public void KnightMove(int x, int y)    {
        if(x>-1 && x<8 && y>-1 && y<8)
            Board[x][y]='K';//Knight
        else    {
            System.out.println("Error: Not valid Points");
            return;
        }
        int a=x+2;int b=y+1;
        if(a>-1 && a<8 && b>-1 && b<8)
            Board[a][b]='T';//Threten
        System.out.println(a+" "+b);
        a=x+2;b=y-1;
        if(a>-1 && a<8 && b>-1 && b<8)
            Board[a][b]='T';//Threten
        a=x-2;b=y+1;
        if(a>-1 && a<8 && b>-1 && b<8)
            Board[a][b]='T';//Threten
        a=x-2;b=y-1;
        if(a>-1 && a<8 && b>-1 && b<8)
            Board[a][b]='T';//Threten
        a=x+1;b=y+2;
        if(a>-1 && a<8 && b>-1 && b<8)
            Board[a][b]='T';//Threten
        a=x-1;b=y+2;
        if(a>-1 && a<8 && b>-1 && b<8)
            Board[a][b]='T';//Threten
        a=x+1;b=y-2;
        if(a>-1 && a<8 && b>-1 && b<8)
            Board[a][b]='T';//Threten
        a=x-1;b=y-2;
        if(a>-1 && a<8 && b>-1 && b<8)
            Board[a][b]='T';//Threten
        printBoard();
    }
    public void printBoard()    {
        for(int i=0; i<8; i++)    {
            StringBuffer sb = new StringBuffer();
            for(int j=0; j<8; j++)
                sb.append((char)Board[i][j]).append(", ");
            System.out.println(sb.toString());
        }
    }
}

Make all diagonal to 0 when encountered a 0

Given a 2D array, write a method MakeDiagonalZeroWhenEncounteredZero() to convert all diagonal to zero when encountered a zero.

import java.util.ArrayList;

public class ChessBoard {
    public int[][] Board;
    public ChessBoard(int fill) { //Pass 1 for fill
        this.Board = new int[8][8];
        for(int i=0; i<8; i++)
            for(int j=0; j<8; j++)
                this.Board[i][j]=fill;
    }
    public void FillZero(int x, int y)    {
        if(x<8 && x>-1 && y<8 && y>-1)
            Board[x][y]=0;
        else
            System.out.println("Error: Possition Not Valid");
    }
    public void MakeDiagonalZeroWhenEncounteredZero()    {
        ArrayList<Coordinates> zeros = getZeroCordinates();
        for(Coordinates c: zeros)    {
            int x=c.getX();
            int y=c.getY();
            while(x<7 && y<7)    {
                x++; y++;
                Board[x][y]=0;
            }
            x=c.getX();    y=c.getY();
            while(x>0 && y>0)    {
                x--; y--;
                Board[x][y]=0;
            }
            x=c.getX();    y=c.getY();
            while(x<7 && y>0)    {
                x++; y--;
                Board[x][y]=0;
            }
            x=c.getX();    y=c.getY();
            while(x>0 && y<7)    {
                x--; y++;
                Board[x][y]=0;
            }
        }
    }
    private ArrayList<Coordinates> getZeroCordinates()    {
        ArrayList<Coordinates> zeros = new ArrayList<Coordinates>();
        for(int i=0; i<8; i++)
            for(int j=0; j<8; j++)    {
                if(Board[i][j]==0)
                    zeros.add(new Coordinates(i,j));
            }
        return zeros;
    }
    public void PrintBoard()    {
        for(int i=0; i<8; i++)    {
            StringBuffer sb = new StringBuffer();
            for(int j=0; j<8; j++)    {
                sb.append(Board[i][j]).append(", ");
            }
            System.out.println(sb.toString());
        }
    }
}
class Coordinates    {
    private int x, y;
    public Coordinates(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int getX() {
        return x;
    }
    public int getY() {
        return y;
    }
}




Main Method:
        ChessBoard cb = new ChessBoard(1);
        cb.FillZero(4, 5);
        cb.FillZero(7, 2);
        System.out.println("Input: ");
        cb.PrintBoard();
        cb.MakeDiagonalZeroWhenEncounteredZero();
        System.out.println("Output: ");
        cb.PrintBoard();
   
Input:
1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 0, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 0, 1, 1, 1, 1, 1,
Output:
1, 0, 1, 1, 1, 1, 1, 1,
1, 1, 0, 1, 1, 1, 1, 1,
1, 1, 1, 0, 1, 1, 1, 0,
1, 1, 1, 1, 0, 1, 0, 1,
1, 1, 1, 1, 1, 0, 1, 1,
0, 1, 1, 1, 0, 1, 0, 1,
1, 0, 1, 0, 1, 1, 1, 0,
1, 1, 0, 1, 1, 1, 1, 1,

Stack Implementation using two Queues

import java.util.LinkedList;
import java.util.Queue;

public class Stack {
    Queue<Integer> Q1,Q2;
    public Stack() {
        Q1=new LinkedList<Integer>();
        Q2=new LinkedList<Integer>();
    }
    public void push(int data)    {
        Q1.add(data);
    }
    public int peek()    {
        int size=Q1.size()-1;
        for(int i=0; i<size;i++)
            Q2.add(Q1.remove());
        int peek = Q1.remove();
        Q2.add(peek);
        SwapQueues();
        return peek;
    }
    public int pop()    {
        int size=Q1.size()-1;
        for(int i=0; i<size;i++)
            Q2.add(Q1.remove());
        int pop = Q1.remove();
        SwapQueues();
        return pop;
    }
    private void SwapQueues()    {
        Queue<Integer> temp = Q1;
        Q1=Q2;
        Q2=temp;
    }
}

Queue Implementation using Two Stacks

import java.util.Stack;

public class Queue {
    Stack<Integer> S1;
    Stack<Integer> S2;
    public Queue() {
        S1 = new Stack<Integer>();
        S2 = new Stack<Integer>();
    }
    public void enqueue(int data)    {
        S1.push(data);
    }
    private void ShiftS1toS2()    {
        while(!S1.isEmpty())
            S2.push(S1.pop());
    }
    public int dequeue()    {
        ShiftS1toS2();
        return S2.pop();
    }
    public int lookup()    {
        ShiftS1toS2();
        return S2.peek();
    }
}

Sort a Stack using one additional Stack

    public Stack<Integer> SortStack(Stack<Integer> input)    {
        if(input.isEmpty())    return input;
        Stack<Integer> buffer = new Stack<Integer>(); //Buffer Stack
        while(!input.isEmpty())    {
            int temp = input.pop();
            if(!buffer.isEmpty() && temp<buffer.peek())
                input.push(buffer.pop());
            buffer.push(temp);
        }
        return buffer;
    }


This Code doesn't work all the time
Input: [5, 7, 8, 9, 6, 0, 2]
Output: [0, 2, 6, 8, 7, 5, 9]

Finding nth Fibonacci number

    public int getFibonacci(int n)    {
        if(n<=1)    return 1;
        int fibonace=0;
        int f1=0;
        int f2=1;
        for(int i=1; i<n; i++)    {
            fibonace=f1+f2;
            f1=f2;
            f2=fibonace;
        }
        return fibonace;
    }

Find Factorial of a Number

// Recursive approach
    public int getFactorialRecursive(int n)    {
        if(n==0)    return 1;
        else
            return n * getFactorial(n-1);
    }

// Non Recursive approach
    public int getFactorial(int n)    {
        int factorial=1;
        if(n==0) return factorial;
        while(n!=0)    {
            factorial=factorial*n;
            n--;
        }
        return factorial;
    }

Find Index of an element in a Circularly Sorted Array

input=Find 3 in {6,7,8,9,0,1,2,3,4,5};
output=7

    public int FindIndexCircularArray(int element, int[] input)    {
        int high = input.length-1;
        int low = 0;
        while(low<=high)    {
            int mid=(high+low)/2;
            if(element==input[mid])
                return mid;
            else if(input[low]<=input[mid])    {
                //left array is sorted
                if(element>=input[low] && element<input[mid])
                    high=mid-1;
                else    low=mid+1;
            }    else if(input[mid]<=input[high])    {
                //right array is sorted
                if(element>input[mid] && element<=input[high])
                    low=mid+1;
                else    high=mid-1;
            }
        }
        return -1;
    }

Starting Element of a Rotated Array using Binary Search

Sample Input: 
input={6,7,8,9,0,1,2,3,4,5};
output=4
input={0,1,2,3,4,5,6,7,8,9};
output=0

    public int FindStartIndex(int[] input)    {
        int high = input.length-1;
        int low = 0;
        while(low<high)    {
            if(input[low]<=input[high])
                return low;
            int mid=(high+low)/2;
            if(input[mid]<input[mid+1] && input[mid]<input[mid-1])
                return mid;
            else if(input[mid]>input[low])    {
                //left array is sorted
                //start index is not in left
                low=mid+1;
            }    else if(input[mid]<input[high])    {
                //right array is sorted
                //start index is not in right
                high=mid-1;
            }
        }
        return -1;
    }

Count the number of occurrence of an element in an array using Binary Search

    public int FindNumberOfOccurancesInArray(int element, int[] input)    {
        int first=BinarySearchFindIndex(element, input, true);
        if(first==-1)//Doesn't have the element
            return 0;
        else    {
            int second=BinarySearchFindIndex(element, input, false);
            System.out.println(first+" "+second);
            return second-first+1;
        }
    }

This is a module to perform Binary Search
if firstElement = true -> Binary Search returns first occurrence of an element
if firstElement = false -> Binary Search returns last occurrence of an element

    public int BinarySearchFindIndex(int element, int[] input, boolean firstElement)    {
         int high = input.length;
        int low = 0;
        int result =-1;
        while(low<=high)    {
            int mid = low + ((high-low)/2);
            if(element==input[mid])    {
                result = mid;
                if(firstElement)
                    high=mid-1;
                else
                    low=mid+1;
            }    else if(element<input[mid])    {
                high=mid-1;
            }    else if(element>input[mid])    {
                low=mid+1;
            }
        }
        return result;
    }

Check if Parentheses are Balanced

import java.util.Stack;

class Parenthesis    {
    public boolean isParenthesisCorrect(String s)    {
        char[] c = s.toCharArray();
        int size=c.length;
        Stack S = new Stack<Character>();
        boolean flag = true;
        for(int i=0; i<size; i++)    {
            if(c[i]=='(')
                S.push(c[i]);
            else if(c[i]==')')    {
                if(!((Character)S.pop()=='('))    {
                    flag=false;
                    break;
                }
            }
        }
        if(!S.isEmpty())
            flag=false;
        return flag;
    }
}

public class Main {
    public static void main(String[] args) {
        Parenthesis P = new Parenthesis();
        String s = "((a+b)*(a-b))/c";
        System.out.println(P.isParenthesisCorrect(s));
    }
}

Implementing 3 fixed size Stacks using same Array

public class ThreeStacks {
    int ArraySize;
    int[] Array;
    int[] topPointers =  {-1,-1,-1};
    public ThreeStacks(int size) {
        this.ArraySize = size;
        this.Array = new int[size * 3];
    }
    public int peek(int StackNumber)    {
        if(topPointers[StackNumber-1]>-1)    {
            return Array[(ArraySize*StackNumber)+topPointers[StackNumber]];
        }    else    {
            System.out.println("Error: "+StackNumber+" is empty");
            return ErrorCode;
        }
    }
    public static final int ErrorCode = -999;
    public int pop(int StackNumber)    {
        StackNumber--;
        if(topPointers[StackNumber]>-1)    {
            int ret = Array[(ArraySize*StackNumber)+topPointers[StackNumber]];
            topPointers[StackNumber]--;
            return ret;
        }    else    {
            System.out.println("Error: "+StackNumber+" is empty");
            return ErrorCode;
        }
    }
    public void push(int data, int StackNumber)    {
        int maxSize = (ArraySize*StackNumber)-1;
        if(topPointers[StackNumber-1]<maxSize)    {
            topPointers[StackNumber-1]++;
            int nextLoc = (ArraySize*(StackNumber-1))+topPointers[StackNumber-1];
            Array[nextLoc]=data;
        }    else    {
            System.out.println("Stack "+StackNumber+" is full");
        }
    }
    public void print3Stacks()    {
        StringBuffer sb =new StringBuffer();
        for(int i=0; i<=topPointers[0]; i++)    {
            sb.append(Array[i]);
        }
        System.out.println(sb.toString());
        sb =new StringBuffer();
        for(int i=ArraySize; i<=ArraySize+topPointers[1]; i++)    {
            sb.append(Array[i]);
        }
        System.out.println(sb.toString());
        sb =new StringBuffer();
        for(int i=(ArraySize*2); i<=(ArraySize*2)+topPointers[2]; i++)    {
            sb.append(Array[i]);
        }
        System.out.println(sb.toString());
    }
}

Create and Detect Loop in Linked List

The Linked List program is available here: link

     public boolean isLoopExist()    {
        LinkedList L = this;
        LinkedList slow = L;
        LinkedList fast = L;
        boolean isLoop = false;
        while(fast.next!=null)    {
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast)    {
                isLoop = true;
                break;
            }
        }
        return isLoop;
    }
    public void createLoop(int index)    {
        LinkedList L = this;
        for(int i=2; i<index; i++)    {
            L=L.next;
        }
        LinkedList indexPrevNode = L;
        while(L.next!=null)    {
            L=L.next;
        }
        L.next=indexPrevNode.next;
    }

Stack Implementation using Linked List

This is a Stack Implementation using LinkedList in Java. As in Java we don't have pointers and hard to remove head node in a empty list, we are using a dummy head node.

public class Stack {
    Stack next;
    int data;
    private int size;
    public Stack() {
        this.size=-1;
        this.data=-999; //Garbage Value to denote Head
        this.next=null;
    }
    public Stack(int data) {
        this.data=data;
        this.next=null;
    }
    public void push(int... data)    {
        int s = data.length;
        for(int i=0; i<s; i++)
            push(data[i]);
    }
    public void push(int data)    {
        Stack S = this;
        if(size==-1)    {
            S.next=new Stack(data);
        }    else    {
            Stack newNode = new Stack(data);
            newNode.next=S.next; //Head is a dummy node here
            S.next=newNode;
        }
        size++;
    }
    public final static int ErrorCode = -999;
    public int pop()    {
        Stack S = this;
        if(size>-1)    {
            int value = S.next.data;
            S.next=S.next.next;
            size--;
            return value;
        }    else    {
            System.out.println("Error: Stack is Empty");
            return ErrorCode;
        }
    }
    public int size()    {
        return size;
    }
    public int peek()    {
        Stack S = this;
        if(size>-1)    {
            return S.next.data;
        }    else    {
            System.out.println("Error: Stack is Empty");
            return ErrorCode;
        }
    }
    public void printStack()    {
        Stack S = this;
        S=S.next; // first node is dummy
        StringBuffer sb = new StringBuffer();
        while(S!=null)    {
            sb.append(S.data).append(", ");
            S=S.next;
        }
        System.out.println(sb.toString());
    }
}

Stack implementation using Array

public class Stack {
    int[] array;
    private int top;
    private int size;
    public Stack(int size) {
        this.size=size;
        array = new int[size];
        top = -1;
    }
    public void push (int... data)    {
        int size = data.length;
        for(int i=0; i<size; i++)
            push(data[i]);
    }
    public void push (int data)    {
        if (top<size-1)    {
            top++;
            array[top]=data;
        }
    }
    public final static int ErrorCode = -999;
    public int pop()    {
        if(!isEmpty())    {
            int a = array[top];
            top--;
            return a;
        }    else return ErrorCode;
    }
    public int peek()    {
        return array[top];
    }
    public boolean isEmpty()    {
        if(top<0) return true;
        else    return false;
    }
    public void printArray()    {
        int size = top+1;
        StringBuffer sb = new StringBuffer();
        for(int i=0; i<size; i++)
            sb.append(array[i]).append(", ");
        System.out.println(sb.toString());   
    }
}

LinkedList print kth to last element

This module returns kth to last element of a Linked List

    public String kthLastElement(int k)    {
        LinkedList L = this;
        for(int i=1; i<k; i++)    {
            L=L.next;
        }
        StringBuffer sb = new StringBuffer();
        while(L!=null)    {
            sb.append(L.data).append(", ");
            L=L.next;
        }
        return sb.toString();
    }

Check if a LinkedList is a Palindrome

Input:
LinkedList L = new LinkedList("HeleH");
L.printList();
System.out.println(L.isPalindrome());

Program:
import java.util.Stack;

public class LinkedList {
    int data;
    LinkedList next;
    private LinkedList(int data) {
        this.data=data;
        this.next=null;
    }
    public LinkedList(String data) {
        char[] a = data.toCharArray();
        int size=a.length;
        if(size>0)    {
            this.data=a[0];
            this.next=null;
            for(int i=1; i<size; i++)
                append(a[i]);
        }
    }
    public boolean isPalindrome()    {
        LinkedList L = this;
        Stack<Integer> S=new Stack<Integer>();
        LinkedList slow = L;
        LinkedList fast = L;
        while(fast!=null && fast.next!=null)    {
            S.push(slow.data);
            fast = fast.next.next;
            slow = slow.next;
        }
        boolean flag = true;
        if(fast!=null) //String has odd number of char
            slow = slow.next;
        while(slow!=null)    {
            if(slow.data!=S.pop())    {
                flag=false;
                break;
            }
            slow = slow.next;
        }
        return flag;
    }
    public void append(int data)    {
        LinkedList L = this;
        while(L.next!=null)
            L=L.next;
        L.next=new LinkedList(data);
    }
    public void printList()    {
        LinkedList L = this;
        StringBuffer sb = new StringBuffer();
        while(L!=null)    {
            sb.append((char)L.data);
            L=L.next;
        }
        System.out.println("String: "+sb.toString());
    }
}

This program also shows how to use an integer data linked list to store characters.

Reverse a Single Linked List in Java using Recursion

You can refer for Linked List in Java program here: link

This is a program to reverse a linked list using recursion.
    public String reverseList()    {
        return reverseList(this, new StringBuffer()).toString();
    }
    private StringBuffer reverseList(LinkedList L, StringBuffer sb)    {
        if(L!=null)    {
            reverseList(L.next, sb);
            sb.append(L.data).append(", ");
        }
        return sb;
    }

Amazon Interview Question

The Question is this: 
      6
    /  \
   3    5
  / \     \
 2   5    4
    / \
   7  4
There are 4 leaves, hence 4 root to leaf paths:
   Path           Sum
6->3->2           632
6->3->5->7       6357
6->3->5->4       6354
6->5>4            654  
Expected Answer: 632+6357+6354+654=13997 

The Program is this:


public class Main {
    public static void main(String[] args) {
        BinaryTree T = new BinaryTree(6);
        T.specialInsert();
        int answer = new AddLinkedListContnents().addLinkedLists(T.rootToLeaf());
        System.out.println("answer="+answer);
    }
}

//--------------------------------------------------------------------------------------------
import java.util.ArrayList;

public class BinaryTree {
    BinaryTree left, right;
    int data;
    public BinaryTree(int data) {
        this.data=data;
        this.left=null;
        this.right=null;
    }
    public void specialInsert()    {
        /*   6
            /  \
           3    5
          / \     \
         2   5    4
            / \
           7  4        */
        BinaryTree T = this;
        T.left=new BinaryTree(3);
        T.left.left=new BinaryTree(2);
        T.left.right=new BinaryTree(5);
        T.left.right.left=new BinaryTree(7);
        T.left.right.right=new BinaryTree(4);
        T.right=new BinaryTree(5);
        T.right.right=new BinaryTree(4);
    }
    private ArrayList<LinkedList> ArrList;
    public ArrayList<LinkedList> rootToLeaf()    {
        ArrList=new ArrayList<LinkedList>();
        rootToLead(this, new ArrayList<Integer>());
        for(LinkedList L:ArrList)    {
            L.printList();
        }
        return ArrList;
    }
    private void rootToLead(BinaryTree T, ArrayList<Integer> path)    {
        if(T!=null)    {
            path.add(T.data);
            if(T.left==null && T.right==null)    {
                ArrList.add(new LinkedList(path));
            }    else    {
                rootToLead(T.left, new ArrayList<>(path));
                rootToLead(T.right, new ArrayList<>(path));
            }
        }
    }
}

//--------------------------------------------------------------------------------------------
import java.util.ArrayList;
import java.util.Collections;

public class LinkedList {
    LinkedList next;
    int data;
    private int size;
    public LinkedList(int data) {
        this.data=data;
        this.next=null;
        this.size++;
    }
    public LinkedList(ArrayList<Integer> values) {
        Collections.reverse(values);
        //Inserts Values in reverse
        this.data=values.get(0);
        this.next=null;
        this.size++;
        insert(values);
    }
    private void insert(ArrayList<Integer> values) {
        int size = values.size();
        if(size>0)    {
            LinkedList L = this;
            for(int i=1; i<size; i++)    {
                L.next=new LinkedList(values.get(i));
                L=L.next;
                this.size++;
            }
        }
    }
    public void insert(int data)    {
        LinkedList L = this;
        while(L!=null)
            L=L.next;
        L.next=new LinkedList(data);
        this.size++;
    }
    public void printList()    {
        LinkedList L = this;
        StringBuffer sb = new StringBuffer();
        while(L!=null)    {
            sb.append(L.data).append(", ");
            L=L.next;
        }
        System.out.println(sb.toString());
    }
    public int getSize() {
        return size;
    }
    /*public void setSize(int size) {
        this.size = size;
    }*/
}

//--------------------------------------------------------------------------------------------
import java.util.ArrayList;

public class AddLinkedListContnents {
    public int addLinkedLists(ArrayList<LinkedList> ALs)    {
        int LargestArraySize=FindLargestArraySize(ALs);
        int carry = 0;
        StringBuffer sb = new StringBuffer();
        for(int i=0; i<LargestArraySize; i++)    {           
            int current_sum = carry;
            int size = ALs.size();
            for(int j=0; j<size; j++)    {
                if(ALs.get(j)!=null)    {               
                    current_sum=current_sum+ALs.get(j).data;
                    ALs.set(j, ALs.get(j).next);
                }
            }
            carry=current_sum/10;
            current_sum=current_sum%10;
            sb.append(current_sum);
            current_sum=0;
        }
        sb.append(carry);
        return Integer.parseInt(sb.reverse().toString());
    }
    private int FindLargestArraySize(ArrayList<LinkedList> ALs)    {
        int size=0;
        for(LinkedList L:ALs)    {
            if(size<L.getSize())
                size=L.getSize();
        }
        return size;
    }
}
//--------------------------------------------------------------------------------------------