Saturday, 27 December 2014

ConcurrentHashMap in java

ConcurrentHashMap is very similar to HashTable but it provides better concurrency level.
You might know , you can synchonize HashTable using Collections.synchronizedMap(Map). So what is difference between ConcurrentHashMap and Collections.synchronizedMap(Map)

In case of Collections.synchronizedMap(Map), it locks whole HashTable object but in ConcurrentHashMap, it locks only part of it. You will understand it in later part.
Another difference is that ConcurrentHashMap will not throw ConcurrentModification exception if we try to modify ConcurrentHashMap while iterating it.

Lets take a very simple example. I have a Country class, we are going to use Country class object as key and its capital name(string) as value. Below example will help you to understand, how these key value pair will be stored in ConcurrentHashMap.

1. Country.java 
package org.arpit.java2blog;
public class Country {

 String name;
 long population;
 
 public Country(String name, long population) {
  super();
  this.name = name;
  this.population = population;
 }
 public String getName() {
  return name;
 }
 public void setName(String name) {
  this.name = name;
 }
 public long getPopulation() {
  return population;
 }
 public void setPopulation(long population) {
  this.population = population;
 }
@Override
public int hashCode() {
	final int prime = 31;
	int result = 1;
	result = prime * result + ((name == null) ? 0 : name.hashCode());
	return result;
}
@Override
 public boolean equals(Object obj) {
  
  Country other = (Country) obj;
   if (name.equalsIgnoreCase((other.name)))
   return true;
  return false;
 }
  
}

2. ConcurrentHashMapStructure.java(main class)

import java.util.HashMap;
import java.util.Iterator;
  
public class ConcurrentHashMapStructure {
  
    /**
     * @author Arpit Mandliya
     */
    public static void main(String[] args) {
          
        Country india=new Country("India",1000);
        Country japan=new Country("Japan",10000);
          
        Country france=new Country("France",2000);
        Country russia=new Country("Russia",20000);
          
        ConcurrentHashMap<country,String> countryCapitalMap=new ConcurrentHashMap<country,String>();
        countryCapitalMap.put(india,"Delhi");
        countryCapitalMap.put(japan,"Tokyo");
        countryCapitalMap.put(france,"Paris");
        countryCapitalMap.put(russia,"Moscow");
          
        Iterator<country> countryCapitalIter=countryCapitalMap.keySet().iterator();//put debug point at this line
        while(countryCapitalIter.hasNext())
        {
            Country countryObj=countryCapitalIter.next();
            String capital=countryCapitalMap.get(countryObj);
            System.out.println(countryObj.getName()+"----"+capital);
            }
        }
  
  
} 
Now put debug point at line 23 and right click on project->debug as-> java application. Program will stop execution at line 23 then right click on countryCapitalMap then select watch.You will be able to see structure as below.

Now From above diagram, you can observe following points
  1. There is an Segment[] array called segments which has size 16. 
  2. It has two more variable called segmentShift and segmentMask.
  3. This segments stores Segment class's object. ConcurrentHashMap class has a inner class called Segment
  4.  /**
         * Segments are specialized versions of hash tables.  This
         * subclasses from ReentrantLock opportunistically, just to
         * simplify some locking and avoid separate construction.
         */
    static final class Segment<K,V> extends ReentrantLock implements Serializable {
     /**
          * The per-segment table.
         */
            transient volatile HashEntry<K,V>[] table;
    // other methods and variables
    } 
Now lets expand segment object present at index 3.



In above diagram, you can see each Segment class contains logically an HashMap.
Here size of table[](Array of HashEntry class) : 2ˆk >= (capacity/number of segments)
It stores a key value pair in a class called HashEntry which is similar to Entry class in HashMap.

static final class HashEntry<K,V> {
        final K key;
        final int hash;
        volatile V value;
        final HashEntry<K,V> next;
}


When we say, ConcurrentHashMap locks only part of it.It actually locks a Segment. So  if two threads are  writing different segments in same ConcurrentHashMap, it allows write operation without any conflicts.

So Segments are only for write operations. In case of read operation, it allows full concurrency and provides most recently updated value using volatile variables.
Now as you understood internal structure of ConcurrentHashMap, it will be easier for you to understand put function.

Concept of ConcurrencyLevel:

While creating a ConcurrentHashMap object, you can pass ConcurrencyLevel in the constructor. ConcurrencyLevel defines"Estimated number of threads going to write to the ConcurrentHashMap". Default ConcurrencyLevel is 16. That is why, we got 16 Segments objects in above created ConcurrentHashMap.
Actual number of Segment will be equal to next power of two defined in ConcurrencyLevel.
For example:
Lets say you have defined ConcurrencyLevel as 5, so 8 Segments object will be created  as 8=2^3 so 3 higher bits of Key will be used to find index of the segment
Another example: You want 10 threads should be able to access ConcurrentHashMap concurrently, so you will define  ConcurrencyLevel as 10 , So 16 Segments will be created as 16=2^4 so 4 higher bits of Key will be used to find index of the segment

put Entry:

