Java program for Descending order traversal of binary search tree

public void descendingOrder(TreeNode rootnode)
{
if(rootnode !=null)
{
Processable info;


descendingOrder(rootnode.right);
info=(Processable)rootnode.data;
info.process();
descendingOrder(rootnode.left);
}
}

Java program for Non recursive tree traversal using stack

public void inorderNonRecursive(TreeNode rootnode)
{
Stack stack =new Stack();
Processable info;
TreeNode temp;
temp=rootnode;

while(true)
{
while(temp!=null)
{
stack.push(temp);
temp=temp.left;
}
if(stack.isEmpty())
break;
temp=(TreeNode)stack.pop();
info=(Processable)temp.data;
info.process();
temp=temp.right;

}


}

Java program to Convert each level of a binary tree into a linked list and store the list pointers in an array

Q. Create a linked list to hold each level of the binary tree. Then store the linked list headers in an array.

Algorithm.
1. Create a linked list array as an instance variable.
2. Create a preorder traversal like recursive function.
3. The function takes the level as a parameter and increments it before
passing it to the next recursive call.
4. Add the root element to the linked list stored at listarray[level].
5. make a recursive call with the left subtree and right subtree.

A working Java implementation is given below.



package lab.tree;

import lab.linkedlist.*;

public class SpecialTree extends Tree {

LinkedList[] listarray=new LinkedList[100];


public void treeToListArray(TreeNode rootnode,int level)
{
if(rootnode !=null)
{

if (listarray[level]==null)
{
LinkedList tmplist=new LinkedList();
tmplist.insertBegining(rootnode.data);
listarray[level]= tmplist;
level++;
}
else
{
listarray[level].insertBegining(rootnode.data);
level++;
}

treeToListArray(rootnode.left,level);
treeToListArray(rootnode.right,level);
}

}

Java program to count the number of bits that are set in an integer

public int setBitCount(int n)
{
//Count the number of bits which are 1

int count=0;

while(n!=0)
{
if((n&1)>0)
{
count++;
}
n=n>>>1;
}
return count;

}

Java program to Find duplicate elements in an array

public void findDuplicatesInArray()
{
// Find duplicate elements in an array O(n)

Hashtable hashtable=new Hashtable();
int [] inputA={1,2,2,3,4,5,5,6,7};

for(int i=0;i<9;i++)
{
if(hashtable.put(inputA[i], inputA[i])!=null)
{
System.out.println("Duplicate:"+inputA[i]);
}
}



}

Java program to Find the intersection of two arrays

public void arrayIntersection()
{
//To find the intersection of 2 arrays
HashSet hashsetA = new HashSet();
HashSet hashsetB = new HashSet();
int[] inputA={1,2,3,4,5,6,7,8,9,10};
int[] inputB={5,6,5,12,13,14};

for(int i=0;i<10;i++) { hashsetA.add(inputA[i]); } for(int i=0;i<5;i++) { hashsetB.add(inputB[i]); } Iterator iterator;
iterator=hashsetB.iterator();

int i;
while(iterator.hasNext())
{
i=iterator.next();
if(hashsetA.contains(i))
{
System.out.println(i);
}
}

}

Java program to Shuffle a pack of 52 cards

Solution :
For every i, card at a random location is placed at i
and card that was at i is placed at j.

If we want every card to change its previous location -
For every i,
Generate a random location >i and which is not same as i


public void shuffle()
{
int[] cards =new int[52];

Random random =new Random();

random.setSeed(new Date().getTime());

for(int i=0,j=0;i<52;i++,j++)
{
cards[i]=j;
System.out.println(j);
}

for(int i=0,j=0,t=0,k=0;i<52;i++)
{
//For every i, card at a random location is placed at i
//and card that was at i is placed at j
j=random.nextInt(52);
t=cards[j];
cards[j]=cards[i];
cards[i]=t;
}

for(int i=0;i<52;i++)
{
System.out.println(cards[i] + ", "+i);
}

}

Java program to find Reverse Factorial

public int reverseFactorial(int fact)
{
int sum=1;
int i=1;
while(sum {
i++;

sum=sum*i;
}

if(sum==fact)
{
return i;
}
else
{
return -1;
}


}

Java program to De duplicate array in O(n) time

public int[] deduplicate(int[] numbers,int N)
{
//Number from 1 to N are stored in an array of size N
//De-duplicate the array without using extra space.
//Algo should be O(n)
int val=0;

for(int i=1;i<=N;i++) { val=Math.abs(numbers[i]); //The fact that a number X appeared once - is represented by //changing the sign of the value at arr[X]. //So if arr[X] is -ve that means X is duplicate. if(numbers[val]>0)
numbers[val]=numbers[val]*-1;
else
{
numbers[i]=N+1;
}


}
return numbers;

}

Java program to calculates x^m in O(log m) time

public int logpower(int x,int m)
{
//Calculates x^m in O(log m) time

if(m==1)
return x;
else if(m%2!=0)
return logpower(x,m/2)*logpower(x,m/2)*x;
else
return logpower(x,m/2)*logpower(x,m/2);
}

Java program to find if a number is divisible by 3 without using / or % operator

public boolean isDivisibleBy3(int num)
{
//Find if a number is divisible by 3 without using / or % operator

int sum=0;
String strnum=(new Integer(num)).toString();
if(num<10){ sum=num; } while(strnum.length()>=2)
{
sum=0;
for(int i=0;i<strnum.length();i++)
{
sum=sum+ Integer.parseInt(strnum.substring(i,i+1));
}
if(sum>=10)
{
strnum=(new Integer(sum)).toString();
}
else
{
break;
}

}

if(sum==3 || sum==6 || sum==9)
{
return true;
}
else
{
return false;
}
}

Java program to get Nth element from the end of a linked list

Algorithm:
1.Use two pointers.
2.Traverse the list from begining.
3.Start the second pointer only when the first pointer reaches Nth element.

Java implementation:

public Object getNthFromLast(int n)
{
 if(n<1)  return null;
 if(n>nodeCount)
 return null;
 ListNode temp1,temp2;
 temp1=this.headnode;
 temp2=this.headnode;
 int i=1;
 while(i<n) 
{
i++;
temp1=temp1.nextnode;
 }

 while(temp1.nextnode!=null)
 {
temp1=temp1.nextnode;
temp2=temp2.nextnode;
 }

 return temp2.data;

}

Java program to build NL Tree from preorder traversal

There exists a special kind of tree which has the node value 'N' if it is an internal node
and 'L' if it is a leaf node. An internal node can have either 0 or 2 children, not 1. Build the tree from preorder traversal.

The algorithm works based on the concept that number of leaf nodes=number of internal nodes+1.
(This is true only if internal node can have either 0 or 2 children, not 1).

Count from the beginning of the preorder array and when number of internal nodes==number of leaf node, that means, it is the end of the left subtree.
Now recursively call the routine with the sub array containing the left subtree and with the
sub array containing the right subtree.
Finally join the left subtree and the right subtree with the root.


public TreeNode buildNLTree(char[] preorder)
{
int length_p=preorder.length;
if(length_p<1 )
{
//Wrong input
return null;
}

if(length_p==1)
{ //Stop condition for the recursion;
TreeNode node=new TreeNode();
node.left=null;
node.right=null;
node.data=preorder[0];
return node;
}

int n_count=0,l_count=0;
int pos_right_sub_tree=0;

for(int i=0;i<length_p;i++)
{
if(preorder[i]=='N')
n_count++;
else
l_count++;

if(n_count==l_count)
{
pos_right_sub_tree=i+1;
break;
}
}

char[] newpreorder_left=new char[pos_right_sub_tree-1];
char[] newpreorder_right=new char[length_p-pos_right_sub_tree];

System.arraycopy(preorder, 1, newpreorder_left, 0, pos_right_sub_tree-1);
System.arraycopy(preorder, pos_right_sub_tree, newpreorder_right, 0, length_p-pos_right_sub_tree);

TreeNode treeroot=new TreeNode();
treeroot.data=preorder[0];

TreeNode leftsubtree=buildNLTree(newpreorder_left);
TreeNode rightsubtree=buildNLTree(newpreorder_right);

treeroot.left=leftsubtree;
treeroot.right=rightsubtree;

return treeroot;
}

Java program to build binary tree from preorder traversal and inorder traversal

public TreeNode buildTree(int[] preorder,int[] inorder )
{
 int length_p=preorder.length;
 int length_i=inorder.length;

 if(length_p<1 ||length_i<1 )
    {
 //Wrong input
 return null;
    }

 if(length_p==1)
 { //Stop condition for the recursion;
 TreeNode node=new TreeNode();
 node.left=null;
 node.right=null;
 node.data=preorder[0];
 return node;
 }

 int preorder_root_val=preorder[0];
 int inorder_root_pos=0;

 for(int i=0; i<length_i; i++)
 {// Get the position of the root in inorder array
 if(inorder[i]==preorder_root_val)
 {
 inorder_root_pos=i;
 break;
 }
 }

 //Create arrays which will hold the traversals of
 //left and right subtrees
 int[] newinorder_left=new int[inorder_root_pos];
      int[] newpreorder_left=new int[inorder_root_pos];
 int[] newinorder_right=new int[length_i-inorder_root_pos-1];
      int[] newpreorder_right=new int[length_i-inorder_root_pos-1];

      //Fill the arrays that hold the subtree traversals
 System.arraycopy(inorder, 0, newinorder_left, 0, inorder_root_pos);
 System.arraycopy(preorder, 1, newpreorder_left, 0, inorder_root_pos);
 System.arraycopy(inorder, inorder_root_pos+1, newinorder_right, 0, length_i-inorder_root_pos-1);
 System.arraycopy(preorder, inorder_root_pos+1, newpreorder_right, 0, length_i-inorder_root_pos-1);

 //Create the root Node
 TreeNode treeroot=new TreeNode();
 treeroot.data=preorder[0];

 //Recursive call to buildTree with subtree traversals
 TreeNode leftsubtree=buildTree(newpreorder_left,newinorder_left);
 TreeNode rightsubtree=buildTree(newpreorder_right,newinorder_right);

 //Join the subtrees with the root
 treeroot.left=leftsubtree;
 treeroot.right=rightsubtree;

 //Return the created tree;
 return treeroot;

}

Java program to convert a binary tree to a doubly linked list, in place

Algorithm :
The problem can be solved recursively.
1. Convert the left subtree into a doubly linked list
2. Convert the right subtree into doubly linked list
3. root.left= the rightmost node of the left subtree in the doubly linked list
4. root.right=the leftmost node of the right subtree in the doubly linked list
5 return root.
At the end of recursion, from the main routine, traverse to the leftmost node
which gives the headnode of the doubly linked list.


public TreeNode treeToDoublyLinkedList(TreeNode root)
{
// Converts a tree to doubly linked list, in place


if(root==null)
{//Stop condition for recursion
// If the tree is null, resulting DLL is also null
return null;
}

TreeNode leftsubtree=treeToDoublyLinkedList(root.left);
TreeNode rightsubtree=treeToDoublyLinkedList(root.right);

if(leftsubtree!=null)
{
 while(leftsubtree.right!=null)
  {
leftsubtree=leftsubtree.right;
   }
   leftsubtree.right=root;
}
    root.left=leftsubtree;

  
if(rightsubtree!=null)
{
 while(rightsubtree.left!=null)
  {
 rightsubtree=rightsubtree.left;
   }
   rightsubtree.left=root;
}
root.right=rightsubtree;

return root;

}

Java program to check if a Linked List is a palindrome

Algorithm:
1. Find the length of the list.
2. Reverse the list from the middle.
3.Compare the lists
4.Reverse the second half again and join back.

Java Program:

public boolean isPalindrome()
{
int len=getLength(); //gets the length of the list
int mid=(len/2)+1;
ListNode temp=headnode;
int i=1;
while(i<mid)
{
temp=temp.nextnode;
i++;
}

ListNode newlisthead=temp.nextnode;
ListNode middlenode=temp;

ListNode temp1,temp2,temp3;

temp1=newlisthead;
temp2=newlisthead.nextnode;
temp3=null;
newlisthead.nextnode=null;
while(temp2.nextnode!=null)
{
temp3=temp2.nextnode;
temp2.nextnode=temp1;
temp1=temp2;
temp2=temp3;
}
temp2.nextnode=temp1;
newlisthead=temp2;
ListNode lastnode=newlisthead;  
// Start comparison

temp1=headnode;
temp2=newlisthead;

boolean palindrome=true;

while(temp2!=null)
{
Comparable dat1=(Comparable)temp1.data;
if(dat1.compareTo(temp2.data)!=0)
{
temp1=newlisthead;
temp2=newlisthead.nextnode;
temp3=null;
newlisthead.nextnode=null;
while(temp2.nextnode!=null)
{
temp3=temp2.nextnode;
temp2.nextnode=temp1;
temp1=temp2;
temp2=temp3;
}
temp2.nextnode=temp1;

newlisthead=temp2;
middlenode.nextnode=newlisthead;
lastnode.nextnode=null;
return false;
}

else
{
temp1=temp1.nextnode;
temp2=temp2.nextnode;
}
}

temp1=newlisthead;
temp2=newlisthead.nextnode;
temp3=null;
newlisthead.nextnode=null;
while(temp2.nextnode!=null)
{
temp3=temp2.nextnode;
temp2.nextnode=temp1;
temp1=temp2;
temp2=temp3;
}
temp2.nextnode=temp1;

newlisthead=temp2;
middlenode.nextnode=newlisthead;
lastnode.nextnode=null;
return true;


}

Java program to Reverse Linked List

public void reverseList()
{
ListNode temp1,temp2,temp3;

temp1=headnode;
temp2=headnode.nextnode;
temp3=null;
headnode.nextnode=null;
while(temp2.nextnode!=null)
{
temp3=temp2.nextnode;
temp2.nextnode=temp1;
temp1=temp2;
temp2=temp3;
}
temp2.nextnode=temp1;
headnode=temp2;

}

Java program to compare two binary trees

Algorithm:

   1. If roots of boths trees are null, then the trees are same (stopping condition for the recursion).
   2. If
       - the data in the roots are same &
       - the left subtrees are same &
       - the right subtrees are same
        Then the trees are same
    Else
        -trees are not same
        


public boolean compareTree(TreeNode root1,TreeNode root2)
{
if(root1==null && root2==null )
{
return true;
}

Comparable data1,data2;
data1=(Comparable)root1.data;
data2=(Comparable)root2.data;

if(data1.compareTo(data2)==0 && compareTree(root1.left,root2.left)
     && compareTree(root1.right,root2.right))
{
return true;
}
else
return false;


}

Java program for Pattern Matching

public void getMatches(String text_file_string, String match_string )
{
    int n,m;
    n=text_file_string.length();
m=match_string.length();
char[] text_file=new char[n];
text_file_string.getChars(0, n, text_file, 0);
char[] match_str=new char[m];
match_string.getChars(0, m, match_str, 0);
int cntr=0;

for (int i=0,j=0; i<=n-m;i++) {
      cntr++;
if(text_file[i]==match_str[0])


{
if (text_file[i+m-1]==match_str[m-1])
{
for(j=0;j<m;j++ )
{
cntr++;

if(text_file[i+j]!=match_str[j])
break;
}
if(j==m)
{
System.out.println("Mathc found at"+ (i+1));
i=i+m;
}
}
}


}

}

Java program to implement Hash Table

A hash table implementation in Java using separate chaining. It creates a linked list for resolving hash collision.
All keys with the same hashcode "h"  is added to the linked list stored at the index "h".
The time complexity of insertion is O(1), no matter how loaded the hash table is. Time complexity for
retrieval is O(1) when the load factor is less than 1.


package lab.hashing;

import lab.linkedlist.*;

public class HashTable
{
   final int INIT_SIZE=100;
   final int INCREMENT=100;
   int CURRENT_SIZE;
   int LOAD_FACTOR=0;
   LinkedList[] hashtable=new LinkedList[INIT_SIZE];

   public HashTable()
   {
  CURRENT_SIZE=INIT_SIZE;
   }



   public void put(Object key,Object value)
   {
  int index;
  Hashable hashkey=(Hashable)key;
  index=(Math.abs(hashkey.getHashCode()))%CURRENT_SIZE;
  if(hashtable[index]==null)
  {
  LinkedList seperatechain=new LinkedList();
  hashtable[index]=seperatechain;
  seperatechain.insertBegining(value);
  }
  else
  {
  hashtable[index].insertBegining(value);
  }

   }


   public Object get(Object key)
   {
  int index;
  Hashable hashkey=(Hashable)key;
  index=(Math.abs(hashkey.getHashCode()))%CURRENT_SIZE;

  if(hashtable[index]==null)
  {
  return null;
  }
  else
  {
  return hashtable[index].search(key);
  }
   }


}

Java program to simulate Multiple Producer Consumer Problem

The Multiple Producer Consumer Problem can be solved using the Java inter thread communication mechanism.


package lab.thread;

public class Queue {
static int n;
static boolean produced;
public Queue()
{
n=0;
produced=false;
}

synchronized public void get(int id)
{

while(!produced)
{    try{
wait();
      }catch(InterruptedException ie)
      {
     System.out.println("Caught Interrupted exception");
       }
    }
System.out.println("Got "+n +" By Consumer: "+id);
produced=false;
notifyAll();
}

synchronized public void put(int val,int id)
{
while(produced)
{
try{
wait();
}catch(InterruptedException ie)
{
System.out.println("Caught Interrupted exception");
}
      
}
n=val;
System.out.println("Put : "+n+ " By Producer: "+id);
produced=true;
notifyAll();
}


}





package lab.thread;

public class Producer extends Thread {

Queue q;
int id;
static int p=1;

public Producer(Queue qu,int sn)
{
q=qu;
id=sn;
this.start();
}

public void run()
{

while(p<100)
{
q.put(p++,id);

}
}


}





package lab.thread;

public class Consumer implements Runnable
{
Queue q;
int id;

public Consumer(Queue qu,int sn)
{
q=qu;
id=sn;
new Thread(this,"Consumer").start();
}

public void run()
{

while(true)
{
q.get(id);

}
}

}

package lab;

public class Runner 

{

 public static void main(String params[])

{

lab.thread.Queue q=new lab.thread.Queue();

new lab.thread.Producer(q,1);

new lab.thread.Consumer(q,1);

new lab.thread.Producer(q,2);

new lab.thread.Consumer(q,2);

new lab.thread.Consumer(q,3);

}

}