Sort an array having 0,1,2 without counting

1.Use 3 pointers low,mid & hi.
2.low will point to first element from left which is not 0
3. hi will point to first element from right which is not 2
4.low will not point to 2, except when low==mid
5.mid will move from 0 to hi and if it is 2, moves it to hi
and if it is 1 moves it to low.


public int[] group012(int[]arr)
{
int low=0,mid=0,hi=arr.length-1,temp=0;

while(mid<=hi)
{


switch(arr[mid])
{
case 0:
arr[mid++]=arr[low];
arr[low++]=0;
break;
case 1:
mid++;
break;
case 2:
arr[mid]=arr[hi];
arr[hi--]=2;
}

}

return arr;
}

To find nth element from the end in a linked list

Use two pointers.
Start the second pointer when the first pointer reaches nth element.

Middle of a linked list in one traversal

Problem

       Find the middle element of a linked list, with just one traversal.


Solution.

Use 1 slow pointer and one fast pointer.
When the fast pointer reaches the end,
slow pointer will be at the middle

Sieve of Eratosthenes

To find all the prime numbers less than or equal to a given integer n:
1. Create a list of consecutive integers from two to n: (2, 3, 4, ..., n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, count up by p and cross out thus found numbers in the list (which will be 2p,
3p, 4p, etc.).
4. Find the first number not yet crossed out after p; let p now equal this number (which is the
next prime).
5. Repeat steps 3 and 4 until p is greater than n.
All the numbers in the list which are not crossed out are prime.

Queue using Stack

Enqueue():
Pop() all elements from StackA to StackB one by one - O(n)
Push() new element in StackA, so it stays at the bottom- O(1).
Pop() all elements from StackB back to StackA - O(n)
So, enqueue is O(n).


Dequeue():
Just Pop().
O(1)

Find the inorder successor of all nodes

Store the nodes to an array.
For each element, tne next element is the inorder successor.

All possible bracket combinations

How can we generate all possibilities on braces ?
N value has given to us and we have to generate all possibilities.
**Examples:**
1) if N == 1, then only one possibility () .
2) if N==2, then possibilities are (()), ()()
3) if N==3, then possibilities are ((())), (())(),()()(), ()(()) ...
Note: left and right braces should match. I mean )( is INVALID for the N==1


The below recursion tree shows the flow:

public static void allValidBrackets(int n, int open, int closed, String str) {

if (closed == n) {
System.out.println(str);
return;
}

if (open < n) {
allValidBrackets(n, open+1, closed, str + "{");
}

if (closed < open) {
allValidBrackets(n, open, closed+1, str + "}");
}
}

Cycle detection in a directed graph

Next smaller in array

For each number, find the next smaller number in the array. If next smaller number does not exists, put 0.
Eg.
Input:   1  5 7 6 3 1  6  2  9  2 7
Output: 0 3  6 3 1 0  2  0  2  0 0

Path in binary tree

There is a binary tree(Not a BST) in which you are given three nodes x,y,z .Write a function which finds whether y lies in the path b/w x
and z.
Assume z is a descedant of x, then y need to satisfy two conditions:
(1) y need to be ancester of z
(2) y need to be descendant of x

Determine all non concentric palindromes in a String

In m"ala"yalam  is a non-concentric palindrome where as malayalam, alayala, aya are concentric palindromes.




Solution:
    For each i in the string
    Find the largest palindrome having i as the center

Finding pairs

Two integer arrays, write a function to get pairs of number
Ex:
input: [2,5,6,8,10,2,3,5] & [4,7,3,5,2,10,2,4] output:[2,2,3,5,10]
input: [2,2,2,3,4,5,6,7] & [2,2,5,5,7,10] output: [2,2,5,7]


Sol.
1. Sort the smaller array.
2. Use a pointer on the unsorted array to search from beginng to end.

Pairing

Give an unsorted array of integers A and and an integer I, find out if any two members of A add up to I.

For example:
A = < 3, 25, 9, 15>
I = 12 returns true
but I = 19 returns false.

Can you find the answer in O(n*log(n)) time?
Can you find the answer in O(n) time?

O(n):
-Create array B by subtracting A[i] from I for each i
-If B[i] exists in A return true.

Deleting current node in a singly linked list

Given a singly linked list with a pointer p pointing to some node(not the first or last node), how will you delete that node? You have no access to the head of the node

Solution:

Copy next node to current node and delete next node

Merge Array

Two sorted arrays A[X] and B[Y+X]. in B array contains Y sorted elements and B can accommodate A[] X elements.

W.A.P to Merge two arrays and store resultant in B[] array.



Solution:
Merge A and B from back to front

Tree Mirror Image

Check if the left subtree is a mirror image of the right subtree.

Solution 1:
Do an inorder traversal. If result is a pallindrom then symmetric else not symmetric

Solution 2:
A solution that may work is - Preorder is reverse to its postorder

most frequent character

Given an array of characters (not sorted), how do you find the most frequent character?

Given a binary search tree find the its least depth.

LRU implementation

Use a Doubly Linked list + Hashtable, similar to the implementation of LinkedHAshMap in Java.
The Hash table will point to a node in the linked list.
Every time a page block, n,  is accessed,
  Go to the hashtable with n
  Get the node pointer
  Bring that node to the head of the doubly linked list

Find out the first non-repeating character in a given input string

Use a count sort based approach.

Check if a number is power of 2

public boolean isPowerOf2(int num)
{
if((num&(num-1))==0 && num>0)
return true;
else
return false;
}

Pairing

Given an array of size 2N, such that its elements are as follows:

{a1,a2,a3,...,an,b1,b2,b3...,bn}

You have to rearrange this array, without using any extra array such that resulting array would be:

{a1,b1,a2,b2,...,an,bn}


1. Swap a2,b1 ;  a4,b3...so that pairs  a1b1,a3b3,a2b2,a4b4 are created.
2. Now swap the pairs a3b3 with a2b2

Count leaf and non-leaf

Using recursion return the number of leaf nodes and non leaf nodes from a single method without any global variables for a given BST?

reverse pair of elements in a linked list

Lowest common ancestor in binary tree

Given a binary search tree and 2 values find the lowest common ancestor. 


The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2). So just traverse the BST in pre-order, if you find a node with value in between n1 and n2 then n is the LCA, if it's value is greater than both n1 and n2 then our LCA lies on left side of the node, if it's value is smaller than both n1 and n2 then LCA lies on right side