Code for putEntry is as follows:
/**
     * Maps the specified key to the specified value in this table.
     * Neither the key nor the value can be null.
     *
     * The value can be retrieved by calling the get method
     * with a key that is equal to the original key.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with key, or
     *         null if there was no mapping for key
     * @throws NullPointerException if the specified key or value is null
     */
    public V put(K key, V value) {
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key.hashCode());
        return segmentFor(hash).put(key, hash, value, false);
    }

 /**
     * Returns the segment that should be used for key with given hash
     * @param hash the hash code for the key
     * @return the segment
     */
    final Segment<k> segmentFor(int hash) {
        return segments[(hash >>> segmentShift) & segmentMask];
    }
 // Put method in Segment:
 V put(K key, int hash, V value, boolean onlyIfAbsent) {
            lock();
            try {
                int c = count;
                if (c++ > threshold) // ensure capacity
                    rehash();
                HashEntry<k>[] tab = table;
                int index = hash & (tab.length - 1);
                HashEntry<k> first = tab[index];
                HashEntry<k> e = first;
                while (e != null && (e.hash != hash || !key.equals(e.key)))
                    e = e.next;

                V oldValue;
                if (e != null) {
                    oldValue = e.value;
                    if (!onlyIfAbsent)
                        e.value = value;
                }
                else {
                    oldValue = null;
                    ++modCount;
                    tab[index] = new HashEntry<k>(key, hash, first, value);
                    count = c; // write-volatile
                }
                return oldValue;
            } finally {
                unlock();
            }
        }



When we add any key value pair to ConcurrentHashMap, following steps take place:
  1. In ConcurrentHashMap, key can not be null. Key's hashCode method is used to calculate hash code
  2. Key 's HashCode method may be poorly written, so java developers have added one more method hash(Similar to HashMap) , another hash() function is applied and hashcode is calculated.
  3. Now we need to find index of segment first, For finding a segment for given key, above SegmentFor method is used.  
  4.  After getting Segment, we use segment's put method.While putting key value pair in Segment, it acquires lock, so no other thread can enter in this block and then it finds index in HashEntry array using hash &(tab.length-1).
  5. If you closely observe, Segment's put method is similar to HashMap's put method.

putIfAbsent:

You want to put element in ConcurrentHashMap only when if it does not have Key already otherwise return old value. This can be written as:
if (map.get(key)==null)

    return map.put(key, value);
else
   return map.get(key);
Above operation is atomic if you use putIfAbsent method. This may be required behaviour. Lets understand with help of an example:
  1. Thread 1 is putting value in ConcurrentHashMap.
  2. At same time, Thread 2 is trying to read(get) value from ConcurrentHashMap and it may return null So it may override whatever thread 1 has put in ConcurrentHashMap.
Above behaviour may not be required so ConcurrentHashMap has putIfAbsent method.

    /*

     * {@inheritDoc}
     *

     * @return the previous value associated with the specified key,

     *         or <tt>null</tt> if there was no mapping for the key

     * @throws NullPointerException if the specified key or value is null
     */

    public V putIfAbsent(K key, V value) {
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key.hashCode());
        return segmentFor(hash).put(key, hash, value, true);

    }

get Entry:

 /**
     * Returns the value to which the specified key is mapped,      * or {@code null} if this map contains no mapping for the key.      *      * <p>More formally, if this map contains a mapping from a key      * {@code k} to a value {@code v} such that {@code key.equals(k)},      * then this method returns {@code v}; otherwise it returns      * {@code null}.  (There can be at most one such mapping.)      *      * @throws NullPointerException if the specified key is null      */     public V get(Object key) {         int hash = hash(key.hashCode());         return segmentFor(hash).get(key, hash);     }  /* Specialized implementations of map methods */ // get method in Segment:         V get(Object key, int hash) {             if (count != 0) { // read-volatile                 HashEntry<K,V> e = getFirst(hash);                 while (e != null) {                     if (e.hash == hash && key.equals(e.key)) {                         V v = e.value;                         if (v != null)                             return v;                         return readValueUnderLock(e); // recheck                     }                     e = e.next;                 }             }             return null;         }
Getting value from ConcurrentHashMap is straight forward.
  1. Calculate hash using key 's Hashcode
  2. Use segmentFor to get index of Segment.
  3. Use Segment's get function to get value corresponding to the key.
  4. If it does not find value in ConcurrentHashMap ,it locks the Segment and tries again to get the value.

Best Practice:

We should not use default constructor of ConcurrentHashMap if we require low level of Concurrency level as default ConcurrencyLevel is 16  and it will create 16 Segments by default.

We should use fully parameterized constructor:
ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel) 
In above constructor, initialCapacity and loadFactor is same as HashMap and concurrencyLevel is same as we have defined above.

So if you require only two threads that can write concurrently, you may initialise ConcurrentHashMap as:
 ConcurrentHashMap ch=new ConcurrentHashMap(16,0.75f,2);

ConcurrentHashMap will perform much better if you have few write threads and large number of read threads.


Monday, 4 August 2014

Binary tree in java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child

Example of binary tree:

I have posted various programs on binary tree so that you can practice them for interviews and it will also help in understanding recursion.

Binary tree traversals:

PreOrder traversal - In PreOrder traversal,each node is processed before either of its sub-trees.In simpler words,Visit each node before its children.

InOrder traversal : In InOrder traversal,each node is processed between subtrees.In simpler words,Visit left subtree, node and then right subtree.

PostOrder traversal: In PostOrder traversal,each node is processed after subtrees traversal.In simpler words,Visit left subtree,  right subtree and then node.

Level order traversal : In Level order traversal, tree is traversed by each level. It is same as breadth first search.

Spiral/Zigzag order traversal : In spiral order traversal, tree is traversed in spiral shape.

Other Binary tree programs:




print all paths from root to leaf in a binary tree in java

In this post, we will see about program to print all paths from root to leaf in a binary tree in java.
Below diagram will show all paths  from root to leaf:

Algorithm:

