Sunday, 28 June 2015

Java bloggers meet to celebrate 20th birthday of java, hosted by oracle

Oracle has invited java bloggers at Hyderabad campus on 13th June 2015 and we celebrated Java 's 20th birthday. Few days back, I got an invitation mail for this event and I was more than happy to join them.

It was really pleasure to meet other java bloggers and interact with them. It started with warm welcome by Ms. Vandana Shenoy( Directory Corporate Communications, Oracle) and she introduced the presenters.First speaker was Sanket Atal ( Group Vice President, India R&D, Oracle) and he gave presentation titled “Java – 20 years of Innovation”. It started with history of java to promising future of java. If you want to go through 20 year of the java, you can read more at oracle timeline
There were some quiz questions in between and it was pretty cool.


After that, there was a talk from java champion, Hashad Oak. He raised few very good points such as
  • Warm welcome nature of java.
  • Is syntax really important?
  • Java bloggers have a great responsibility for carrying a warm culture to the future developers
  • Promising future of java.

It was followed speech by Mr. Debraj Dutta, a winner of Oracle IOT challenge. He presented his "Bot so" robot which was really great. It uses raspberry pi and It actually takes command from twitter, then capture images and upload to google drive and share same at twitter privately.



After that, we cut yummy java 20 cake and celebrated java's 20th birthday.




In the end, I would like to thank Oracle for inviting to this event and I look forward more such events from Oracle. Below is the group picture of the event











Thursday, 25 June 2015

How to iterate over Map or HashMap in java

In this post, we will see how  can we iterate a map in java. There are four ways of iterating over a map, HashMap or TreeMap.
  1. Using keyset() and for each loop(Java 5)
  2. Using keyset() and java Iterator
  3. Using EntrySet() and for each loop(Java 5)
  4. Using EntrySet() and java Iterator
if you remove elements while iterating , then 1st and 3rd option  will throw java.util.ConcurrentModificationException.
If you understand internal working of HashMap, then it may be easier for you to iterate an HashMap

Lets take an example:
1. IterateListMain.java 
package org.arpit.java2blog;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;

public class IterateMapMain {

 public static void main(String args[])
 {
  // HashMap with Country as key and capital as value
  HashMap<String,String> countryCapitalMap=new HashMap<String,String>();
  countryCapitalMap.put("India","Delhi");
  countryCapitalMap.put("Japan","Tokyo");
  countryCapitalMap.put("France","Paris");
  countryCapitalMap.put("Russia","Moscow");

  // Iterating Using keySet() and for each loop
  System.out.println("Iterating Using keySet() and for each loop");
  for (String countryKey:countryCapitalMap.keySet()) {
   System.out.println("Country:"+ countryKey +" and  Capital:"+countryCapitalMap.get(countryKey));

  }
  System.out.println("-----------------------------");

  // Iterating Using keySet() and java iterator
  System.out.println("Iterating Using keySet() and java Iterator");
  Iterator<String> countryKeySetIterator=countryCapitalMap.keySet().iterator();
  while(countryKeySetIterator.hasNext()){
   String countryKey=countryKeySetIterator.next();
   System.out.println("Country:"+ countryKey +" and Capital:"+countryCapitalMap.get(countryKey));

  }
  System.out.println("-----------------------------");

  // Iterating Using entrySet() and for each loop
  System.out.println("Iterating Using entrySet() and for each loop");
  for (Entry<String,String> entry:countryCapitalMap.entrySet()) {
   System.out.println("Country:"+ entry.getKey() +" and  Capital:"+entry.getValue());

  }
  System.out.println("-----------------------------");

  // Iterating Using entrySet() and java iterator
  System.out.println("Iterating Using entrySet() and and java Iterator");
  Iterator<Entry<String,String>> entryIterator=countryCapitalMap.entrySet().iterator();
  while(entryIterator.hasNext())
  {
   Entry<String,String> entry=entryIterator.next();
   System.out.println("Country:"+ entry.getKey() +" and  Capital:"+entry.getValue());

  }
  System.out.println("-----------------------------");

 }

}

