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;
    }
}
//--------------------------------------------------------------------------------------------