Find kth largest integer from an unsorted array of integers. Provide O(n) algorithm

Merge two sorted linked lists

Stack - getMin() in O(1)

Use two stacks, s1 and s2.
Push: Always push in s2, push in s1 too if value is less than top.
Pop:Pop from s2, if popped value is equal to top of s1, pop from s1 too.
Min: Top of s1.

Write A Program to Remove Duplicates from BST

Find the hight of a tree

Recursive solution:


Termination condition : treenode==null


1. Find the height of left subtree
2. Find the height of the right sub tree


if height of left subtree is larger
height=height of left subtree +1
else
height=height of right subtree +1

Integer Palindrome

given an integer. Check whether its binary equivalent is a palindrome or not

Find Gap

Given an unsorted array of numbers. Find if the array consists of consecutive numbers after sorting. Do this in linear time.

Example 1: If array has 5,2,3,1,4
after sorting we get 1,2,3,4,5 which represents consecutive numbers

Counter Example:
If the array has 34,23,52,12,3 after sorting we get 3,12,23,34,52 which are not consecutive

Find first n sorted elements

Describe an algorithm to find the largest 1 million numbers in 1 billion numbers. Assume
that the computer memory can hold all one billion numbers

Swap children of a tree

write a program that implements a function Swap_Tree() that takes a binary tree and swaps left and the right children of every node .

Median of a stream

Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.

Write code to check whether given tree is BST or not

Write code to check whether given tree is BST or not. Time O(n) and space O(1)

Copy Doubly Linked List

The head pointer of a doubly linked list points to a random node.
Copy the DLL by traversal the nodes just once.

Binary Search