Run it and you will get following output:
Iterating Using keySet() and for each loop
Country:France and  Capital:Paris
Country:Russia and  Capital:Moscow
Country:Japan and  Capital:Tokyo
Country:India and  Capital:Delhi
-----------------------------
Iterating Using keySet() and java Iterator
Country:France and Capital:Paris
Country:Russia and Capital:Moscow
Country:Japan and Capital:Tokyo
Country:India and Capital:Delhi
-----------------------------
Iterating Using entrySet() and for each loop
Country:France and  Capital:Paris
Country:Russia and  Capital:Moscow
Country:Japan and  Capital:Tokyo
Country:India and  Capital:Delhi
-----------------------------
Iterating Using entrySet() and and java Iterator
Country:France and  Capital:Paris
Country:Russia and  Capital:Moscow
Country:Japan and  Capital:Tokyo
Country:India and  Capital:Delhi
-----------------------------

Wednesday, 24 June 2015

How to iterate a list in java

In this post, we will see how  can we iterate a list in java. There are four ways of iterating over a list.
  • For loop
  • For each loop(Java 5)
  • While loop
  • Iterator
Below example will help you to understand, how to iterate list in java. I am taking custom object list to understand better

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;
 } 
  
}
2. IterateListMain.java 
package org.arpit.java2blog;

import java.util.ArrayList;
import java.util.Iterator;