Steps for print all paths from root to leaf are:
  • If node is null then return 0
  • put node.data in array and increment len by 1.
  • If encounterd leaf node(i.e. node.left is null and node.right is null) then print array.
  • Recursively visit left subtree and right subtree

Code for recursion will be:
// Prints all paths to leaf
 public static void printAllPathsToLeaf(TreeNode node, int[] path, int len) {
     if ( node == null )
         return;

     // storing data in array
     path[len] = node.data;
     len++;

     if(node.left == null && node.right == null) {
         // leaf node is reached
         printArray(path,len);
         return;
     }

     printAllPathsToLeaf(node.left, path, len);
     printAllPathsToLeaf(node.right, path, len);
 }


Lets create java program for counting number of leaf nodes:
 
package org.arpit.java2blog;

public class BinaryTree {

 
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }
 
// Prints all paths to leaf
 public static void printAllPathsToLeaf(TreeNode node, int[] path, int len) {
     if ( node == null )
         return;

     // storing data in array
     path[len] = node.data;
     len++;

     if(node.left == null && node.right == null) {
         // leaf node is reached
         printArray(path,len);
         return;
     }

     printAllPathsToLeaf(node.left, path, len);
     printAllPathsToLeaf(node.right, path, len);
 }

 
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  TreeNode rootNode=createBinaryTree();
  System.out.println("Printing all paths from root to leaf :");
  printAllPathsToLeaf(rootNode,new int[1000],0);
 }
 
 public static TreeNode createBinaryTree()
 {
  
  TreeNode rootNode =new TreeNode(40);
  TreeNode node20=new TreeNode(20);
  TreeNode node10=new TreeNode(10);
  TreeNode node30=new TreeNode(30);
  TreeNode node60=new TreeNode(60);
  TreeNode node50=new TreeNode(50);
  TreeNode node70=new TreeNode(70);
  TreeNode node5=new TreeNode(5);
  TreeNode node55=new TreeNode(55);
  
  rootNode.left=node20;
  rootNode.right=node60;
  
  node20.left=node10;
  node20.right=node30;
  
  node60.left=node50;
  node60.right=node70;
  node10.left=node5;
  node50.right=node55;
  
  return rootNode;
 }
}

Run above program and you will get following output:
 
Printing all paths from root to leaf :
40 20 10 5 
40 20 30 
40 60 50 55 
40 60 70 

Spiral/Zigzag level order traversal of binary tree in java

In this post, we will see about Spiral/Zigzag Level Order binary tree traversal in java.

Spiral/Zigzag Level Order traversal:

 Spiral/Zigzag Level order traversal of below tree will be:


Steps for solution:
  1. Create an empty stack s and push root to it.
  2. while stack is not NULL Do following
    1. Create a empty stack called tempStack.
    2. Pop a node from stack and push it to tempStack depending on directionFlag
    3. Change directionFlag to change the direction of traversal
    4. set stack=tempStack
 
// prints in Spiral/Zigzag level order
 public static void spiralOrZigzagLevelOrder(TreeNode root) {
        if(root==null) return; 
        Stack<TreeNode> stack=new Stack<TreeNode>();
        stack.push(root);
        
        boolean directionflag=false;
        while(!stack.isEmpty())
        {
            Stack<TreeNode> tempStack=new Stack<TreeNode>();
        
            while(!stack.isEmpty())
            {
                TreeNode tempNode=stack.pop();
             System.out.printf("%d ",tempNode.data);
                if(!directionflag) 
                {
                    if(tempNode.left!=null) 
                     tempStack.push(tempNode.left);
                    if(tempNode.right!=null) 
                     tempStack.push(tempNode.right);
                }else
                {
                    if(tempNode.right!=null) 
                     tempStack.push(tempNode.right);
                    if(tempNode.left!=null) 
                     tempStack.push(tempNode.left);
                }
            }
            // for changing direction
            directionflag=!directionflag; 
      
            stack=tempStack; 
        }
     
    }

Example:
Lets say your binary tree is :


So Spiral/Zigzag Level Order traversal will work as below:

Lets create java program for Spiral/Zigzag Level traversal:
 
package org.arpit.java2blog;

import java.util.Queue;
import java.util.LinkedList;
public class BinaryTree {

 
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }
 
// prints spiral/zigzag level order
 public static void spiralOrZigzagLevelOrder(TreeNode root) {
        if(root==null) return; 
        Stack<TreeNode> stack=new Stack<TreeNode>();
        stack.push(root);
        
        boolean directionflag=false;
        while(!stack.isEmpty())
        {
            Stack<TreeNode> tempStack=new Stack<TreeNode>();
        
            while(!stack.isEmpty())
            {
                TreeNode tempNode=stack.pop();
             System.out.printf("%d ",tempNode.data);
                if(!directionflag) 
                {
                    if(tempNode.left!=null) 
                     tempStack.push(tempNode.left);
                    if(tempNode.right!=null) 
                     tempStack.push(tempNode.right);
                }else
                {
                    if(tempNode.right!=null) 
                     tempStack.push(tempNode.right);
                    if(tempNode.left!=null) 
                     tempStack.push(tempNode.left);
                }
            }
            // for changing direction
            directionflag=!directionflag; 
      
            stack=tempStack; 
        }
     
    }
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  TreeNode rootNode=createBinaryTree();
  System.out.println("Spiral/Zigzag traversal of binary tree :");
  spiralOrZigzagLevelOrder(rootNode);
 }
 
 public static TreeNode createBinaryTree()
 {
  
  TreeNode rootNode =new TreeNode(40);
  TreeNode node20=new TreeNode(20);
  TreeNode node10=new TreeNode(10);
  TreeNode node30=new TreeNode(30);
  TreeNode node60=new TreeNode(60);
  TreeNode node50=new TreeNode(50);
  TreeNode node70=new TreeNode(70);
  TreeNode node5=new TreeNode(5);
  TreeNode node55=new TreeNode(55);
  
  rootNode.left=node20;
  rootNode.right=node60;
  
  node20.left=node10;
  node20.right=node30;
  
  node60.left=node50;
  node60.right=node70;
  node10.left=node5;
  node50.right=node55;
  
  return rootNode;
 }
}