public int binarySearch(int[]a,int key)
{
int low,mid,high;

low=0;
high=a.length;
mid=high/2;

while(low<=high) { if(a[mid]>key)
{
high=mid-1;
mid=(low+high)/2;
}
else if(a[mid] {
low=mid+1;
mid=(low+high)/2;
}
else
return mid;
}

return -1;


}

Searching in an Up Down Array

There is an array and the distance between any two consequent
elements is one(+1 or -1) and given a number. You have to check whether the
number is in array or not with minimum complexity

Missing and Duplicated

I have a array which has numbers from 1 to n one number is missing and one number is duplicated. find those in O(n)

Recursion to iteration

/recursive
void f()
{
if(cond == false)
return;
f();
g();
}
//iterative


public void iterative_f() {
int count = 0;
while (cond == false)
{
count++;
}

while(count > 0)
{
g();
count--;
}

Find an element in a partially rotated sorted array in O(log n)

O(1) Insert, delete and Get

Design a Data Structure with following operations
1.Insert(X) -> insert X if X not present
2.Delete(X) -> delete X if X present
3.Get() -> return any element if it is present
all operations in O(1).
No memory constraint.

Use an array, which has size equal to the maximum size of the key

Find the k-th Smallest Element in the Union of Two Sorted Arrays in (logn)

resource lock

Given an n-ary tree of resources arranged hierarchically. A process needs to lock a resource node in order to use it. But a node cannot be locked if any of its descendant or ancestor is locked. You are supposed to:
-> write the structure of node
-> write codes for
* Islock()- returns true if a given node is locked and false if it is not
* Lock()- locks the given node if possible and updates lock information
* Unlock()- unlocks the node and updates information.
Codes should be :
* Islock –O(1)
* Lock()- O(log n)
* unLock()- O(log n)

Check if Anagram

How do you determine to strings are anagram.

Keep an integer array of size 26.
Go through the first string and increment the array location corresponding to the character.
Go through the second string and decrement the array location corresponding to the character.
At the end, if the array contains any non-zero element, then the strings are not anagrams.

Minimum Distance in an array

Given an unsorted array and two numbers, find the minimum distance between them. For example, if the array is {1,2, 10, 2, 3, 5, 2, 1, 5} distance between 2 and 5 is 1.

Given an infix expression convert into postfix

Given a doubly linked list with just 3 numbers 0,1,2 . Sort it

1) Take 2 pointers at starting and at the end of list.
2) traverse list blindly push all the 2s at end of list.---> O(n)
3) move end pointer just before first two and sort normally by two pointer trick in O(n)

Zig Zag Order To Doubly linked list

Given a binary tree,convert into a doubly linked list,The list must be as if the tree is traversed in zig-zag order from top to botton.. (left to right in one level and right to level in the next)

Minimum number of Coins

You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount

Implement a double linked list with only one pointer

Use XOR

Common Ancestor

How to find the common ancestor of two nodes in a binary tree

mplement a function that, given a linked list that may be circular, swaps the first two elements, the third with the fourth, etc

Check if String is a number

Write a method that takes a string, and returns true if that string is a number

Recursive function for reversing linked list

Java program to reverse a number

Write a program to reverse a number. For example if 3652 is the input, the output should be 2563.

Java program for Breadth First Search of a Binary Tree

The below program uses Binary Search Tree implementation
and Queue implementation

public void BFS()
{
Queue queue=new Queue();
Processable info;
TreeNode temp,temp1;

if(root!=null)
{
queue.enqueue(root);
}

while(true)
{
if(queue.isEmpty())
break;

temp=(TreeNode)queue.dequeue();
info=(Processable)temp.data;
info.process();

temp1=temp.left;
if(temp1!=null)
queue.enqueue(temp1);
temp1=temp.right;
if(temp1!=null)
queue.enqueue(temp1);

}


}

MergeSort - Java Program