public class IterateListMain {
 /**
     * @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);
        
        // We are going to iterate on this list and will print 
        //name of the country 
        ArrayList<Country> countryLists=new ArrayList<Country>();
        countryLists.add(india);
        countryLists.add(japan);
        countryLists.add(france);
        countryLists.add(russia);
        
        // For loop
        System.out.println("Iterating using for loop : ");
        for (int i = 0; i < countryLists.size(); i++) {
   Country countryObj=countryLists.get(i);
   System.out.println(countryObj.getName());
  }
        System.out.println("-----------------------------");
       
       // For each loop
        System.out.println("Iterating using for each loop : ");
        for (Country countryObj:countryLists) {
   System.out.println(countryObj.getName());
  }
        System.out.println("-----------------------------");
       
       // While loop
        System.out.println("Iterating using while loop : ");
        int i=0;
        while(i<countryLists.size())
        {
         Country countryObj=countryLists.get(i);
   System.out.println(countryObj.getName());
   i++;
        }
        
        System.out.println("-----------------------------");
      
        // Iterator
        System.out.println("Iterating using iterator : ");
        Iterator<Country> iteratorCountryLists= countryLists.iterator();
        while(iteratorCountryLists.hasNext())
        {
         System.out.println(iteratorCountryLists.next().getName());
        }
        
    }
}
Run it and you will get following output:
Iterating using for loop : 
India
Japan
France
Russia
-----------------------------
Iterating using for each loop : 
India
Japan
France
Russia
-----------------------------
Iterating using while loop : 
India
Japan
France
Russia
-----------------------------
Iterating using iterator : 
India
Japan
France
Russia


Wednesday, 17 June 2015

Difference between ArrayList and LinkedList in java


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

ArrayList

  • ArrayList is implementation of list interface.
  • ArrayList is not synchonized(so not thread safe)
  • ArrayList is implemented using array as internal data structure.It can be dynamically resized .

LinkedList

  • LinkedList is implementation of list and deque interface.
  • LinkedList is not synchronized
  • LinkedList is implemented using doubly linked list as internal data structure.

ArrayList vs LinkedList:

Parameter
ArrayList
LinkedList
Internal data structure
It uses dynamic array to store elements internally
It uses doubly Linked List to store elements internally
Manipulation
If  We need to insert or delete element in ArrayList, it may take O(n), as it internally uses array and we may have to shift elements in case of insertion or deletion
If  We need to insert or delete element in LinkedList, it will take O(1), as it internally uses doubly LinkedList 
Search
Search is faster in ArrayList as uses array internally which is index based. So here time complexity is O(1)
Search is slower in LinkedList as uses doubly Linked List internally So here time complexity is O(n)
Interfaces
ArrayList implements List interface only, So it can be used as List only
LinkedList implements List,Deque interfaces, so it can be used as List,Stack or Queue

When to use ArrayList or LinkedList?

It actually depends on our need.

  • If we have more insertion or deletion then we should use LinkedList.
  • If we have less insertion or deletion and more search operations then we should use ArrayList.


Tuesday, 16 June 2015

Java Thread Join Example

Thread class's join method can be used to stop current execution of thread until thread it joins, completes its task. So basically , it waits for the thread on which join method is getting called, to die.

There are three variant of join method:

public final void join() throws InterruptedException :
Thread on which join method is getting called to die.

public final void join(long millis) throws InterruptedException:
This method when called on the thread, it waits for either of following:
  • Thread on which join method is getting called, to die. 
  • Specified milliseconds
public final void join(long millis,int nanos) throws InterruptedException:
This method when called on the thread, it waits for either of following:
  • Thread on which join method is getting called, to die. 
  • Specified milliseconds + nano seconds

Example:

Lets take simple example:
package org.arpit.java2blog.thread;

public class MyRunnable implements Runnable{

 public void run()
 {
  try {
   System.out.println(Thread.currentThread().getName()+" Start");
   // thread sleeps for 4 secs
   Thread.sleep(4000);
   System.out.println(Thread.currentThread().getName()+" end");
  } catch (InterruptedException e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  }  
 } 
}
Create ThreadExampleMain.java
package org.arpit.java2blog.thread;

public class ThreadExampleMain {
 
 public static void main(String args[])
 {
               
  System.out.println("Main thread execution starts");
  MyRunnable mr=new MyRunnable();
  
  Thread t1=new Thread(mr,"Thread 1");
  Thread t2=new Thread(mr,"Thread 2");
  Thread t3=new Thread(mr,"Thread 3");
  
  t1.start();
  // lets waits for  t1 to die
  try {
   t1.join();
  } catch (InterruptedException e) {
   
   e.printStackTrace();
  }
 
 
  t2.start();
  try {
 // lets waits for 1 sec or t2 to die which ever occurs first 
  t2.join(1000);
   
  } catch (InterruptedException e1) {
   
   e1.printStackTrace();
  }
  t3.start() ;
  
  // complete all threads before completing main thread
  try {
   t2.join();
   t3.join();
   
  } catch (InterruptedException e1) {
   
   e1.printStackTrace();
  }
  System.out.println("Main thread execution ends");   
 }
}

When you run above program, you will get following output.
Main thread execution starts
Thread 1 Start
Thread 1 end
Thread 2 Start
Thread 3 Start
Thread 2 end
Thread 3 end
Main thread execution ends

Lets analysis output now.
  1. Main thread execution starts
  2. Thread 1 starts(Thread 1 start) and as we have put t1.join() , it will wait for t1 to die(Thread 1 end). 
  3. Thread 2 starts(Thread 2 start) and waits for either 1 seconds or die but as we have put sleep for 4 seconds in run method, it will not die in 1 second. so main thread resumes and Thread 3 starts(Thread 3 start)
  4. As we have put t2.join() and t3.join(). These 2 threads will get completed before exiting main thread.So Thread 2 will end(Thread 2 end ) and then thread 3 will end(Thread 3 end).
  5. Main thread execution ends.

Sunday, 14 June 2015

Java Thread Sleep Example

Sleep method of java.lang.Thread is used to pause current execution of thread for specific period of time.

Some important points about sleep method are :
  • 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.
      
  
Example: Create a class FirstThread.java as below.
package org.arpit.java2blog.thread;

public class FirstThread implements Runnable{

 public void run()
 {
  System.out.println("Thread is running");
 }
 
}
Create main class named ThreadSleepExampleMain.java
package org.arpit.java2blog.thread;

public class ThreadSleepExampleMain {
 
 public static void main(String args[])
 {
  FirstThread ft= new FirstThread();
  
  Thread t=new Thread(ft);
  t.start();
  long startTime=System.currentTimeMillis();
  try {
                // putting thread on sleep
   Thread.sleep(1000);
  } catch (InterruptedException e) {
   e.printStackTrace();
  }
  long endTime=System.currentTimeMillis();
  long timeDifference=(endTime-startTime);
  System.out.println("Time difference between before and after sleep call: "+timeDifference);
 }

}

When you run above program, you will get following output.
Thread is running
Time difference between before and after sleep call: 1001
You can see there is delay of 1 milliseconds. As mentioned earlier,its accuracy depends on system timers and schedulers.

Java Thread example

Thread can be called as light weight process. Java supports multithreading , so it allows your application to perform two or more task concurrently.  Multithreading can be of advantage specially when now a days, machine has multiple CPUs, so multiple tasks can be executed concurrently.

Whenever we call main method in java, it actually creates a single main thread. Although it creates other threads too but those are related to system and known as daemon threads. So if we want to create more threads to execute task concurrently , we can use multiThreading.

Thread can be created in two ways.
  • By extending Thread class
  • By implementing Runnable interface

By extending Thread class:

You can create your own thread by extending Thread class and override run method. You need to create object of that class and then call start() method on it to execute thread as different threads.
Create a class FirstThread.java as below.
package org.arpit.java2blog.thread;

public class FirstThread extends Thread{

 public void run()
 {
  System.out.println("Thread is running");
 }
 
}
In above program, we have created our own thread by extending Thread class and overriding run method.
Create main class named ThreadExampleMain.java
package org.arpit.java2blog.thread;

public class ThreadExampleMain {
 
 public static void main(String args[])
 {
  FirstThread ft= new FirstThread();
  ft.start();
 }

}

In above program ,we are creating a object of FirstThread class and calling start method to execute the thread.
When you run above program, you will get following output.
Thread is running

By implementing Runnable  interface:

The other way is , you need to implement Runnable interface and override public void run() method. You need to instantiate the class, pass created object to Thread constructor and call start method on thread object to execute thread as different threads.
Create a class FirthThread.java as below.
package org.arpit.java2blog.thread;

public class FirstThread implements Runnable{

 public void run()
 {
  System.out.println("Thread is running");
 }
 
}
In above program, we have created our own class and implemented Runnable interface and overridden run() method.
Create main class named ThreadExampleMain.java
package org.arpit.java2blog.thread;

public class ThreadExampleMain {
 
 public static void main(String args[])
 {
  FirstThread ft= new FirstThread();
  Thread t=new Thread(ft);
  t.start();
 }

}

In above program ,we are creating a object of FirstThread class and passing it to Thread constructor and calling start method to actually execute.The start method will eventually call run method of FirstThread class.
When you run above program, you will get following output.
Thread is running

Thread vs Runnable which is better?

Implementing Runnable interface is considered to be better approach than Extending Thread due to following reasons.
  • Java does not support multiple inheritance so if you extend Thread class and you can not extend any other class which is needed in most of the cases. 
  • Runnable interface represents a task and this can be executed with help of Thread class or Executors. 
  • When you use inheritance, it is because you want to extend some properties of parent, modify or improve class behavior. But if you are extending thread class just to create thread, so it may not be recommended behavior for Object Oriented Programming.




Saturday, 6 June 2015

Introduction to complexity of algorithm

"How will you calculate complexity of algorithm" is very common question in interview.How will you compare two algorithm? How running time get affected when input size is quite large? So these are some question which is frequently asked in interview.In this post,We will have basic introduction on complexity of algorithm and also to big o notation

What is an algorithm?

An algorithm is step by step instructions to solve given problem.
Lets take a simple example.You want to write an algorithm for listening particular song.
1) Search for song on computer.
2) Is song available?
            i.If Yes,Then listen that song.
           ii.If no,download that song and then listen that song.
So we are solving a problem by step by step procedure.This step by step instructions is called Algorithm.

Why do you need to evaluate an algorithm?

You need to evaluate an algorithm so that you can find most optimize algorithm for solving given problem and also considering various factors and constraints.
For example:
You want to go from city A to City B.Then there are various choices available i.e. by flight,bus or train.So you need to choose among different options depending on your budget and urgency.

Counting number of instructions: 

Number of instructions can be different for different programming languages.
Lets count number of instruction for searching a element in a array.
int n=array.length
for (int i = 0; i < n; i++) {

 if(array[i]==elementToBeSearched)
         return true;
 }
   return false;
Lets assume our processor takes one instruction for each of the operation:
  • For assigning a value to a variable
  • For comparting two values
  • Multiply or addition
  • Return statement
In Worst case:
If element which we want to search is last element in sorted array then it will be worst case here.
So :
if(array[i]==elementToBeSearched) ,i++ and i<n will executed n time

i=0,i<n, return true or false will be executed one time.

Here f(n)=3n+3

Asymptotic behaviour :

Here We will see how f(n) performs with larger value of n.Now in above function, we have two parts i.e. 3n and 3. Here you can note two points:
  • As n grows larger, we can ignore constant 3 as it will be always 3 irrespective of value of n. It makes sense as you can consider 3 as initialization constant and different language may take different time for initialization.So other function remains f(n)=3n.
  • We can ignore constant multiplier as different programming language may compile the code differently. For example array look up may take different number of instructions in different languages. So what we are left with is f(n)=n

How will you compare algorithms?

You can compare algorithms by its rate of growth with input size n
Lets take a example.For solving same problem, you have two functions:
f(n) =4n2 +2n+4 and f(n) =4n+4
For f(n) =4n2 +2n+4
so here
f(1)=4+2+4
f(2)=16+4+4
f(3)=36+6+4
f(4)=64+8+4
....
As you can see here contribution of n2 increasing with increasing value of n.So for very large value of n,contribution of n2 will be 99% of value on f(n).So here we can ignore low order terms as they are relatively insignificant as described above.In this f(n),we can ignore 2n and 4.so
n2 +2n+4 -------->n2

For f(n) =4n+4
so here
f(1)=4+4
f(2)=8+4
f(3)=12+4
f(4)=16+4
....
As you can see here contribution of n increasing with increasing value of n.So for very large value of n,contribution of n will be 99% of value on f(n).So here we can ignore low order terms as they are relatively insignificant.In this f(n),we can ignore 4 and also 4 as constant multiplier as seen above so
4n+4 -------->n

So here n is highest rate of growth.
Point to be noted :
We are dropping all the terms which are growing slowly and keep one which grows fastest.

Big O Notation:

This notation is used for theoretical measure of  execution  of an algorithm. It gives tight upper bound of a given function. Generally it is represented as f(n)=O(g(n)) and it reads as "f of n is big o of g of n".

Formal definition:
f(n) = O(g(n)) means there are positive constants c and n0, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0. The values of c and n0 must not be depend on n. 



When you say O(g(n)) , It means it will never be worst than g(n). Having said that it means O(g(n)) includes smaller or same order of growth as g(n).
So O(n) includes O(n),O(logn) and O(1).
So O(g(n)) is a good way to show complexity of algorithm.

Lets take some example and calculate value for c and n0.
1. f(n)=4n+3
Writing in a form of f(n)<=c*g(n) with f(n)=4n+3 and g(n)=5n

4n+3<=5n for n0=3 and c=5.

or 4n+3<=6n for n0=2 and c=6
Writing in a form of f(n)<=c*g(n) with f(n)=4n+3 and g(n)=6n
so there can be multiple values for n0 and c for which f(n)<=c g(n) will get satisfied.

2. f(n)=4n2 +2n+4
Writing in a form of f(n)<=c*g(n) with f(n)=4n2 +2n+4 and g(n)=5n2
4n2 +2n+4<=5n2 for n0=4 and c=5

Rules of thumb for calculating complexity of algorithm:

Simple programs can be analyzed using counting number of loops or iterations.

Consecutive statements:
We need to add time complexity of consecutive statements.
       
                   int m=0; // executed in constant time c1
                   m=m+1;  // executed in constant time c2
  

f(n)=c1+c2;
So O(f(n))=1

Calculating complexity of a simple loop:
Time complexity of a loop can be determined by running time of statements inside loop multiplied by total number of iterations.
         int m=0; // executed in constant time c1
         // executed n times
         for (int i = 0; i < n; i++) {
             m=m+1;  // executed in constant time c2
  }
f(n)=c2*n+c1;
So O(n)=n

Calculating complexity of a nested loop:
It is product of iterations of each loop.
         
          int m=0; executed in constant time c1
          // Outer loop will be executed n times 
   for (int i = 0; i < n; i++) {
          // Inner loop will be executed n times
  for(int j = 0; j < n; j++)
  {
   m=m+1; executed in constant time c2
  }
 }
f(n)=c2*n*n + c1
So O(f(n))=n2

If and else:
When you have if and else statement, then time complexity is calculated with whichever of them is larger.
    
           int countOfEven=0;//executed in constant time c1
        int countOfOdd=0; //executed in constant time c2
           int k=0; //executed in constant time c3
//loop will be executed n times  
  for (int i = 0; i < n; i++) {
          if(i%2==0) //executed in constant time c4
            { countOfEven++; //executed in constant time c5
              k=k+1; //executed in constant time c6
            }
          else
            countOfOdd++; //executed in constant time c7
 }
                     
f(n)=c1+c2+c3+(c4+c5+c6)*n
So o(f(n))=n

Logarithmic complexity

Lets understand logarithmic complexity with the help of example.You might know about binary search.When you want to find a value in sorted array, we use binary search.
  
public  int binarySearch(int[] sorted, int first, int last, int elementToBeSearched) {
     int iteration=0;
     while (first < last) {
      iteration++;
      System.out.println("i"+iteration);
         int mid = (first + last) / 2;  // Compute mid point.
         System.out.println(mid);
         if (elementToBeSearched < sorted[mid]) {
          last = mid;     // repeat search in first half.
         } else if (elementToBeSearched > sorted[mid]) {
             first = mid + 1;  // Repeat search in last half.
         } else {
             return mid;     // Found it. return position
         }
     }
     return -1;    // Failed to find element
 }
Now lets assume our soreted array is:
  
int[] sortedArray={12,56,74,96,112,114,123,567};
and we want to search for 74 in above array. Below diagram will explain how binary search will work here.

When you observe closely, in each of the iteration you are cutting scope of array to the half. In every iteration, we are overriding value of first or last depending on soretedArray[mid].
So for
0th iteration : n
1th iteration: n/2
2nd iteration n/4
3rd iteration n/8.
Generalizing above equation:
For ith iteration : n/2i

So iteration will end , when we have 1 element left i.e. for any i, which will be our last iteration:
1=n/2i;
2i=n;
after taking log
i= log(n);
so it concludes that number of iteration requires to do binary search is log(n) so complexity of binary search is log(n)
It makes sense as in our example, we have n as 8 . It took 3 iterations(8->4->2->1) and 3 is log(8).
So If we are dividing input size by k in each iteration,then its complexity will be O(logk(n)) that is log(n) base k.

Lets take an example:
  int m=0; 
         // executed log(n) times
         for (int i = 0; i < n; i=i*2) {
             m=m+1; 
  }
Complexity of above code will be O(log(n)).

Exercise:

Lets do some exercise and find complexity of given code:

1.
   
         int m=0; 
         for (int i = 0; i < n; i++) {
             m=m+1; 
  }
Ans:
   
         int m=0; 
         // Executed n times
         for (int i = 0; i < n; i++) {
             m=m+1; 
  }
Complexity will be O(n)

 2.
   
        int m=0;
         for (int i = 0; i < n; i++) {
             m=m+1; 
  }
   for (int i = 0; i < n; i++) {
       for(int j = 0; j < n; j++)
             m=m+1; 
  }
}
Ans:
   
        int m=0;
       // Executed n times
         for (int i = 0; i < n; i++) {
             m=m+1; 
  }
    // outer loop executed n times
   for (int i = 0; i < n; i++) {
 // inner loop executed n times
       for(int j = 0; j < n; j++)
             m=m+1; 
  }
}
Complexity will be :n+n*n --->O(n2)

3.
   
        int m=0;
       
    // outer loop executed n times
   for (int i = 0; i < n; i++) {
 // middle loop executed n/2 times
       for(int j = n/2; j < n; j++)
          for(int k=0;k*k < n; k++ )
             m=m+1; 
  }
        }
}
Ans:
   
        int m=0;
       
    // outer loop executed n times
   for (int i = 0; i < n; i++) {
 // middle loop executed n/2 times
       for(int j = n/2; j < n; j++)
      // inner loop executed log(n) times
          for(int k=0;k*k < n; k++ )
             m=m+1; 
  }
       }
}
Complexity will be n*n/2*log(n)--> n2log(n)

 4.
   
 int m=0;
       
    
   for (int i = n/2; i < n; i++) {
       for(int j = n/2; j < n; j++)
          for(int k=0;k < n; k++ )
             m=m+1; 
  }
Ans:
 int m=0;
       
    // outer loop executed n/2 times
   for (int i = n/2; i < n; i++) {
 // middle loop executed n/2 times
       for(int j = n/2; j < n; j++)
      // inner loop executed n times
          for(int k=0;k < n; k++ )
             m=m+1; 
  }
Complexity will be n/2*n/2*n --> n3

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 void  printArray(int[] path,int len)
 {
	 for (int i = 0; i < len; i++) {
		System.out.print(" "+path[i]);
	}
	 System.out.println();
 }
 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
 

Java tutorial for beginners Copyright © 2012