Run above program and you will get following output:
 
Spiral/Zigzag traversal of binary tree :
40 60 20 10 30 50 70 55 5 

Sunday, 20 July 2014

program to count leaf nodes in a binary tree in java

In this post, we will see about program to count leaf nodes in a binary tree in java

Algorithm-

Steps for counting number of leaf nodes are:
  • If node is null then return 0
  • If encounterd leaf node(i.e. node.left is null and node.right is null) then return 1.
  • Recursively calculate number of leaf nodes using
  • Number of leaf nodes= number of leaf nodes in left subtree + number of leaf nodes in right sub tree
    

Code for recursion will be:
/* To get the count of leaf nodes in a binary tree*/
 public static  int getLeafCountOfBinaryTree(TreeNode node)
 {
   if(node == null)      
     return 0;
   if(node.left ==null && node.right==null)     
     return 1;           
   else
     return getLeafCountOfBinaryTree(node.left)+ getLeafCountOfBinaryTree(node.right);     
}


Lets create java program for counting number of leaf nodes:
 
package org.arpit.java2blog;

public class BinaryTree {

 
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }
 
 // Recursive Solution
/* To get the count of leaf nodes in a binary tree*/
public static  int getLeafCountOfBinaryTree(TreeNode node)
{
  if(node == null)      
    return 0;
  if(node.left ==null && node.right==null)     
    return 1;           
  else
    return getLeafCountOfBinaryTree(node.left)+ getLeafCountOfBinaryTree(node.right);     
}

 
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  TreeNode rootNode=createBinaryTree();
  System.out.println("Number of leaf nodes in binary tree :"+getLeafCountOfBinaryTree(rootNode));
 }
 
 public static TreeNode createBinaryTree()
 {
  
  TreeNode rootNode =new TreeNode(40);
  TreeNode node20=new TreeNode(20);
  TreeNode node10=new TreeNode(10);
  TreeNode node30=new TreeNode(30);
  TreeNode node60=new TreeNode(60);
  TreeNode node50=new TreeNode(50);
  TreeNode node70=new TreeNode(70);
  
  rootNode.left=node20;
  rootNode.right=node60;
  
  node20.left=node10;
  node20.right=node30;
  
  node60.left=node50;
  node60.right=node70;
  
  return rootNode;
 }
}

Run above program and you will get following output:
 
Number of leaf nodes in binary tree :4

how to print leaf nodes of a binary tree in java

In this post, we will see about program to print leaf nodes in a binary tree in java

Algorithm-

Steps for counting number of leaf nodes are:
  • If node is null then return 0
  • If encounterd leaf node(i.e. node.left is null and node.right is null) then print the node.
  • Recursively visit leaf subtree and right subtree.
Code for recursion will be:
 // print leaf nodes
 public static void printLeafNodes(TreeNode node) {
 
   if(node==null)
    return;
   
   if(node.left == null && node.right == null) {
    System.out.printf("%d ",node.data);
   }
   printLeafNodes(node.left);
   printLeafNodes(node.right);
 }



Example:
Binary tree:

Lets create java program for counting number of leaf nodes:
 
package org.arpit.java2blog;

public class BinaryTree {

 
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }
 
 // Recursive Solution
 // print leaf nodes
 public static void printLeafNodes(TreeNode node) {
 
   if(node==null)
    return;
   
   if(node.left == null && node.right == null) {
    System.out.printf("%d ",node.data);
   }
   printLeafNodes(node.left);
   printLeafNodes(node.right);
 }


 
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  System.out.println("Printing leaf nodes in binary tree :");
  printLeafNodes(rootNode);
 }
 
 public static TreeNode createBinaryTree()
 {
  
 TreeNode rootNode =new TreeNode(40);
 TreeNode node20=new TreeNode(20);
 TreeNode node10=new TreeNode(10);
 TreeNode node30=new TreeNode(30);
 TreeNode node60=new TreeNode(60);
 TreeNode node50=new TreeNode(50);
 TreeNode node70=new TreeNode(70);
  
 TreeNode node5=new TreeNode(5);
 TreeNode node55=new TreeNode(55);

 rootNode.left=node20;
 rootNode.right=node60;

 node20.left=node10;
 node20.right=node30;

 node60.left=node50;
 node60.right=node70;
 
 node10.left=node5;
 node50.right=node55;
 return rootNode;
 }
}

Run above program and you will get following output:
 
Printing leaf nodes in binary tree :
5 30 55 70 

Saturday, 19 July 2014

Binary Tree Level Order traversal in java

In this post, we will see about Level Order binary tree traversal in java.

Level Order traversal:

Level order traversal of below tree will be:



We will use Queue for Level Order traversal.This algorithm is very similar to Breadth first search of graph.
Steps for Level order traversal algorithm:
  1. Create empty queue and pust root node to it.
  2. Do the following when queue is not empty
    • Pop a node from queue and print it
    • Push left child of popped node to queue if not null
    • Push right child of popped node to queue if not null
 