public int[] mergeSort(int[] arr,int start,int end)
{
int mid=(start+end)/2;

if(start {
mergeSort(arr,start,mid);
mergeSort(arr,mid+1,end);
merge(arr,start,mid,end);
}

return arr;
}

//To merge two sorted portions of an array
public int[] merge(int[]arr,int low,int mid,int end)
{
int[] temp=new int[end-low+1];

int ptr1=low,ptr2=mid+1,ptr3=0;

//Copy the elements in sorted order to a third array - O(n)
while(ptr1<=mid && ptr2<=end )
{
if(arr[ptr1] {
temp[ptr3]=arr[ptr1];
ptr1++;
ptr3++;
}
else if(arr[ptr2]<=arr[ptr1] && ptr2<=end )
{
temp[ptr3]=arr[ptr2];
ptr2++;
ptr3++;
}
}

//Copy remaining elements from first half
while(ptr1<=mid)
{ temp[ptr3]=arr[ptr1];
ptr1++;
ptr3++;
}

//Copy remaining elements from second half
while(ptr2<=end)
{ temp[ptr3]=arr[ptr2];
ptr2++;
ptr3++;
}


//Copy the sorted temp array back to the main array -O(n)
for(int i=low,j=0;i<=end;i++)
arr[i]=temp[j++];


return arr;
}

Java program to implement QuickSort

Java program to find the middle of a linked list in O(n) time

Method:
. Use two pointers in a loop
. One pointer will jump one node, where as the other pointer will jump 2 nodes.
. When the fast pointer reaches the end, the slow pointer will be at the middle.

To find if a linked list has a loop

Problem: Suppose the last node in the linked list point back to any of the previous nodes, creating a loop. How will you detect this?


Use 2 pointers that traverses the list with different speed. For example, at each step, pointer1 will jump one node and pointer2 will jump 2 nodes.

Start both pointers from head.

ptr1=head.next;
ptr2=head.next.next;


Now that ptr2 has already marched ahead of ptr1, there's no chance these two pointers will point to the same node, unless there's a loop.


      

To find the intersection of two linked list

1) Get count of the nodes in first list, let count be c1.
2) Get count of the nodes in second list, let count be c2.
3) Get the difference of counts d = abs(c1 – c2)
4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
5) Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)

Java Program to implement Min Heap

package lab.heaps;

public class MinHeap
{
  int MAX_SIZE=100;
  int last_position; //last position which is empty
  Comparable[] heap=new Comparable[MAX_SIZE];
  //left child:2n+1, Right child: 2n+2
 
  public MinHeap()
  {
 last_position=0;
  }
 
  public void insert(Object o)
  {
    Comparable data=(Comparable)o;
    Comparable temp;
    int i=last_position;
    last_position++;
    heap[i]=data;
    int parent_i=getParentPosition(i);
  
    if(parent_i==-1)
    { // No more checks needed for first insertion, so return
     return;
    }
  
    while(heap[parent_i].compareTo(heap[i])>0)
    {
     temp=heap[i];
     heap[i]=heap[parent_i];
     heap[parent_i]=temp;
     i=parent_i;
     parent_i=getParentPosition(i);
     if(parent_i==-1)
        {//To avoid array out of bound exception
         return;
        }
    
    }
  
   }
 
  public Object deleteMin()
  {
 Object temp1=heap[0];
 Comparable temp;

 if(last_position==0)
 {
 return null;
 }
 else if(last_position==1)
 {
     heap[0]=null;
     return temp1;
 }

 int i=last_position-1;
 heap[0]=heap[i];
 heap[i]=null;
 i=0;

// If there exists a smaller child for i, then get it.
 int next=getSmallerChild(i);

 while(next!=-1)
 {  
// Go down the heap until you have no smaller child
 temp=heap[i];
 heap[i]=heap[next];
 heap[next]=temp;
 i=next;
 next=getSmallerChild(i);
 }

 last_position--;
 return temp1;
 
  }
 
  public Object getMin()
  {
 return heap[0];
  }
 
  public int getLeftChildPosition(int i)
  {
  return (2*i)+1;
  }
 
  public int getRightChildPosition(int i)
  {
  return (2*i)+2;
  }

  public int getParentPosition(int i)
  {
 if(i==0)
 {
 return -1;
 }
 else if(i%2!=0)
 {
 return (i/2);
 }
 else
 {
 return (i/2)-1;
 }
 
  }
 