// prints in level order
	public static void levelOrderTraversal(TreeNode startNode) {
		Queue<TreeNode> queue=new LinkedList<TreeNode>();
		queue.add(startNode);
		while(!queue.isEmpty())
		{
			TreeNode tempNode=queue.poll();
			System.out.printf("%d ",tempNode.data);
			if(tempNode.left!=null)
				queue.add(tempNode.left);
			if(tempNode.right!=null)
				queue.add(tempNode.right);
		}
	}

Example:
Lets say your binary tree is :

So Level Order traversal will work as below:

Lets create java program for PreOrder traversal:
 
package org.arpit.java2blog;

import java.util.Queue;
import java.util.LinkedList;
public class BinaryTree {

 
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }
 
// prints in level order
	public static void levelOrderTraversal(TreeNode startNode) {
		Queue<TreeNode> queue=new LinkedList<TreeNode>();
		queue.add(startNode);
	        while(!queue.isEmpty())
		{
			TreeNode tempNode=queue.poll();
			System.out.printf("%d ",tempNode.data);
			if(tempNode.left!=null)
				queue.add(tempNode.left);
			if(tempNode.right!=null)
				queue.add(tempNode.right);
		}
	}
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  TreeNode rootNode=createBinaryTree();
  System.out.println("Level Order traversal of binary tree will be:");
  levelOrderTraversal(rootNode);
 }
 
 public static TreeNode createBinaryTree()
 {
  
  TreeNode rootNode =new TreeNode(40);
  TreeNode node20=new TreeNode(20);
  TreeNode node10=new TreeNode(10);
  TreeNode node30=new TreeNode(30);
  TreeNode node60=new TreeNode(60);
  TreeNode node50=new TreeNode(50);
  TreeNode node70=new TreeNode(70);
  
  rootNode.left=node20;
  rootNode.right=node60;
  
  node20.left=node10;
  node20.right=node30;
  
  node60.left=node50;
  node60.right=node70;
  
  return rootNode;
 }
}

Run above program and you will get following output:
 
Level Order traversal of binary tree will be:
40 20 60 10 30 50 70 

How HashSet works in java

This is one of the frequently asked question in core java interview so in this post, we will see how HashSet works in java.We have already seen How hashMap works in java and also difference between HashMap and HashSet.

Lets first see introduction of Hashset then we will go through internals of it.

HashSet:

HashSet implements Set interface which does not allow duplicate value.It is not synchronized and is not thread safe.
Definition of duplicate can be quite tricky sometimes.Lets consider two cases here.
  1. In case of primitive types(such as interger, String)
  2. In case of custom defined objects.
In case of primitive types:
In case of primitives type, it is very straight forward.Lets see with help of example:
Lets create a java program:
package org.arpit.java2blog;
import java.util.HashSet;

public class HashSetMain {

 public static void main(String[] args) {
  HashSet<String> nameSet=new HashSet<String>();
  nameSet.add("Arpit");
  nameSet.add("Arpit");
  nameSet.add("john");
  System.out.println("size of nameSet="+nameSet.size());
  System.out.println(nameSet);
 }

}
When you run above program, you will get following output:
size of nameSet=2
[Arpit, john]
So we tried to add String "Arpit" twice, but as HashSet does not allow duplicate value, it will add "Arpit" once in HashSet

In case of Custom Objects:
For understanding how HashSet will work in case of custom objects, you need to understand hashcode and equals method in java.Lets create a class called Country and implement only equals method in it.
package org.arpit.java2blog;

public class Country {

 String name;
 long population;
 public String getName() {
  return name;
  }
 public void setName(String name){
  this.name = name;
 }
 public long getPopulation() {
  return population;
 }
 public void setPopulation(long population) {
  this.population = population;
 }
 
 public String toString()
 {
  return name;
 }
 @Override
 public boolean equals(Object obj) {
  if (this == obj)
   return true;
  if (obj == null)
   return false;
  if (getClass() != obj.getClass())
   return false;
  Country other = (Country) obj;
  if (name == null) {
   if (other.name != null)
    return false;
  } else if (!name.equals(other.name))
   return false;
  return true;
 }
 
}
create main class:
package org.arpit.java2blog;

import java.util.HashSet;

public class HashSetCountryMain {

 public static void main(String[] args)
 {
  HashSet<Country> countrySet=new HashSet<Country>();
  Country india1=new Country();
  india1.setName("India");
 
  Country india2=new Country();
  india2.setName("India");
  
  countrySet.add(india1);
  countrySet.add(india2);
   
  System.out.println("size of nameSet="+countrySet.size());
  System.out.println(countrySet);
  
 }
}

When you run above program, you will get following output:
size of nameSet=2
[India, India]

Now you must be wondering even through two objects are equal why HashSet contains two values instead of one.This is because First HashSet calculates hashcode for that key object, if hashcodes are same then only it checks for equals method and because hashcode for above two country objects uses default hashcode method,Both will have different memory address hence different hashcode.
Now lets add hashcode method in above Country class
@Override
 public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + ((name == null) ? 0 : name.hashCode());
  return result;
 }
Run above main program again, you will get following output:
size of nameSet=1
[India]

So now we have good understanding of HashSet, lets see its internal representation:

Internal working of HashSet:

When you add any duplicate element to HashSet, add() method returns false and do not add duplicate element to HashSet.
How add method return false? For this, we need to see HashSet's add method in JavaAPI
public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    
    private transient HashMap<E,Object> map;
 
    // PRESENT is dummy value which will be used as value in map
    private static final Object PRESENT = new Object();
    
    /**
     * Constructs a empty map.so hash
     * 
     */
    public HashSet() {
    	map = new HashMap<E,Object>();
    }
    
    // return false if e is already present in HashSet
    public boolean add(E e) {
	    return map.put(e, PRESENT)==null;
    }
    
    // other HashSet methods
}
So from above code, It is clear that HashSet uses HashMap for checking duplicate elements.As we know that in HashMap , key should be unique. So HashSet uses this concept, When element is added to HashSet, it is added to internal HashMap as Key.This HashMap required some value so a dummy Object(PRESENT) is used as value in this HashMap.
PRESENT is dummy value which is used value for internal map.
Lets see add method:
 // return false if e is already present in HashSet
    public boolean add(E e) {
	    return map.put(e, PRESENT)==null;
    }
So here there will be two cases
  • map.put(e,PRESENT) will return null, if element not present in that map. So map.put(e, PRESENT) == null will return true ,hence add method will return true and element will be added in HashSet.
  • map.put(e,PRESENT) will return old value ,if element is already present in that map. So  map.put(e, PRESENT) == null will return false, hence add method will return false and element will not be added in HashSet.

Thursday, 17 July 2014

Binary Tree PostOrder traversal in java

In this post, we will see about PostOrder binary tree traversal in java.

PostOrder traversal:

In PostOrder traversal,each node is processed after subtrees traversal.In simpler words,Visit left subtree,  right subtree and then node.

Steps for PostOrder traversal are:
  • Traverse the left subtree in PostOrder.
  • Traverse the right subtree in PostOrder.
  • Visit the node.
 There can be two ways of implementing it
  • Recursive
  • Iterative
Recursive solution:
Recursive solution is very straight forward.Below diagram will make you understand recursion better.

Code for recursion will be:
public void postOrder(TreeNode root) {
  if(root !=  null) {
   postOrder(root.left);
   postOrder(root.right);
   //Visit the node by Printing the node data  
   System.out.printf("%d ",root.data);
  }
 }
Iterative solution:
Steps for iterative solution:
  1. Create an empty stack s and set currentNode =root.
  2. while currentNode is not NULL Do following
    1. Push currentNode 's right child and then currentNode to stack.
    2. Set currentNode =currentNode .left
  3. Pop an node from stack and set it as root and set it to currentNode 
    1. If the popped node has a right child and the right child is at top of stack, then remove the right child from stack, push the current node back and set currentNode as currentNode 's right child.
    2. Else print currentNode 's data and set currentNode as NULL.
  4. Repeat steps 2 and 3 while stack is not empty.
 
 public void postorderIter( TreeNode root) {
      if( root == null ) return;
   
      Stack<TreeNode> s = new Stack<TreeNode>( );
      TreeNode current = root;
   
      while( true ) {
   
          if( current != null ) {
              if( current.right != null ) 
               s.push( current.right );
              s.push( current );
              current = current.left;
              continue;
        }
   
          if( s.isEmpty( ) ) 
           return;
          current = s.pop( );
   
          if( current.right != null && ! s.isEmpty( ) && current.right == s.peek( ) ) {
              s.pop( );
              s.push( current );
              current = current.right;
          } else {
              System.out.print( current.data + " " );
              current = null;
          }
      }
  }
Lets create java program for InOrder traversal:
 
package org.arpit.java2blog;

import java.util.Stack;

public class BinaryTree {

 
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }
 
        // Recursive Solution
 public void postOrder(TreeNode root) {
  if(root !=  null) {
   postOrder(root.left);
   postOrder(root.right);
   //Visit the node by Printing the node data  
   System.out.printf("%d ",root.data);
  }
 }
 
  // Iterative solution
  public void postorderIter( TreeNode root) {
      if( root == null ) return;
   
      Stack<TreeNode> s = new Stack<TreeNode>( );
      TreeNode current = root;
   
      while( true ) {
   
          if( current != null ) {
              if( current.right != null ) 
               s.push( current.right );
              s.push( current );
              current = current.left;
              continue;
        }
   
          if( s.isEmpty( ) ) 
           return;
          current = s.pop( );
   
          if( current.right != null && ! s.isEmpty( ) && current.right == s.peek( ) ) {
              s.pop( );
              s.push( current );
              current = current.right;
          } else {
              System.out.print( current.data + " " );
              current = null;
          }
      }
  }
 
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  TreeNode rootNode=createBinaryTree();
  System.out.println("Using Recursive solution:");

  bi.inOrder(rootNode);

  System.out.println();
  System.out.println("-------------------------");
  System.out.println("Using Iterative solution:");

  bi.inOrderIter(rootNode);
 }
 
 public static TreeNode createBinaryTree()
 {
  
  TreeNode rootNode =new TreeNode(40);
  TreeNode node20=new TreeNode(20);
  TreeNode node10=new TreeNode(10);
  TreeNode node30=new TreeNode(30);
  TreeNode node60=new TreeNode(60);
  TreeNode node50=new TreeNode(50);
  TreeNode node70=new TreeNode(70);
  
  rootNode.left=node20;
  rootNode.right=node60;
  
  node20.left=node10;
  node20.right=node30;
  
  node60.left=node50;
  node60.right=node70;
  
  return rootNode;
 }
}

Run above program and you will get following output:
 
Using Recursive solution:
10 30 20 50 70 60 40 
-------------------------
Using Iterative solution:
10 30 20 50 70 60 40  

Tuesday, 15 July 2014

Binary Tree InOrder traversal in java

In this post, we will see about InOrder binary tree traversal in java.

InOrder traversal:

In InOrder traversal,each node is processed between subtrees.In simpler words,Visit left subtree, node and then right subtree.