  public int getSmallerChild(int i)
  {
//Returns the index of the smaller child, if any of the children are smaller
int left=getLeftChildPosition(i);
int right=getRightChildPosition(i);

if(heap[left]==null && heap[right]==null)
{
return -1;
}
else if(heap[left]!=null && heap[right]==null)
{
if(heap[left].compareTo(heap[i])<0)
   return left;
else
return -1;
}
else if(heap[left]!=null && heap[right]!=null)
{
if(heap[left].compareTo(heap[right])<0 && heap[left].compareTo(heap[i])<0)
{
return left;
}
else if(heap[left].compareTo(heap[right])>0 && heap[right].compareTo(heap[i])<0)
{
return right;
}
else
{
return -1;
}
}

return -1;

  }


}

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);

}

}

Java program to implement Binary Search Tree

A very generic Binary Search Tree implementation in Java


package lab.tree;

import lab.general.Processable;


public class Tree {

public TreeNode root;

public Tree()
{
root=null;
}

public void insert(Object info)
{

Comparable compdata;

compdata=(Comparable)info;

TreeNode newnode=new TreeNode();
newnode.data=info;



if(root==null)
{
root=newnode;
root.left=null;
root.right=null;
return;

}

TreeNode tmpnode;
tmpnode=root;
while(tmpnode!=null)
{
if((compdata.compareTo(tmpnode.data))<0 )
{
if(tmpnode.left==null)
{
tmpnode.left=newnode;
return;
}
else
{
tmpnode=tmpnode.left;
}

}
else
{
if(tmpnode.right==null)
{
tmpnode.right=newnode;
return;
}
else
{
tmpnode=tmpnode.right;
}
}
}
}




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

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

 
}

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

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

  
}


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

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

 
}







}

Stack Implementation - Java Program

A Java implementation of stack using Linked List. It uses Linked List which can be found here.




package lab.stack;

import lab.linkedlist.*;

public class Stack 
{

LinkedList stackList;

public Stack()
{
stackList=new LinkedList();
stackList.headnode=null;

}

public void push(Object data)
{

    stackList.insertBegining(data);

}

public Object pop()
{
return stackList.getFirstinList();
}

}

Queue implementation - Java program

A Java implementation of Queue is given below. The implementation uses LinkedList  which can be found here.


package lab.queue;

import lab.linkedlist.*;

public class Queue {

private LinkedList queuelist;

public Queue()
{
queuelist=null;
}


public void enqueue(Object info)
{

  if(queuelist==null)
   {
queuelist=new LinkedList();
queuelist.insertEnd(info);
   }
  else
  {
queuelist.insertEnd(info);
  }

}

public Object dequeue()
{

if(queuelist==null)
{
return null;
}
else
{
Object tmp=new Object();
tmp=queuelist.getFirstinList();
queuelist.deleteFirstInList();
return tmp;
}

}


}

Linked List implementation - Java program

Java implementation of the Linked List  is given below.





package lab.linkedlist;



public class LinkedList
{


public ListNode headnode;
public ListNode currentNode;
public ListNode lastnode;


public LinkedList()
{
headnode=null;  
currentNode=null;
lastnode=null;
}


public void insertBegining(Object info)
{
ListNode tmpnode=new ListNode();
tmpnode.data=info;
if(headnode==null)
{
tmpnode.nextnode=null;
lastnode=tmpnode;
}
else
{
tmpnode.nextnode=headnode;
}
headnode=tmpnode;
}






public Object getFirstinList()
{
if (headnode!=null)
{
return headnode.data;
}
else
{
return null;
}
}




public void deleteFirstInList()
{
if(headnode!=null)
{
headnode=headnode.nextnode;
}
else
{
return;
}

}


public Object getNextNode()
{
ListNode temp=currentNode;
if(currentNode==null)
{return null;}
else{
currentNode=currentNode.nextnode;
     return temp.data ;
   }
}

public void startIterator()
{
currentNode=headnode;
}


public void insertEnd(Object info)
{
ListNode tmpnode=new ListNode();
tmpnode.data=info;
if(headnode==null)
{
headnode=tmpnode;
}
else
{
lastnode.nextnode=tmpnode;
}
tmpnode.nextnode=null;
lastnode=tmpnode;
}


}





package lab.general;


public class Node {


public Object data;

public Node(Object dat){
data=dat;
               }


public Node()
{
data=null;
}
}

package lab.linkedlist;

import lab.general.Node;

public class ListNode extends Node {

ListNode nextnode;

}