Steps for InOrder traversal are:
  • Traverse the left subtree in InOrder.
  • Visit the node.
  • Traverse the right subtree in InOrder.
 There can be two ways of implementing it
  • Recursive
  • Iterative
Recursive solution:
Recursive solution is very straight forward.Below diagram will make you understand recursion better.

Code for recursion will be:

public void inOrder(TreeNode root) {
  if(root !=  null) {
   inOrder(root.left);
   //Visit the node by Printing the node data  
   System.out.printf("%d ",root.data);
   inOrder(root.right);
  }
 }
Iterative solution:

For recursion, we use implicit stack. So here to convert recursive solution to iterative, we will use explicit stack.
Steps for iterative solution:
  1. Create an empty stack s and Initialize current node as root
  2. Push the current node to s and set currentNode = currentNode.left until currentNode is NULL
  3. If currentNode is NULL and s is not empty then
    • Pop the top node from stack and print it
    •  set currentNode = currentNode.right
    • go to step 2
  4. If stack is empty and currentNode is also null then we are done with it

 
public void inOrderIter(TreeNode root) {

  if(root == null)
   return;

  Stack<TreeNode> s = new Stack<TreeNode>();
  TreeNode currentNode=root;

  while(!s.empty() || currentNode!=null){

   if(currentNode!=null)
   {
    s.push(currentNode);
    currentNode=currentNode.left;
   }
   else
   {
    TreeNode n=s.pop();
    System.out.printf("%d ",n.data);
    currentNode=n.right;
   }
  }
 }

Lets create java program for InOrder traversal:
 
package org.arpit.java2blog;

import java.util.Stack;

public class BinaryTree {

 
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }
 
        // Recursive Solution
 public void inOrder(TreeNode root) {
  if(root !=  null) {
   inOrder(root.left);
   //Visit the node by Printing the node data  
   System.out.printf("%d ",root.data);
   inOrder(root.right);
  }
 }
 
  // Iterative solution
 public void inOrderIter(TreeNode root) {

  if(root == null)
   return;

  Stack<TreeNode> s = new Stack<TreeNode>();
  TreeNode currentNode=root;

  while(!s.empty() || currentNode!=null){

   if(currentNode!=null)
   {
    s.push(currentNode);
    currentNode=currentNode.left;
   }
   else
   {
    TreeNode n=s.pop();
    System.out.printf("%d ",n.data);
    currentNode=n.right;
   }
  }
 }
 
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  TreeNode rootNode=createBinaryTree();
  System.out.println("Using Recursive solution:");

  bi.inOrder(rootNode);

  System.out.println();
  System.out.println("-------------------------");
  System.out.println("Using Iterative solution:");

  bi.inOrderIter(rootNode);
 }
 
 public static TreeNode createBinaryTree()
 {
  
  TreeNode rootNode =new TreeNode(40);
  TreeNode node20=new TreeNode(20);
  TreeNode node10=new TreeNode(10);
  TreeNode node30=new TreeNode(30);
  TreeNode node60=new TreeNode(60);
  TreeNode node50=new TreeNode(50);
  TreeNode node70=new TreeNode(70);
  
  rootNode.left=node20;
  rootNode.right=node60;
  
  node20.left=node10;
  node20.right=node30;
  
  node60.left=node50;
  node60.right=node70;
  
  return rootNode;
 }
}}
}
Run above program and you will get following output:
 
Using Recursive solution:
10 20 30 40 50 60 70 
-------------------------
Using Iterative solution:
10 20 30 40 50 60 70  

Binary Tree PreOrder traversal in java

In this post, we will see about PreOrder binary tree traversal in java.

PreOrder traversal:

In PreOrder traversal,each node is processed before either of its sub-trees.In simpler words,Visit each node before its children.

Steps for PreOrder traversal are:
  • Visit the node.
  • Traverse the left subtree in PreOrder.
  • Traverse the right subtree in PreOrder.
 There can be two ways of implementing it
  • Recursive
  • Iterative
Recursive solution:
Recursive solution is very straight forward.Below diagram will make you understand recursion better.



Code for recursion will be:

public void preorder(TreeNode root) {
    if(root !=  null) {
   //Visit the node by Printing the node data  
      System.out.printf("%d ",root.data);
      preorder(root.left);
      preorder(root.right);
    }
  }
Iterative solution:
For recursion, we use implicit stack. So here to convert recursive solution to iterative, we will use explicit stack.
Steps for iterative solution:
  1. Create empty stack and pust root node to it.
  2. Do the following when stack is not empty
    • Pop a node from stack and print it
    • Push right child of popped node to stack
    • Push left child of popped node to stack
We are pushing right child first, so it will be processed after left subtree as Stack is LIFO.
 
public void preorderIter(TreeNode root) {
   
         if(root == null)
             return;
  
         Stack<TreeNode> stack = new Stack<TreeNode>();
         stack.push(root);
  
         while(!stack.empty()){
          
             TreeNode n = stack.pop();
             System.out.printf("%d ",n.data);
  
           
             if(n.right != null){
                 stack.push(n.right);
             }
             if(n.left != null){
                 stack.push(n.left);
             }
  
         }
         
     }

Example:
Lets say your binary tree is :

Lets create java program for PreOrder traversal:
 
package org.arpit.java2blog;

import java.util.Stack;

public class BinaryTree {

 
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }
 
        // Recursive Solution
 public void preorder(TreeNode root) {
    if(root !=  null) {
   //Visit the node-Printing the node data  
      System.out.printf("%d ",root.data);
      preorder(root.left);
      preorder(root.right);
    }
  }
 
  // Iterative solution
  public void preorderIter(TreeNode root) {
   
         if(root == null)
             return;
  
         Stack<TreeNode> stack = new Stack<TreeNode>();
         stack.push(root);
  
         while(!stack.empty()){
          
             TreeNode n = stack.pop();
             System.out.printf("%d ",n.data);
  
           
             if(n.right != null){
                 stack.push(n.right);
             }
             if(n.left != null){
                 stack.push(n.left);
             }
  
         }
         
     }
 
 public static void main(String[] args)
 {
  BinaryTree bi=new BinaryTree();
  // Creating a binary tree
  TreeNode rootNode=createBinaryTree();
  System.out.println("Using Recursive solution:");
  
  bi.preorder(rootNode);
  
  System.out.println();
  System.out.println("-------------------------");
  System.out.println("Using Iterative solution:");
  
  bi.preorderIter(rootNode);
 }
 
 public static TreeNode createBinaryTree()
 {
  
  TreeNode rootNode =new TreeNode(40);
  TreeNode node20=new TreeNode(20);
  TreeNode node10=new TreeNode(10);
  TreeNode node30=new TreeNode(30);
  TreeNode node60=new TreeNode(60);
  TreeNode node50=new TreeNode(50);
  TreeNode node70=new TreeNode(70);
  
  rootNode.left=node20;
  rootNode.right=node60;
  
  node20.left=node10;
  node20.right=node30;
  
  node60.left=node50;
  node60.right=node70;
  
  return rootNode;
 }
}

Run above program and you will get following output:
 
Using Recursive solution:
40 20 10 30 60 50 70
-------------------------
Using Iterative solution:
40 20 10 30 60 50 70 

Friday, 11 July 2014

Difference between sleep and wait in java


One of the common interview question is "What is difference between sleep and wait in java".Before we actually see differences,let me give you brief introduction of both.

sleep

  • It causes current executing thread to sleep for specific amount of time.
  • Its accuracy depends on system timers and schedulers.
  • It keeps the monitors it has acquired, so if it is called from synchronized context, no other thread can enter that block or method.
  • If we call interrupt() method , it will wake up the sleeping thread.
    synchronized(lockedObject) {   
      Thread.sleep(1000); // It does not release the lock on lockedObject.
      // So either after 1000 miliseconds, current thread will wake up, or after we call 
      //t. interrupt() method.
      
  }

wait

  • It causes current thread to wait until either another thread invokes the notify() method or the notifyAll() method for this object
  • It must be called from synchronized context i.e. from block or method.It means before wait() method is called,current thread must have lock on that object.
  • It releases lock on the object on which it is called and added to wait list, so another thread can acquire lock on the object.
    synchronized(lockedObject) {   
   lockedObject.wait(); // It releases the lock on lockedObject.
      // So until we call notify() or notifyAll() from other thread,It will
   // not wake up
      
  }

sleep vs wait:

Parameter
wait
sleep
Synchonized
wait should be called from synchronized context i.e. from block or method, If you do not call it using synchronized context, it will throw IllegalMonitorStateException

It need not be called from synchronized block or methods
Calls on
wait method operates on Object and defined in Object class

Sleep method operates on current thread and is in java.lang.Thread
Release of lock
wait release lock of object on which it is called and also other locks if it holds any
Sleep method does not release lock at all
Wake up condition
until call notify() or notifyAll() from Object class
Until time expires or calls interrupt()
static
wait is non static method
sleep is static method

Thursday, 10 July 2014

How to find prime factors of a number in java

In this post, we will see how to find prime factors of a number in java.
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
The prime factors of a number are all of the prime numbers that will exactly divide the given number.
For example-
Prime factor of 15 = 3,5
Prime factor of 48=2,2,2,2,3

Lets create java program for it:
package org.arpit.java2blog;

import java.util.ArrayList;
import java.util.List;

public class PrimeFactorsMain {

 // This method calculate prime factor and add it to primeFactor list
 public static List<Integer> primeFactors(int number) {
  int n = number;
  List<Integer> primeFactors = new ArrayList<Integer>();
  for (int i = 2; i <= n; i++) {
   while (n % i == 0) {
    primeFactors.add(i);
    n /= i;
   }
  }
  return primeFactors;
 }

 public static void main(String[] args) {
  System.out.println("Primefactors of 15 are : ");
  System.out.printf("%s %n",primeFactors(15));

  System.out.println("Primefactors of 48 are :");
  System.out.printf("%s %n",primeFactors(48));

  System.out.println("Primefactors of 91");
  System.out.printf("%s %n",primeFactors(91));

 }
} 
Run above program and you will get following output:
Primefactors of 15 are : 
[3, 5] 
Primefactors of 48 are :
[2, 2, 2, 2, 3] 
Primefactors of 91
[7, 13] 
You must be wondering we are not checking whether loop variable i is prime or not But you don't need to do this because in any loop, number has been already divided by 2 to i-1 so i can only be divisor if it is prime.

More optimized solution:

Change above primeFactors function to below function
 // This method calculate prime factor and add it to primeFactor list
 public static List<Integer> primeFactors(int number) {
  int n = number;
  List<Integer> primeFactors = new ArrayList<Integer>();
  for (int i = 2; i <= n/i; i++) {
   while (n % i == 0) {
    primeFactors.add(i);
    n /= i;
   }
  }
  if(n>1)
   primeFactors.add(n);
  return primeFactors;
 } 
This is based on the fact that in above for loop,divisor can not be greater than n/i.
 

Java tutorial for beginners Copyright © 2012