Counting number of Objects in Java

Dear reader,
I am writing a very common use case here: Counting number of objects which are there in HEAP memory.
This is basically an interview question: how to count number of objects created for a class.

Giving a very basic example below:
=================
public class MySerialization1 {
    static int counter;    //Defined a counter for this class
    static String className="MySerialization1"; 
    
    public MySerialization1() {
        synchronized(MySerialization.class) {   //making the counter thread safe
            counter++;
        }
    }
    public static void main(String args[]) throws Exception {
        MySerialization1 oc = new MySerialization1();  
        MySerialization1 od = new MySerialization1();
        MySerialization1 oe = new MySerialization1();
        MySerialization1 of = new MySerialization1();
        MySerialization1 og = new MySerialization1();
        System.out.println("Total object count: "+counter);

        Object ob=Class.forName(className).newInstance();  //Creating object using Class.forName();
        System.out.println("Total object count after Class.forName().newInstance(): "+counter);
        
        og.makeNull();    //Decrease the counter value
        og=null;          //Make object null       
        System.out.println("Total object count after null: "+counter);
    }
    private static void makeNull() {
        synchronized(MySerialization.class) {
            counter--;
        }
    }
}
//Output:
Total object count: 5
Total object count after Class.forName().newInstance(): 6
Total object count after null: 5
===================

Now, lets tweak little bit. When you serialize, you will have an object. What if you de-serialize here,
since constructor didn't get invoked at de-serialization time(assuming no inheritance here), you will have 
the same count of object. I mean see below example:

===================
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;

public class MySerialization implements Serializable {
    private static final long serialVersionUID = 1L;
    static String className="MySerialization"; 
    static int counter;
    public MySerialization(){
        synchronized(MySerialization.class) {
            counter++;
        }
    }

    public static void main(String[] args) throws Exception {
        MySerialization object=new MySerialization();
        System.out.println("Object is: "+object);
        ObjectOutputStream out=new ObjectOutputStream(new FileOutputStream("output.out"));
        out.writeObject(object);
        System.out.println("Object is saved using Serialization");

        ObjectInputStream in=new ObjectInputStream(new FileInputStream("output.out"));
        MySerialization deserialObject=(MySerialization)(in.readObject());
        System.out.println("Object is read using De-Serialization");
        System.out.println("Object is: "+deserialObject);
        System.out.println("Total object count after deserialization: "+counter);

        Object tempObj=Class.forName(className).newInstance();
        System.out.println("Total object count after Class.forName().newInstance(): "+counter);
    }

    //Comment the below method and then see the output again, This is read internally
    //while de-serializing object by JVM.
    /*
    private Object readResolve(){
        return new MySerialization();
    }
    */
}

//Output: 
Object is: MySerialization@1c4bd0
Object is saved using Serialization
Object is read using De-Serialization
Object is: MySerialization@1c68b0
Total object count after deserialization: 1
Total object count after Class.forName().newInstance(): 2

NOTE: If you see the output, after de-serialization too, count is only 1. Count is increased to "2"
      because of Class.forName().newInstance().
      Now un-comment the comment line, having method "readResolve()" and then run the same program, 
      below is the output:

//Output:
Object is: MySerialization@1c4bd0
Object is saved using Serialization
Object is read using De-Serialization
Object is: MySerialization@1c68c8
Total object count after deserialization: 2
Total object count after Class.forName().newInstance(): 3

NOTE: See the difference. When Java De-Serializes a saved object, it checks whether "readResolve()" 
      method is re-defined in Serializable class or no. You can use "public" access specifier too in place
      of "private". If re-defined, it return the object from there. Since constructor again gets called,
      Counter is increased. 
      The same logic we use in SingletonPattern too, where even after De-Serialization, we need the same 
      old object (I mean only one object) else De-serialization creates a new/converted one which violates 
      Singleton Pattern fundamental.

NOTE: A more sophisticated program which will show count of Objects of each class used in Program will be written
      later, as I have not written as of now. 
      Like if we use Thread, StringBuffer, HashMap, List etc in our program and then there should be a method to 
      display ObjectStatistics for each class used in program. You can use Inner class and put a counter there.
      I will write later.      
      
--------------------------------END--------------------------------      

JTA and Transaction Attributes

JTA and Transaction Attributes

Dear reader,
In this blog article I have discussed about JTA (Java Transaction API) and Transaction Attributes.

The Contents are taken from below site but edited for my reading purpose:
http://www.java-tips.org/java-ee-tips/enterprise-java-beans/introduction-to-the-java-transactio.html

A transaction is a series of operations that must be performed atomically. In other words, each operation 
in the transaction series must succeed for the entire transaction to be successful. If any operation in the 
transaction does not succeed, the entire transaction fails. At that point, any operations which have succeeded 
must be "rolled back" so that the end state matches with what was in place when the transaction started.

For example, let's say you want to transfer $50 from a savings account (account number: 12345-1) to a checking 
account (account number 12345-2). The steps in this transaction can be stated in "pseudo code" as follows:

   BOUNDARY: START TRANSACTION A
   SUBTRACT 50 DOLLARS FROM SAVINGS ACCOUNT 12345-1
   ADD 50 DOLLARS TO THE CHECKING ACCOUNT 12345-2
   BOUNDARY: END TRANSACTION A

To run the transaction, the following code is required:
   PREPARE (RUN) TRANSACTION A
   IF TRANSACTION A SUCCEEDED
       COMMIT TRANSACTION A
   ELSE
       ROLLBACK TRANSACTION A

Let's assume that there are sufficient funds to subtract $50 from the savings account, so the first part of 
the transaction succeeds. However, let's also assume that the second part fails. When the computer attempts 
to add 50 dollars to the checking account, it discovers that the checking account is frozen. Because the 
second part of the transaction fails, the entire transaction fails. As a result, the first part of the transaction 
needs to be rolled back: means $50 needs to be placed back into the savings account 12345-1. This is essential. 
Otherwise, each time the computer tries to transfer money from the savings to the checking account, it will 
lose the money!

If the entire transaction succeeds, then the entire transaction is committed, and the results are made permanent.

Note that the commit process takes two phases to complete. In the first phase, checks are made to see that the 
transaction ran without error. If there were no errors, the results are committed in the second phase. If there 
were errors in the first-phase check, the transaction is rolled back. This common transaction strategy is 
appropriately called the two-phase commit protocol.

Transactions in the J2EE Environment:
    The Java Transaction API(JTA) is part of the J2EE platform. The API gives you the ability to perform 
    distributed transactions, that is, an application can use the API to perform transactions on more than 
    one data store in the network at the same time. But to do this efficiently, it helps to have another 
    component operating in the application server: a J2EE transaction manager. A transaction manager helps 
    to efficiently schedule and execute the potentially large number of transactions coming in through the 
    application server.

Many database vendors provide their own transaction managers. However, a particular DBMS's transaction 
manager might not work with databases from different vendors. If you want to work with these heterogeneous 
databases, for example, if you want to update multiple databases from different vendors, you should consider 
using a JTA transaction with a corresponding J2EE transaction manager. The JTA specification states that 
"A JTA transaction is controlled by the J2EE transaction manager." Note that the J2EE transaction manager 
does have one limitation: the J2EE transaction model is flat. Support for nested transactions is not part 
of J2EE. This means that the J2EE transaction manager cannot start a transaction for an instance until the 
previous transaction has ended.

Learning the JTA:
There are three separate interfaces that you can use with the JTA to perform transactions, and each uses a 
unique approach to handling transactions. The interfaces are:

    javax.transaction.UserTransaction: This interface allows you to specify the transaction boundaries, 
        bypassing a transaction manager.

    javax.transaction.TransactionManager. This interface allows you to delegate the boundaries of the 
        transactions, as well as various transaction operations, to the J2EE transaction manager.

    javax.transaction.xa.XAResource. This interface maps to the X/Open CAE Specification (Distributed Transaction 
        Processing: The XA Specification) standard for using third-party XA-compliant transaction managers to perform 
        transactions.

Because most J2EE programmers only use the first interface, I am writing for that only.

EJB Transactions: Container and Bean-Managed Transactions, not explaining here.

Container-managed transactions can be used with any type of enterprise bean (session bean, entity bean, or message-
driven bean). With container-managed transactions, the EJB container sets the boundaries of the transaction. This is 
typically done by marking one or more methods in the bean as individual transactions. The container sets the 
transaction boundary just before the beginning of the method, and sets the end boundary just before the method 
exits. However, with container-managed transactions, each method can be only one transaction -- multiple transactions 
are not allowed. When deploying a bean, you specify which of the bean's methods are associated with transactions. 
You do this by setting the transaction attributes.

The sequence of transaction events differs between container-managed and bean-managed transactions.
Below are the sequence:

Container-managed Transactions:
For EJB applications with container-managed transactions, a basic transaction works in the following way:

1.  In the EJB’s deployment descriptor, the Bean Provider or Application Assembler specifies the transaction type 
    (transaction-type element) for container-managed demarcation (Container).
   
2.  In the EJB’s deployment descriptor, the Bean Provider or Application Assembler specifies the default transaction 
    attribute (trans-attribute element) for the EJB, which is one of the following settings: 
    NotSupported, Required, Supports, RequiresNew, Mandatory, or Never. 
    Detailed description of all these attributes are written in the blog article.
 
3.  However in the EJB’s deployment descriptor, we can set trans-attribute for one or more methods as per 
    requirement. However this is optional.
4.  When a client application invokes a method in the EJB, the EJB container checks the trans-attribute setting in the 
    deployment descriptor for that method. If no setting is specified for the method, the EJB uses the default 
 trans-attribute setting for that EJB.
 
5.  The EJB container takes the appropriate action depending on the applicable trans-attribute setting.
        For example, if the trans-attribute setting is Required, the EJB container invokes the method within the 
    existing transaction context or, if the client called without a transaction context, the EJB container 
    begins a new transaction before executing the method.
  
        In another example, if the trans-attribute setting is Mandatory, the EJB container invokes the method within 
    the existing transaction context. If the client called without a transaction context, the EJB container throws 
    the javax.transaction.TransactionRequiredException exception.
  Detailed description of all these attributes are written in the blog article.
 
6.  During invocation of the business method, if it is determined that a rollback is required, the business method 
    calls the EJBContext.setRollbackOnly method, which notifies the EJB container that the transaction is to be 
 rolled back at the end of the method invocation.
    Note: Calling the EJBContext.setRollbackOnly method is allowed only for methods that have a meaningful transaction 
 context.
 
7. At the end of the method execution and before the result is sent to the client, the EJB container completes the 
   transaction, either by committing the transaction or rolling it back (if the EJBContext.setRollbackOnly() was called).



Bean-managed Transactions:
For EJB applications with bean-managed transaction demarcations, a basic transaction works in the following way:

1.  In the EJB’s deployment descriptor, the Bean Provider or Application Assembler specifies the transaction type 
    (transaction-type element) for container-managed demarcation (Bean).
2.  The client application uses JNDI to obtain an object reference to the UserTransaction object for the WebLogic 
    Server domain.
    
3.  The client application begins a transaction using the UserTransaction.begin method, and issues a request to 
    the EJB through the EJB container. All operations on the EJB execute within the scope of a transaction.
        If a call to any of these operations raises an exception (either explicitly or as a result of a communication 
  failure), the exception can be caught and the transaction can be rolled back using the UserTransaction.rollback 
  method.
        
  If no exceptions occur, the client application commits the current transaction using the UserTransaction.commit 
  method. This method ends the transaction and starts the processing of the operation. The transaction is committed 
  only if all of the participants in the transaction agree to commit.
  
4.  The UserTransaction.commit method causes the EJB container to call the transaction manager to complete the transaction.
5.  The transaction manager is responsible for coordinating with the resource managers to update any databases.



Transaction attributes control the scope of a transaction when one enterprise bean method calls another enterprise 
bean method. The JTA specification states that an enterprise bean method can be marked with one of six different 
transaction attributes in the EJB deployment descriptor. The transaction attribute indicates how the EJB container 
should treat the method called by the client enterprise bean when transactions are involved.

Transaction attributes appear in the EJB deployment descriptor as follows:
   <ejb-jar>
     ...
    <enterprise-beans>
    ... 
     </enterprise-beans>
     <assembly-descriptor>
       <container-transaction>
         <method>
           <ejb-name>BankBean</ejb-name>
           <method-intf>Remote</method-intf>
           <method-name>transferMoney</method-name>
           <method-params>
             <method-param>java.lang.String</method-param>             
             <method-param>java.lang.double</method-param>
           </method-params>
         </method>
         <trans-attribute>Required</trans-attribute>
       </container-transaction>
     </assembly-descriptor>
   </ejb-jar>

Here is what the specification says about each of the six transaction attributes:

    Required - If the client is running within a transaction and invokes the enterprise bean's method, 
        the method executes within the client's transaction. If the client is not associated with a 
        transaction, the container starts a new transaction before running the method. Most container-managed 
        transactions use Required.

    RequiresNew - If the client is running within a transaction and invokes the enterprise bean's method, 
        the container suspends the client's transaction, starts a new transaction, delegates the call to the 
        method, and finally resumes the client's transaction after the method completes. If the client is not 
        associated with a transaction, the container starts a new transaction before running the method.

    Mandatory - If the client is running within a transaction and invokes the enterprise bean's method, the 
        method executes within the client's transaction. If the client is not associated with a transaction, 
        the container throws the TransactionRequiredException. Use the Mandatory attribute if the enterprise 
        bean's method must use the transaction of the client.

    NotSupported - If the client is running within a transaction and invokes the enterprise bean's method, the 
        container suspends the client's transaction before invoking the method. After the method has completed, 
        the container resumes the client's transaction. If the client is not associated with a transaction, 
        the container does not start a new transaction before running the method. Use the NotSupported attribute 
        for methods that don't need transactions. Because transactions involve overhead, this attribute may 
        improve performance.

    Supports - If the client is running within a transaction and invokes the enterprise bean's method, the method 
        executes within the client's transaction. If the client is not associated with a transaction, the container 
        does not start a new transaction before running the method. Because the transactional behavior of the method 
        may vary, you should use the Supports attribute with caution.

    Never - If the client is running within a transaction and invokes the enterprise bean's method, the container 
        throws a RemoteException. If the client is not associated with a transaction, the container does not start 
        a new transaction before running the method.

There are two ways to Roll-back a container-managed transaction. If a system exception is thrown, the container 
automatically rolls back the transaction. You can also roll back a transaction by invoking the setRollbackOnly() 
ethod of the EJBContext interface. This instructs the container to roll back the transaction. If an enterprise bean 
throws an application exception, the rollback is not automatic, but the rollback can be initiated by a call to 
setRollbackOnly(). Note that you cannot invoke some JTA methods while using container-managed transactions. 
That's because these methods are reserved for use with bean-managed transactions. These methods are:

    Any resource-specific functions that conflict with the transactional semantics, such as the commit(), 
    setAutoCommit(), and rollback() methods of java.sql.Connection.
    
    The getUserTransaction() method of javax.ejb.EJBContext.
    
    Any method of javax.transaction.UserTransaction

In a bean-managed transaction, the code explicitly marks the boundaries of the transaction. 
When you code a bean-managed transaction you typically can use either JDBC or JTA transactions. 
A JDBC transaction is controlled by the transaction manager of the database management system, and 
not by the J2EE transaction manager. To perform a JDBC transaction, use the commit() and rollback() methods of the 
java.sql.Connection interface. 

The beginning of a transaction is generally assumed with the first SQL statement that follows the most recent commit(), 
rollback(), or connect() statement. For JTA transactions, you can invoke the begin(), commit(), and rollback() methods 
of the javax.transaction.UserTransaction interface. The begin() and commit() methods mark the transaction boundaries. 
If the transaction operations fail, an exception handler typically invokes the rollback() method, and throws an 
EJBException. The following code shows how to use the JTA javax.transaction.UserTransaction interface to perform a 
bean-managed transaction:

//All class imports
  import javax.naming.*;
  import javax.transaction.UserTransaction;
  import javax.transaction.SystemException;
  import javax.transaction.HeuristicMixedException
  import javax.transaction.HeuristicRollbackException
  import javax.transaction.NotSupportedException
  import javax.transaction.RollbackException
  import javax.transaction.IllegalStateException
  import javax.transaction.SecurityException
  import java.sql.*;
  import java.util.*;

  //Getting UserTransaction
  Context ctx = null;
  Hashtable env = new Hashtable();
  env.put(Context.INITIAL_CONTEXT_FACTORY, "weblogic.jndi.WLInitialContextFactory");
 
  //Substitute the correct hostname, port number. Also user name, and password for your environment:
  env.put(Context.PROVIDER_URL, "t3://localhost:7001"); 
  env.put(Context.SECURITY_PRINCIPAL, "Fred");
  env.put(Context.SECURITY_CREDENTIALS, "secret");
 
  ctx = new InitialContext(env);

  UserTransaction tx = (UserTransaction) ctx.lookup("java:comp/env/jdbc/customer");
  //UserTransaction ut = context.getUserTransaction();
  try {
      ut.begin();
      //Do whatever transaction functionality is necessary
      ut.commit();
  } 
  catch (Exception ex) {
      try {
         ut.rollback();
      } 
      catch (SystemException syex) { 
         throw new EJBException("Rollback failed: " + syex.getMessage());
      }
      throw new EJBException ("Transaction failed: " + ex.getMessage());
  }   

  //Or you can get a JDBC data source connection:
  Context context=new InitialContext();
  //Set context attributes
  DataSource ds=(DataSource)context.lookup("java:comp/env/jdbc/customer");
  Connection connection=ds.getConnection();
  //Now use normal JDBC operations.


The code to perform a JDBC bean-managed transaction is similar. Note, however, that the code turns off the 
auto-commit on the database connection. This way, the database treats all subsequent operations as a single 
transaction (until the code calls the commit() method) .

   try {            
        Connection con = makeDatabaseConnection(); //Using JDBC
        con.setAutoCommit(false);           
        //  Do whatever database transaction functionality
        //  is necessary           
        con.commit();          
    } 
    catch (Exception ex) {
        try {
            con.rollback();
        } catch (SQLException sqx) {
            throw new EJBException("Rollback failed: " +
                sqx.getMessage());
        }
    } 
    finally {
        releaseDatabaseConnection();
    }

Here are a few rules stated by the JTA specification:
    In a stateless session bean with bean-managed transactions, a business method must commit or roll back a 
    transaction before returning. 
    
    However, a stateful session bean does not have this restriction. In a stateful session bean with a JTA 
    transaction, the association between the bean instance and the transaction is retained across multiple 
    client calls. Even if each business method called by the client opens and closes the database connection, 
    the association is retained until the instance completes the transaction. 
    
    In a stateful session bean with a JDBC transaction, the JDBC connection retains the association between 
    the bean instance and the transaction across multiple calls. If the connection is closed, the association 
    is not retained. 

There is one method limitation with JTA bean-managed transactions: do not invoke the getRollbackOnly() and 
setRollbackOnly() methods of the EJBContext interface (these methods should be used only in container-managed 
transactions). For bean-managed transactions, invoke the getStatus() and rollback() methods of the UserTransaction 
interface instead. And, be sure not to invoke any resource-specific functions that conflict with the transactional 
semantics.
------------------------------END------------------------------------

User Defined "Connection Pool Provider" in Java

Dear reader,
Writing a blog about:
1) Creating user defined Connection Pool in Java.
2) Creating Object Pool provider.

Application wise both are same. I have created a pool of Database Connection objects
which can be considered as Object Pool. Such APIs are used in Connection Pooling, EJBs (where
session beans are shared, kept in pool and assigned to client. Once processing is done Bean is
again kept in pool). Also initialization of Connection Pool with total no of initial connections
should be done in synchronous ways. Please see below the complete program:

============ObjectPool.java START==================

import java.sql.Connection;
import java.sql.DriverManager;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class ObjectPool {

    private static Map<Connection, Boolean> poolMap=new HashMap<Connection, Boolean>();
    private Boolean connUsed=false;
    private Set<Connection> set=null;
    private Iterator<Connection> iter;
    private static final int poolSize=10;   //Making final means no more than 10 connections allowed
    Connection[] dbConn;

    public void initializePool(){
        if(poolMap!=null && poolMap.isEmpty()){
            try {
                dbConn=new Connection[poolSize]; 
                Class.forName("oracle.jdbc.OracleDriver");
                String connQuery = "jdbc:oracle:thin:@10.200.101.45:1521:obdbdev";  //obdbdev is the schema.

                //Initializing of connections should be done by only one thread..
                synchronized(this) {
                    for(int i=0;i<poolSize;i++) {
                        dbConn[i] = DriverManager.getConnection(connQuery,"nktst21","nktst21");
                        poolMap.put(dbConn[i], connUsed);
                    }
                }
                System.out.println("DB connection successful: Total connections available: "+dbConn.length);
                //System.out.println("Map contents: "+poolMap);
            }
            catch(Exception e){
                e.printStackTrace();
            }
            set=poolMap.keySet();
        }
        else
            System.out.println("Object Pool Map is already loaded with connections");
    }
    public Object getObjectFromPool(){
        Connection con=null;
        if(set!=null && !set.isEmpty()) {
            iter=set.iterator();
            while(iter.hasNext()) {
                con=(Connection)(iter.next());
                if(poolMap.get(con)==connUsed)  { //if false, means connection is not used till now
                    System.out.println("This connection is unused, returning to client: "+con);
                    poolMap.put(con,true);  //Now making this connection as used.
                    return con;
                }
            }
        }
        return con;
    }
    public void putObjectBackToPool(Object obj){
        Connection con=(Connection)obj;
        if(poolMap.get(con)==true)  { //if true, means connection is is use till now
            System.out.println("Marking this connection as ready to use again: "+con);
            poolMap.put(con, false);  //Now making this connection as used.
        }
        else
            System.out.println("Nothing is done for this connection");

    }
    public static void main(String[] args) {
        ObjectPool poolObject=new ObjectPool();
        poolObject.initializePool();

        System.out.println("Total unused connections: "+poolObject.getSizeOfUnusedConnections());
        Object conn=poolObject.getObjectFromPool();
        System.out.println("Got connection Object: "+conn);

        Object conn2=poolObject.getObjectFromPool();
        System.out.println("Got again connection Object: "+conn2);
        System.out.println("Total unused connections: "+poolObject.getSizeOfUnusedConnections());

        poolObject.putObjectBackToPool(conn2);
        System.out.println("After putting object back to Pool..");
        System.out.println("Total unused connections: "+poolObject.getSizeOfUnusedConnections());
    }
    
    public int getSizeOfUnusedConnections(){
        int unusedConnections=0;
        Connection con=null;
        if(set!=null && !set.isEmpty()) {
            iter=set.iterator();
            while(iter.hasNext()) {
                con=(Connection)(iter.next());
                if(poolMap.get(con)==false)  { //if false, means connection is not used till now
                    unusedConnections++;
                }
            }
        }
        return unusedConnections;
    }
}
//Output:
DB connection successful: Total connections available: 10
Total unused connections: 10
This connection is unused, returning to client: oracle.jdbc.driver.T4CConnection@199176
Got connection Object: oracle.jdbc.driver.T4CConnection@199176
This connection is unused, returning to client: oracle.jdbc.driver.T4CConnection@1c5dbb
Got again connection Object: oracle.jdbc.driver.T4CConnection@1c5dbb
Total unused connections: 8
Marking this connection as ready to use again: oracle.jdbc.driver.T4CConnection@1c5dbb
After putting object back to Pool..
Total unused connections: 9

============ObjectPool.java END==================

Kill a thread in Java

Dear reader, 

The topic of discussion of this article is:
    How can I kill a thread? 
    And that too without using stop() method which is a deprecated one?

After reading lot of articles I found that there are two ways we can achieve this:
1) Make a boolean flag variable which will say a thread to run or not and change the property later,
   the complete program I have written which is tested in my system.

2) By making use of Thread.interrupt() method which is more standard and I prefer to use that. However
   Thread.interrupt() doesn't stop the thread execution immediately. Interruption is a cooperative mechanism.  
   When one thread interrupts another, the interrupted thread does not necessarily stop what it is doing 
   immediately. Instead, interruption is a way of politely asking another thread to stop what it is doing 
   if it wants to, at its convenience. Again the complete program I have given.   
   
========Program 1=========
class Outer {    
    public static boolean flag = true;
    Outer() {
        new Test().start();
    } 
    class Test extends Thread { 
        public void run() {
            while(Outer.flag) {
                System.out.println("Thread is running");
            }  
        }
    }
    public static void main(String[] args) throws InterruptedException {
        Outer out=new Outer();      //Thread is running till 1000 milliseconds.
        Thread.sleep(1000);
        out.flag=false;             //Changing the boolean value, now thread will stop execution.
    }
}
//Output:
Thread is running
Thread is running
Thread is running
......
......
Thread is running
Thread is running
Now thread is stopped


========Program 2=========
public class RunningThread implements Runnable {
    long start = System.currentTimeMillis();

    public void run() {
        while (!Thread.currentThread().isInterrupted()) {
            try {
                System.out.println("Thread is running..");
                Thread.sleep(10);
            } 
            catch (InterruptedException ex) {
                System.out.println("RunningThread got Interrupted");
                System.out.println("Running time in millis: "+ (System.currentTimeMillis() - start));
                Thread.currentThread().interrupt();
            }
        }
    }

    public static void main(String[] args) {
        RunningThread rt = new RunningThread();
        Thread t = new Thread(rt);
        //Set the current main thread to sleep 2000 milli seconds and then stop the RunnableThread
        System.out.println("Starting a thread..");
        t.start();
        try {
            Thread.sleep(2000);
            t.interrupt();
        } 
        catch (InterruptedException ex) {
            ex.printStackTrace();
        }
    }
}
//Output:
Thread is running..
Thread is running..
Thread is running..
......
......
Thread is running..
Thread is running..
Thread is running..
RunningThread got Interrupted
Running time in millis: 2000

==========================Some theoritical contents=======================
More details about Interruption: below theory taken from IBM site:

Blocking methods :
When a method throws InterruptedException, it is telling you several things in addition to the fact 
that it can throw a particular checked exception. It is telling you that it is a blocking method and 
that it will make an attempt to unblock and return early -- if you ask nicely.

A blocking method is different from an ordinary method that just takes a long time to run. The completion 
of an ordinary method is dependent only on how much work you've asked it to do and whether adequate 
omputing resources (CPU cycles and memory) are available. The completion of a blocking method, on the 
other hand, is also dependent on some external event, such as timer expiration, I/O completion, or the 
action of another thread (releasing a lock, setting a flag, or placing a task on a work queue). Ordinary 
methods complete as soon as their work can be done, but blocking methods are less predictable because they 
depend on external events. Blocking methods can compromise responsiveness because it can be hard to predict 
when they will complete.

Because blocking methods can potentially take forever if the event they are waiting for never occurs, it 
is often useful for blocking operations to be cancelable. (It is often useful for long-running non-blocking 
methods to be cancelable as well.) A cancelable operation is one that can be externally moved to completion 
in advance of when it would ordinarily complete on its own. The interruption mechanism provided by Thread 
and supported by Thread.sleep() and Object.wait() is a cancellation mechanism; it allows one thread to request 
that another thread stop what it is doing early. When a method throws InterruptedException, it is telling you 
that if the thread executing the method is interrupted, it will make an attempt to stop what it is doing and 
return early and indicate its early return by throwing InterruptedException. Well-behaved blocking library 
methods should be responsive to interruption and throw InterruptedException so they can be used within 
cancelable activities without compromising responsiveness.

Thread interruption:
Every thread has a Boolean property associated with it that represents its interrupted status. The interrupted 
status is initially false; when a thread is interrupted by some other thread through a call to Thread.interrupt(), 
one of two things happens. If that thread is executing a low-level interruptible blocking method like Thread.sleep(), 
Thread.join(), or Object.wait(), it unblocks and throws InterruptedException. Otherwise, interrupt() merely sets the 
thread's interruption status. Code running in the interrupted thread can later poll the interrupted status to see 
if it has been requested to stop what it is doing; the interrupted status can be read with Thread.isInterrupted() 
and can be read and cleared in a single operation with the poorly named Thread.interrupted().

Interruption is a cooperative mechanism. When one thread interrupts another, the interrupted thread does not necessarily 
stop what it is doing immediately. Instead, interruption is a way of politely asking another thread to stop what it is 
doing if it wants to, at its convenience. Some methods, like Thread.sleep(), take this request seriously, but methods 
are not required to pay attention to interruption. Methods that do not block but that still may take a long time to 
execute can respect requests for interruption by polling the interrupted status and return early if interrupted. You 
are free to ignore an interruption request, but doing so may compromise responsiveness.

One of the benefits of the cooperative nature of interruption is that it provides more flexibility for safely constructing 
cancelable activities. We rarely want an activity to stop immediately; program data structures could be left in an 
nconsistent state if the activity were canceled mid-update. Interruption allows a cancelable activity to clean up any
work in progress, restore invariants, notify other activities of the cancellation, and then terminate. 
-------------------------------END---------------------------

Few important SQL in Oracle

Dear reader,
I am writing few sql queries in this blog article which is used for interview purposes,
I hope you will find useful. I have given table creation, seed data and all needed sql 
query for the first Question only as it will help to start. I mean from "Question 2"
onwards only necessary query has been provided. All queries I have tested on my machine.

Q.1) Given a table EMPLOYEE with data below:
    --------------
    ID    EMPNAME        MANAGERID
    110    Saikumar    114
    111    Deepak        114
    112    Srikanth    114
    113    Gudeti_Shekhar    114
    114    Sandeep        118
    115    Kotesh        118
    118    Rishi        120
    119    Khem        120
    120    Ganesh        null
    --------------
   Assuming MANAGERS are also EMPLOYEE, write a query to fetch ID, EMPNAME, MANAGERNAME.

Ans): This can be done in three ways: Either SELF JOIN, Normal JOIN operation or Sub-query.
 Writing TABLE creation and SEED DATA entry first:
--------------
    CREATE TABLE EMPLOYEE(ID NUMBER, EMPNAME VARCHAR(20), MANAGERID NUMBER);
    ALTER TABLE EMPLOYEE ADD CONSTRAINT PK_ID PRIMARY KEY (ID);

    INSERT INTO Employee VALUES(110,'Saikumar',114);
    INSERT INTO Employee VALUES(111,'Deepak',114);
    INSERT INTO Employee VALUES(112,'Srikanth',114);
    INSERT INTO Employee VALUES(113,'Gudeti_Shekhar',114);
    INSERT INTO Employee VALUES(114,'Sandeep',118);
    INSERT INTO Employee VALUES(115,'Kotesh',118);
    INSERT INTO Employee VALUES(118,'Rishi',120);
    INSERT INTO Employee VALUES(119,'Khem',120);
    INSERT INTO Employee VALUES(120,'Ganesh',null);
--------------
Fetching Query 1:
 SELECT a.id eid, a.empname empname, b.empname MANAGER FROM EMPLOYEE a, EMPLOYEE b WHERE a.managerid=b.id;

Fetching Query 2:
 SELECT A.ID, A.EMPNAME, B.EMPNAME AS MANAGER FROM EMPLOYEE A JOIN EMPLOYEE B ON A.MANAGERID = B.ID;
 
Fetching Query 3:
 SELECT A.ID,A.EMPNAME,B.EMPNAME AS MANAGER FROM
 (SELECT ID,EMPNAME,MANAGERID FROM EMPLOYEE)A,
 (SELECT ID,EMPNAME FROM EMPLOYEE)B
 WHERE A.MANAGERID=B.ID;

Output from all 3 queries:
    ID    EMPNAME            MANAGER
    113    Gudeti_Shekhar    Sandeep
    112    Srikanth        Sandeep
    111    Deepak            Sandeep
    110    Saikumar        Sandeep
    115    Kotesh            Rishi
    114    Sandeep            Rishi
    119    Khem            Ganesh
    118    Rishi            Ganesh

NOTE: Here the last inserted record where there is no manager (super boss) is not 
      showing in the output. To show such null records too, I have modified the "Fetching Query 2" 
      and added LEFT OUTER JOIN as below:
      
      SELECT A.ID, A.EMPNAME, B.EMPNAME AS MANAGER FROM EMPLOYEE A LEFT OUTER JOIN EMPLOYEE B 
      ON A.MANAGERID = B.ID;

      Now all the records will show properly. Can be fine tuned more not to show NULL values:
      
      SELECT A.ID, A.EMPNAME, NVL(B.EMPNAME,'NO MANAGER') AS MANAGER FROM EMPLOYEE A LEFT OUTER JOIN 
      EMPLOYEE B ON A.MANAGERID = B.ID;
      
    
==================================
Q.2) Write a query to find 2nd Highest salary employee.
 Table data:
  EMP_ID    EMP_NAME    EMP_SAL
    1    Anees    10000
    2    Rick    12000
    3    John    11000
    4    Stephen    13000
    5    Maria    14000
    6    Deepak    13500
    7    Rajesh    12500
Ans:)
Max Salary:  SELECT Max(emp_sal) FROM employee_test;
2nd Max salary: 
SELECT EMP_ID, emp_sal, EMP_NAME FROM employee_test WHERE emp_sal=
 (
  SELECT Max(emp_sal) FROM employee_test WHERE emp_sal IN
    (
    SELECT emp_sal FROM employee_test WHERE emp_sal< (SELECT Max(emp_sal) FROM employee_test)
    )
  );
//Output 
EMP_ID    EMP_SAL    EMP_NAME
6    13500    Deepak    
==================================

Merge Sort in Java

Dear reader,

Merge Sort is a divide and conquer algorithm. The sorting elements are stored in a collection. This 
collection is divided into two collections and these are again sorted via mergesort. Once the two 
collections are sorted then the result is combined.

Mergesort will take the middle of the collection and takes then the two collection for the next iteration 
of mergesort. In the merging part mergesort runs through the both collections and selects the lowest of 
the both to insert it into a new collection.

In comparison to quicksort the divide part is simple in mergesort while the merging take is complex. 
In addition quicksort can work "inline", e.g. it does not have to create a copy of the collection while 
mergesort requires a copy. 

Time efficiency:
Mergesort sorts in worst case in O(n log n) time. Due to the required copying of the collection, Mergesort is 
in the average case slower then Quicksort. 

===============MergeSort.java============
public class MergeSort {
    private int mArray[] = {13,4,70,12,9,4,99,120,1,3,10};
    private int[] tempArray;
    private int length;

    public void sort() {
        length = mArray.length;
        this.tempArray = new int[length];
        System.out.println("Array elements before Merge sorting:");
        for(int num:mArray)
            System.out.print(num+", ");
        mergesort(0, length - 1);
        System.out.println("\nArray elements After Merge sorting:");
        for(int num:mArray)
            System.out.print(num+", ");
    }
    public static void main(String a[]){
        new MergeSort().sort();
    }

    private void mergesort(int low, int high) {
        //Check if low is smaller then high, if not then the array is sorted
        if (low < high) {
            int middle = (low + high) / 2;
            //Sort the left side of the array
            mergesort(low, middle);
            //Sort the right side of the array
            mergesort(middle + 1, high);
            //Combine them both
            merge(low, middle, high);
        }
    }

    private void merge(int low, int middle, int high) {
        //Copy both parts into the helper array
        for (int i = low; i <= high; i++) {
            tempArray[i] = mArray[i];
        }
        int i = low;
        int j = middle + 1;
        int k = low;
        //Copy the smallest values from either the left or the right side back to the original array
        while (i <= middle && j <= high) {
            if (tempArray[i] <= tempArray[j]) {
                mArray[k] = tempArray[i];
                i++;
            } 
            else {
                mArray[k] = tempArray[j];
                j++;
            }
            k++;
        }
        //Copy the rest of the left side of the array into the target array
        while (i <= middle) {
            mArray[k] = tempArray[i];
            k++;
            i++;
        }
    }
}

//Output:
Array elements before Merge sorting:
13, 4, 70, 12, 9, 4, 99, 120, 1, 3, 10, 
Array elements After Merge sorting:
1, 3, 4, 4, 9, 10, 12, 13, 70, 99, 120, 

Other Sorting links can be found in below links: 
http://www.deepakmodi2006.blogspot.in/2012/03/quicksort-in-java.html
http://deepakmodi2006.blogspot.in/2012/03/sorting-in-java.html

===================END===================

Implementation of Java Cryptography Extension

Implementation of Java Cryptography Extension (JCE) in Programs

Dear friend, 
JCE is a huge topic in Java programming language. There are many books written on the same.
I am writing a basic example to show how it works, for complete details and loop holes please 
google it:

I will show: how do use JCE to encrypt or decrypt a text in Data Encryption Standard (DES) mechanism.

Steps to do:
1) Generate the key.
2) Create the Cipher.
3) Initialize the Cipher for Encryption using key.
4) Encrypt the text.
5) Again initialize the Cipher for Decryption using the same key.
6) Decrypt the text.

//CryptoMain.java
import java.security.InvalidKeyException;
import java.security.NoSuchAlgorithmException;

import javax.crypto.BadPaddingException;
import javax.crypto.Cipher;
import javax.crypto.IllegalBlockSizeException;
import javax.crypto.KeyGenerator;
import javax.crypto.NoSuchPaddingException;
import javax.crypto.SecretKey;

public class CryptoMain {    
    public static void main(String[] argv) {
        try {
            //Generate the Key
            KeyGenerator keygenerator = KeyGenerator.getInstance("DES");            
            SecretKey myDesKey = keygenerator.generateKey();

            //Create the cipher
            Cipher desCipher = Cipher.getInstance("DES/ECB/PKCS5Padding"); 

            // Initialize the cipher for encryption
            desCipher.init(Cipher.ENCRYPT_MODE, myDesKey);

            //sensitive information
            byte[] text = "Password_Content".getBytes();

            System.out.println("Text [Byte Format] : " + text);
            System.out.println("Text : " + new String(text));

            //Encrypt the text
            byte[] textEncrypted = desCipher.doFinal(text);

            System.out.println("Text Encrypted : " + textEncrypted);

            //Initialize the same cipher for decryption, using the same key
            desCipher.init(Cipher.DECRYPT_MODE, myDesKey);

            //Decrypt the text
            byte[] textDecrypted = desCipher.doFinal(textEncrypted);
            System.out.println("Text Decrypted : " + new String(textDecrypted));
        }
        catch(NoSuchAlgorithmException e){
            e.printStackTrace();
        }
        catch(NoSuchPaddingException e){
            e.printStackTrace();
        }
        catch(InvalidKeyException e){
            e.printStackTrace();
        }
        catch(IllegalBlockSizeException e){
            e.printStackTrace();
        }
        catch(BadPaddingException e){
            e.printStackTrace();
        } 
    }
}

//Output:
Text [Byte Format] : [B@1f585b
Text : Password_Content
Text Encrypted : [B@1f593c
Text Decrypted : Password_Content


Details about creation of cipher: Create a Cipher instance from Cipher class, specify the following 
information and separated by a slashes (/).
    a. Algorithm name
    b. Mode (optional)
    c. Padding scheme (optional)

    Cipher desCipher;
    // Create the cipher 
    desCipher = Cipher.getInstance("DES/ECB/PKCS5Padding");

Note : 
    DES = Data Encryption Standard. 
    ECB = Electronic Codebook mode.
    PKCS5Padding = PKCS #5-style padding.
In this case, you created a DES (Data Encryption Standard) cipher in Electronic Codebook mode, with 
PKCS #5-style padding.

---------------------END----------------------

Difference between ClassNotFoundException and NoClassDefFoundError in Java

Difference between ClassNotFoundException and NoClassDefFoundError in Java

Dear Reader,
Many times you might have encountered the above exceptions/errors while running your application built in
Java platform. I am explaining the difference here:

ClassNotFoundException: 
1) This is an Exception, so can be handled using Exception handling in Java.
2) ClassNotFoundException comes when JVM tries to load a class at runtime dynamically means you give the 
   name of class at runtime and then JVM tries to load it and if that class is not found in classpath it 
   throws ClassNotFoundException. 
   So this is thrown when an application tries to load a class through its string name as below:
        a) Class.forName("oracle.driver.Driver");
        b) ClassLoader.findSystemClass("class name") or ClassLoader.findClass("class name").
        c) ClassLoader.loadClass("class name").
   But no definition for the class with the specified name could be found.
3) Also remember this ClassNotFoundException is a Checked Exception, means when you write your code as 
   mentioned above "Class.forName("oracle.driver.Driver")", you must either write this code in try-catch 
   block or use throws keyword else code will not compile.
   
   Solution of this Exception: Set the classpath well.

NoClassDefFoundError:
1) This is an Error, means thrown by JVM so can't be recovered and program crashed.
2) This is basically a linkage error and comes when you create an object using "new MyClassName()" syntax.
   It means at the compilation time the class was available but at runtime it is not available.
   Or,
   Your application is using a class (assume "AA"), that uses another class (assume "BB") inside either as 
   static variable or in static method or anywhere in class "AA". Now your class "AA" is there in classpath
   but class "BB" got missed out then "NoClassDefFoundError" comes.

Example: Now writing complete code for getting above both exception/errors:
1) ClassNotFoundException: 
------------------------------------
    //ClassNotFound.java
    public class ClassNotFound {
        public static void main(String[] args) throws Exception {
            Class c = Class.forName("modi.driver.MyDriver");     //Sample user defined driver name 
        }
    }

    //The above program will compile well, I have declared throws Exception too.
    //But at run time you will get below exception:
    E:\My Workspace\NoClassDefFoundError\src>java ClassNotFound
    Exception in thread "main" java.lang.ClassNotFoundException: modi.driver.MyDriver
            at java.net.URLClassLoader$1.run(URLClassLoader.java:200)
            at java.security.AccessController.doPrivileged(Native Method)
            at java.net.URLClassLoader.findClass(URLClassLoader.java:188)
            at java.lang.ClassLoader.loadClass(ClassLoader.java:306)
            at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:268)
            at java.lang.ClassLoader.loadClass(ClassLoader.java:251)
            at java.lang.ClassLoader.loadClassInternal(ClassLoader.java:319)
            at java.lang.Class.forName0(Native Method)
            at java.lang.Class.forName(Class.java:164)
            at ClassNotFound.main(ClassNotFound.java:3)
------------------------------------

2) NoClassDefFoundError:
Steps: 
    a. Write a program
    b. Compile it and run it. It will run well.
    c. Delete a class after compilation done, here inner class is deleted.
    d. Run the program again. You will see error.

------------------------------------
//MainProgram.java   
public class MainProgram {
    static class b {}
    public static void main(String args[]) {
        System.out.println("First attempt new b():");
        try {
            new b(); 
        } 
        catch(Throwable t) {
            t.printStackTrace();
        }
        System.out.println("\nSecond attempt new b():");
        try {
            new b(); 
        }
        catch(Throwable t) {
            t.printStackTrace();
        }
    }
}

//Compiling the Java code
E:\My Workspace\NoClassDefFoundError\src>javac MainProgram.java
//Once program is compiled, we will have below classes in the src directory:
Directory of E:\My Workspace\NoClassDefFoundError\src
03/09/2012  08:58 PM               250 MainProgram$b.class
03/09/2012  08:58 PM               676 MainProgram.class
03/09/2012  08:57 PM               362 MainProgram.java

//Running the Java code
E:\My Workspace\NoClassDefFoundError\src>java MainProgram
First attempt new b():

Second attempt new b():

//Deleting the inner class "MainProgram$b.class"
E:\My Workspace\NoClassDefFoundError\src>del MainProgram$b.class

//Now directory contains below files:
E:\My Workspace\NoClassDefFoundError\src>dir
Directory of E:\My Workspace\NoClassDefFoundError\src
03/09/2012  08:58 PM               676 MainProgram.class
03/09/2012  08:57 PM               362 MainProgram.java
--------Removed "MainProgram$b.class"----------

//Running the Java code again
E:\My Workspace\NoClassDefFoundError\src>java MainProgram
First attempt new b():
java.lang.NoClassDefFoundError: MainProgram$b
        at MainProgram.main(MainProgram.java:6)

Second attempt new b():
java.lang.NoClassDefFoundError: MainProgram$b
        at MainProgram.main(MainProgram.java:13)
E:\My Workspace\NoClassDefFoundError\src>
------------------------------------

That's it. Dear reader, if still there is a confusion, please drop a question, I will reply.

How HashMap works in Java

Dear reader, 
I have mentioned below topics in this blog article:
1) How HashMap works in Java.
2) Difference between HashMap and HashTable. 
3) At the end few programs having implementation of equals() and hashCode() method
   and impact of these methods on HashMap storage.

How HashMap works in Java is a very common question. Almost everybody who worked 
in Java knows what hashMap is, where to use hashMap or difference between 
hashTable and HashMap, then why this interview question becomes so special? Because of the breadth and depth 
this question offers. It has become very popular java interview question in almost any senior or mid-senior 
level java interviews.

Questions start with simple statement:
"Have you used HashMap before" or "What is HashMap? Why do we use it“
Almost everybody answers this with yes and then interviewee keep talking about common facts about HashMap like 
HashMap accept null while hashTable doesn't, HashMap is not synchronized, hashMap is fast and so on along with 
basics like its stores key and value pairs etc.
This shows that person has used HashMap and quite familiar with the functionality HashMap offers but interview 
takes a sharp turn from here and next set of follow up questions gets more detailed about fundamentals involved 
in HashMap. Interview here you and come back with questions like

"Do you Know how HashMap works in Java” or "How does get () method of HashMap works in Java"
And then you get answers like I don't bother its standard Java API, you better look code on java; I can find 
it out in Google at any time etc.
But some interviewee definitely answer this and will say "HashMap works on principle of hashing, we have put() 
and get() method for storing and retrieving data from HashMap. When we pass an object to put () method to store 
it on HashMap, HashMap implementation calls hashcode() method HashMap key object and by applying that hashcode on 
its own hashing function it identifies a bucket location for storing value object , important part here is HashMap 
stores both key+value in bucket which is essential 
to understand the retrieving logic. if people fails to recognize this and say it only stores Value in the bucket they 
will fail to explain the retrieving logic of any object stored in HashMap . This answer is very much acceptable and 
does make sense that interviewee has fair bit of knowledge how hashing works and how HashMap works in Java.
But this is just start of story and going forward when depth increases a little bit and when you put interviewee on 
scenarios every java developers faced day by day basis. So next question would be more likely about collision 
detection and collision resolution in Java HashMap e.g 

"What will happen if two different objects have same hashCode?”
Now from here confusion starts some time interviewer will say that since hashCode is equal objects are equal and 
HashMap will throw exception or not store it again etc. then you might want to remind them about equals and hashCode() 
contract that two unequal object in Java very much can have equal hashCode. Some will give up at this point and some 
will move ahead and say "Since hashCode () is same, bucket location would be same and collision occurs in HashMap, 
Since HashMap uses a linked list to store in bucket, value object will be stored in next node of linked list." 
Great this answer make sense to me though there could be some other collision resolution methods available this is 
simplest and HashMap does follow this. See the program at the end of this article.

But story does not end here and final questions interviewer ask like:
"How will you retrieve if two different objects have same hashcode?”
Hmmmmmmmmmmm
Interviewee will say we will call get() method and then HashMap uses keys hashCode to find out bucket location and 
retrieves object but then you need to remind him that there are two objects are stored in same bucket , so they will 
say about traversal in linked list until we find the value object , then you ask how do you identify value object 
because you don't value object to compare ,So until they know that HashMap stores both Key and Value in linked list 
node they won't be able to resolve this issue and will try and fail.

But those bunch of people who remember this key information will say that after finding bucket location , we will call 
keys.equals() method to identify correct node in linked list and return associated value object for that key in Java 
HashMap. Perfect this is the correct answer.

In many cases interviewee fails at this stage because they get confused between hashcode() and equals() and keys and 
values object in hashMap which is pretty obvious because they are dealing with the hashcode() in all previous questions 
and equals() come in picture only in case of retrieving value object from HashMap.
Some good developer point out here that using immutable, final object with proper equals() and hashcode() 
implementation would act as perfect Java HashMap keys and improve performance of Java hashMap by reducing collision. 
Immutability also allows caching there hashcode of different keys which makes overall retrieval process very fast and 
suggest that String and various wrapper classes e.g Integer provided by Java Collection API are very good HashMap keys.

Now if you clear all this java hashmap interview question you will be surprised by this very interesting question 
"What happens On HashMap in Java if the size of the Hashmap exceeds a given threshold defined by load factor ?". 
Until you know how hashmap works exactly you won't be able to answer this question.
if the size of the map exceeds a given threshold defined by load-factor e.g. if load factor is .75 it will act to 
re-size the map once it filled 75%. Java Hashmap does that by creating another new bucket array of size twice of 
previous size of hashmap, and then start putting every old element into that new bucket array and this process is 
called rehashing because it also applies hash function to find new bucket location. 

If you manage to answer this question on hashmap in java you will be greeted by "do you see any problem with resizing 
of hashmap in Java", you might not be able to pick the context and then he will try to give you hint about multiple 
thread accessing the java hashmap and potentially looking for race condition on HashMap in Java. 

So the answer is Yes there is potential race condition exists while resizing hashmap in Java, if two thread at the same 
time found that now Java Hashmap needs resizing and they both try to resizing. on the process of resizing of hashmap in 
Java, the element in bucket which is stored in linked list get reversed in order during there migration to new bucket 
because java hashmap doesn't append the new element at tail instead it append new element at head to avoid tail traversing. 
If race condition happens then you will end up with an infinite loop. though this point you can potentially argue that 
what the hell makes you think to use HashMap in multi-threaded environment to interviewer :). 
Never use it in multithreaded env. For MultiThreaded use ConcurrentHashMap.

I like this question because of its depth and number of concept it touches indirectly, if you look at questions asked 
during interview this HashMap questions has verified:
    Concept of hashing
    Collision resolution in HashMap
    Use of equals () and hashCode () method and there importance?
    Benefit of immutable object?
    race condition on hashmap in Java
    Resizing of Java HashMap

Just to summarize here are the answers which does makes sense for above questions:
How HashMAp works in Java
HashMap works on principle of hashing, we have put() and get() method for storing and retrieving object form hashMap.
When we pass an both key and value to put() method to store on HashMap, it uses key object hashcode() method to calculate 
hashcode and they by applying hashing on that hashcode it identifies bucket location for storing value object.
While retrieving it uses key object's equals method to find out correct key value pair and return value object associated 
with that key. HashMap uses linked list in case of collision and object will be stored in next node of linked list.
Also hashMap stores both key+value tuple in every node of linked list.

What will happen if two different HashMap key objects have same hashcode?
They will be stored in same bucket but no next node of linked list. And keys equals() method will be used to identify 
correct key value pair in HashMap.

In terms of usage HashMap is very versatile and can be mostly used hashMap as cache in electronic trading application. 
Since finance domain used Java heavily and due to performance reason we need caching a lot, HashMap comes very handy there.

For new insertions, If key is same i.e. equals by equals method in Java than hashcode would be same and value will be 
replaced but if key is not same i.e. not equal but hashcode is same (Which is possible in java) than bucked location 
would be same and collision would happen and second object will be stored on second node of linked list structure 
on Map. 

So key.equals() is used on both put() and get() method call if object already exits in bucked location on hashmap 
and that's why tuples contains both key and value in each node. In Java Object helpfully provides hashCode() and equals() 
so we know that any object will be usable as a key in a hashtable.

So the known risks when using HashMap data structure in multithreaded env are: HashMap internal index corruption 
and infinite looping, which can bring your JVM to its knees.

What JDK Map data structure is more suitable to handle concurrent read & write operations in a Java EE environment?
The answer is to use the ConcurrentHashMap, introduced in JDK 1.5, which provides Thread safe operations but no 
blocking get() operation; which is key for proper performance. This is the typical data structure used these 
days in modern Java EE container implementations.

JDK 1.5 introduce some good concurrent collections which is highly efficient for high volume, low latency system.

The synchronized collections classes, Hashtable and Vector, and the synchronized wrapper classes, 
Collections.synchronizedMap and Collections.synchronizedList, provide a basic conditionally thread-safe implementation 
of Map and List.
However, several factors make them unsuitable for use in highly concurrent applications -- their single collection-wide 
lock is an impediment to scalability and it often becomes necessary to lock a collection for a considerable time during 
iteration to prevent ConcurrentModificationExceptions.

The ConcurrentHashMap and CopyOnWriteArrayList implementations provide much higher concurrency while preserving thread 
safety, with some minor compromises in their promises to callers. ConcurrentHashMap and CopyOnWriteArrayList are not 
necessarily useful everywhere you might use HashMap or ArrayList, but are designed to optimize specific common situations. 
Many concurrent applications will benefit from their use.

So what is the difference between hashtable and ConcurrentHashMap , both can be used in multithreaded environment but 
once the size of hashtable becomes considerable large performance degrade because for iteration it has to be locked 
for longer duration.

Since ConcurrentHashMap indroduced concept of segmentation , how large it becomes only certain part of it get locked 
to provide thread safety so many other readers can still access map without waiting for iteration to complete.

In Summary ConcurrentHashMap only locked certain portion of Map while Hashtable lock full map while doing iteration.

HashMap can be synchronized by:
 Map m = Collections.synchronizeMap(hashMap);
 
Difference between HashMap and HashTable? 
1. The HashMap class is roughly equivalent to Hashtable, except that it is non synchronized and permits nulls. 
   (HashMap allows null values as key and value whereas Hashtable doesn't allow nulls).
2. HashMap does not guarantee that the order of the map will remain constant over time.
3. HashMap is non synchronized whereas Hashtable is synchronized.
4. Iterator in the HashMap is  fail-fast  while the enumerator for the Hashtable is not and throw 
ConcurrentModificationException if any other Thread modifies the map structurally  by adding or removing any 
element except Iterator's own remove()  method. But this is not a guaranteed behavior and will be done by 
JVM on best effort.
5) HashTable extends Dictionary interface which is quite old while hashmap extends Map interface.
6) hashtalbe doesn't have counterpart like ConcurrentHashMap.

Note on Some Important Terms:
1)Synchronized means only one thread can modify a hashtable at one point of time. Basically, it means that 
any thread before performing an update on a hashtable will have to acquire a lock on the object while others 
will wait for lock to be released.

2)Fail-safe is relevant from the context of iterators. If an iterator has been created on a collection object 
and some other thread tries to modify the collection object "structurally", a concurrent modification exception
will be thrown. It is possible for other threads though to invoke "set" method since it doesn't modify the 
collection "structurally". However, if prior to calling "set", the collection has been modified structurally, 
"IllegalArgumentException" will be thrown.

3)Structurally modification means deleting or inserting element which could effectively change the structure 
of map.


=================Other important points about use of Map============
1) If the Class's object which is getting stored in Map, overrites equals() and hashCode() method and
   hashCode() returns a fixed value like "45" or "10" and equals() return "true" for all cases as explained 
   in below coding then Map objects will be considered as Duplicate, so only one Pair will be shown as output.
   Check the MainMap.java program below:

//Person.java (overriding equals() and hashCode() method
public final class Person {
    final String name;
    public Person(String name){
        this.name=name;
    }
    @Override
    public boolean equals(Object obj) {
        //return super.equals(obj);
        return true;
    }
    @Override
    public int hashCode() {
        return 45;
    }
}

===========
//MainMap.java
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class MainMap {
    public static void main(String[] args) {
        Person a=new Person("John");
        Person b=new Person("Deepak");
        Person c=new Person("John");
        Person d=new Person("John");

        System.out.println("a.hashCode():"+a.hashCode());
        System.out.println("b.hashCode():"+b.hashCode());
        System.out.println("c.hashCode():"+c.hashCode());
        System.out.println("d.hashCode():"+d.hashCode());

        HashMap map=new HashMap();
        map.put(a,"John");
        map.put(b, "Deepak");
        map.put(c,"John");
        System.out.println("Map contents: "+map);

        System.out.println("Trying to get object \"d\" : "+map.get(d));

        Set s=new HashSet();
        s.add(a);
        s.add(b);
        s.add(c);
        System.out.println("Set containing Person objects :"+s);
        //System.out.println(s.get(d)); //get method is not allowed in Set.
        System.out.println("Does Set contains Person d object \"d\": "+s.contains(d));  //false

        s.clear();
        Integer intObj1=new Integer("0");
        Integer intObj2=new Integer("0");
        s.add(intObj1);
        s.add(intObj2);
        System.out.println("Set containing Integer objects :"+s);

        s.clear();
        String stringObj1=new String("0");
        String stringObj2=new String("0");
        s.add(stringObj1);
        s.add(stringObj2);
        System.out.println("Set containing String objects :"+s);


        s.clear();
        StringBuffer stringBuffObj1=new StringBuffer("0");
        StringBuffer stringBuffObj2=new StringBuffer("0");
        s.add(stringBuffObj1);
        s.add(stringBuffObj2);
        System.out.println("Set containing StringBuffer objects :"+s);
        
        s.clear();
        Thread threadObj1=new Thread("0");
        Thread threadObj2=new Thread("0");
        s.add(threadObj1);
        s.add(threadObj2);
        System.out.println("Set containing Thread objects :"+s);
    }
}
==========
//Output:
a.hashCode():45
b.hashCode():45
c.hashCode():45
d.hashCode():45
Map contents: {Person@2d=John}   //Map shows only one entry.
Trying to get object "d" : John  //Value is printed, even though we have not copied this value to Map.
Set containing Person objects :[Person@2d]   //Set shows only one entry.
Does Set contains Persond object "d": true
Set containing Integer objects :[0]
Set containing String objects :[0]
Set containing StringBuffer objects :[0, 0]
Set containing Thread objects :[Thread[0,5,main], Thread[0,5,main]]


******************
However if you change the equals() method like below:
    @Override
    public boolean equals(Object obj) {
        return super.equals(obj);
        //return true;
    }

//Output:
a.hashCode():45   //Our defined hashCode
b.hashCode():45
c.hashCode():45
d.hashCode():45
Map contents: {Person@2d=John, Person@2d=Deepak, Person@2d=John} //Map shows 3 entries
Trying to get object "d" : null   //Null is printed.
Set containing Person objects :[Person@2d, Person@2d, Person@2d] //Set shows 3 entries
Does Set contains Persond object "d": false
Set containing Integer objects :[0]
Set containing String objects :[0]
Set containing StringBuffer objects :[0, 0]
Set containing Thread objects :[Thread[0,5,main], Thread[0,5,main]]

******************
Also if you change the equals() and hashCode() method like below:
    @Override
    public boolean equals(Object obj) {
        return super.equals(obj);
        //return true;
    }
    @Override
    public int hashCode() {
        return name.hashCode();
    }
//Output:
a.hashCode():2314539   //System defined hashCode.
b.hashCode():2043177526
c.hashCode():2314539
d.hashCode():2314539
Map contents: {Person@79c86a36=Deepak, Person@23512b=John, Person@23512b=John}  //Map shows 3 entries
Trying to get object "d" : null   //Null is printed.
Set containing Person objects :[Person@79c86a36, Person@23512b, Person@23512b]  //Set shows 3 entries
Does Set contains Persond object "d": false
Set containing Integer objects :[0]
Set containing String objects :[0]
Set containing StringBuffer objects :[0, 0]
Set containing Thread objects :[Thread[0,5,main], Thread[0,5,main]]

******************
Also if you change the equals() and hashCode() method like below:
    @Override
    public boolean equals(Object obj) {        
        return true;
    }
    @Override
    public int hashCode() {
        return name.hashCode();
    }    

//Output:
a.hashCode():2314539
b.hashCode():2043177526
c.hashCode():2314539
d.hashCode():2314539
Map contents: {Person@79c86a36=Deepak, Person@23512b=John}   //Map shows 2 entries with different name.
Trying to get object "d" : John        //Value is printed, even though we have not copied this value to Map.
Set containing Person objects :[Person@79c86a36, Person@23512b] //Set shows 3 entries
Does Set contains Persond object "d": true
Set containing Integer objects :[0]
Set containing String objects :[0]
Set containing StringBuffer objects :[0, 0]
Set containing Thread objects :[Thread[0,5,main], Thread[0,5,main]]

======================END=================

Running Time Analysis (Big O notation)

Running Time Analysis
Running Time Analysis (Big O notation)

"Big O" notation is the language we use for articulating how long an algorithm takes to run. It is a way to compare the efficiency 
of different solutions/algorithms to a problem. However "Big O" represents the worst case analysis means "The supposed algorighm
can't be slower than this upper bound time".
This means: Algo_Running_Time <= c(f(n)). Where c is some variable for all input size "n".

There are other representations too for asymptotic analysis:
    Big-O :     represents worst case analysis, upper bound of running time (Running_Time <= c(f(n))). See proper definition below.    
    
    Big-Theta : represents average case but not exactly (c1f(n) <= Algo_Running_Time <= c2f(n) where c1 and c2 are some variables for all n).
                Big Theta says that the running time of our algorithm is bounded ABOVE AND BELOW by some multiple of f(n). See proper definition below.        
    
    Big-Omega : represents best case. This is the Lower bound of running time. See proper definition below.    
    
Again the definition of above asymptotic notations:
    Big-O : The function g(n) is O(f(n)) if there exists a positive real constant c and a positive integer n0 such that g(n) ≤ cf(n) for all n > n0.
    Big-Ω : The function g(n) is Ω(f(n)) if there exists a positive real constant c and a positive integer n0 such that g(n) ≥ cf(n) for all n > n0.
    Big-Θ : The function g(n) is Θ(f(n)) if there exists two positive real constants c1 and c2 and a positive integer n0 such that c1f(n) ≤ g(n) ≤ c2f(n) for all n > n0.    


As a programmer, we focus for the worst case scenario. Big-O analysis is very useful as it helps a programmer to predict an algorithm's 
running time without having to implement it and run benchmarks.

======================================================
Examples:
1) O(1) : Below function runs in O(1) time (or "Constant time") relative to its input. The input array could be 1 item or 1000 items, 
          but this function would just require just one "step."

          public void printFirst(int[] arrayOfItems) {
            System.out.println(arrayOfItems[0]);
          }

2) O(n) : Below function runs in O(n) time (or "Linear time") where "n" is the number of items in array. If the array has 10 items, 
          we have to print 10 times. If it has 1000 items, we have to print 1000 times.

          public void printAll(int[] arrayOfItems) {
            for (int item : arrayOfItems) {  //This will run number of times of size of array
                System.out.println(item);   
            }
          }

3) O(n^2) : Below function runs in O(n^2). Here we are nesting two loops. If our array has "n" items, our outer loop runs "n" times and 
            our inner loop runs "n" times for each iteration of the outer loop, giving us as n*n = n^2.
​            O(n^2) is also called "Quadratic time". If the array has 10 items, we have to print 100 times. If has 1000 items, we have to print 1000000 times.

            public void printAllOrderedPairs(int[] arrayOfItems) {
                for (int firstItem : arrayOfItems) {
                    for (int secondItem : arrayOfItems) {
                        int[] orderedPair = new int[]{firstItem, secondItem};
                        System.out.println(Arrays.toString(orderedPair));
                    }
                }
            }

4) NOTE: While computing run time in Big O notation, we ignores the constants values. See below:
        
        public void printAllThenAllPairSums(int[] arrayOfNumbers) {
            System.out.println("These are the numbers:");
            for (int number : arrayOfNumbers) {   // O(n)
                System.out.println(number);
            }
        
            System.out.println("And these are their consecutive sums:");
            for (int firstNumber : arrayOfNumbers) {  // O(n)
                for (int secondNumber : arrayOfNumbers) {  // O(n)
                    System.out.println(firstNumber + secondNumber);  //This line will execute O(n^2) times.
                }
            }
        }
        ---------
    Here our runtime is O(n + n^2). Which we just call O(n^2).
    Even if it was O(n^2/2 + 100n), it would still be O(n^2). This is because as "n" reaches towards infinity, other constants has no role.

    Similarly:
    O(n^3 + 50n^2 + 10000) ===> O(n​3​​ +50n​2​​ +10000) ===> is O(n^3) 
    O((n + 30) * (n + 5))  ===> O((n+30)(n+5))     ===> is O(n^2)

5) O(2^N) :  O(2^N) Denotes an algorithm whose growth doubles with each additon to the input data set. The growth curve of an O(2^N) function is 
             exponential. It starts very shallow, then rising meteorically. 
             An example of an O(2^N) function is the recursive calculation of Fibonacci numbers:

        int Fibonacci(int number){
            if (number <= 1) return number;
            return Fibonacci(number - 2) + Fibonacci(number - 1);
        }

---------------------------------------    

Common Running Times and Scenarios:
---------------------------------------
O(1)        Insertion and deletion for arrays due to random access.
            Insertion and deletion of the head element in linked lists.
            Insertion and deletion of the root element in heaps.
        
O(log [n])  Binary search in arrays (search in sorted array, it is actually "log [n]" with base 2 as binary search divides items by 2).
            Insertion, deletion, and balancing of binary search trees (all are divide by 2).

O(n)        Linked list traversal. 
            Linear Search opeations.
            
O(nlog[n])  Merge Sort, Quick Sort (best and average case).
O(n^2)      Shell Sort, Insertion/Selection Sort, Bubble Sort, Quick Sort (worst case).

O(2^n)      Very bad. Finding the (exact) solution to the travelling salesman problem using dynamic programming, Recursive Fibonacci Series.
O(n!)       Solving the traveling salesman problem via brute-force search, Permutation..
---------------------------------------

Big-O follows a hierarchy that goes something like this:
    O(1) < O(log[n]) < O(n) < O(n*log[n]) < O(n^2) < O(2^n) < O(n!)   (Here 2 can be any number greater than 1 for O(n^2) and O(2^n)).

    
Graph of running time for various common Big O algorithm:
Will upload later... not able to upload.. Image1

Will upload later... not able to upload.. Image2
-----------------------------END-----------------------------

SinglyLinkedList Algorithm in Java

A Singly Linked List, in its simplest form, is a collection of nodes that together form a linear ordering.
    A node has two parts: Element and Pointer (or Data and Reference).
    Each element in the node represents DATA_VALUE of that Node. The Pointer of each node has reference to another Node 
    like STEPS of a LADDER. So NULL Pointer means a TAIL Node, that means End of Linked list. Moving from one node to 
    another by following a next reference is known as Link hopping or Pointer hopping. The first and last node of a linked 
    list usually are called the head and tail of the list. Also remember DATA_VALUE can be anything like a "Person" Object 
    having many attributes or any Wrapper class object.

LinkedList Program:

-----------------------------------------------------------
package datastructure.linkedlist;
//Author Deepak Kumar Modi
public class Node {
    public int data;
    public Node next;
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
    public String toString(){
        return data+"";
    }
}
-----------------------------------------------------------
package datastructure.linkedlist;
//Author Deepak Kumar Modi
public class SinglyLinkedList {
    public Node start;  //means header node
    public int size;
    
    public SinglyLinkedList(){
        start=null;   //start means header node
        size=0;
    }
    public void addAtFirst(int number){
        Node temp=new Node();
        temp.setData(number);  //Make temp new node
        if(size==0){           //List is empty, create head node
            temp.setNext(null);  //Make first node, so reference is null.
            start=temp;          //make temp as header node
        }else{
            temp.setNext(start);    //new node is complete now with pointing to header       
            start=temp;             //make new node as header 
        }
        size++;
    }
    public void addAtEnd(int number){
        Node temp=new Node();
        temp.setData(number);       //temp is new node
        
        if(size==0){                //List is empty, create head node
            temp.setNext(null);
            start=temp;
        }else{  
            Node tempHead=start;        //store header node "start" to a temp node as "tempHead"
            while(start.getNext()!=null){
                start=start.getNext();
            }
            start.setNext(temp);   //temp.setNext will be null by default.
            start=tempHead;        //Since start pointer has moved to the end, store the old tempHead node to start again.
        }
        size++;
    }
    
    public Node getNodeAt(int nodePos) {
        if(nodePos>=size || nodePos<0){
            return null;
        }
        Node temp = start; //Move start pointer to front
        for(int counter=0; counter<nodePos; counter++){
            temp = temp.next;  //Move till the node position
        }
        return temp;
    }
    public void removeAtPosition(int position) {
        System.out.println("\nRemoving from position: "+position);
        Node temp = getNodeAt(position-1);            
        temp.setNext(temp.getNext().getNext());  //here temp.getNext() is getting removed/reference removed from LinkedList.
        size--;
    }
    public void reverseList() {
        System.out.println("\nReversing the List now.");
        if(size<=1){
            System.out.println("Not required, only one Node.");
        }
        Node previousNode = null; 
        Node currentNode = start; 
        Node nextNode = null;
        
        while(currentNode.next != null) {
            nextNode = currentNode.next;
            currentNode.next = previousNode;
            previousNode = currentNode;
            currentNode = nextNode;
        }
        currentNode.next = previousNode;
        start = currentNode;
    }
    
    public Node getFirst(){
        return getNodeAt(0);
    }

    public Node getLast(){
        return getNodeAt(size-1);
    }

    public boolean contains(int number){
        Node temp = start; //Move pointer to front
        for(int counter=0;counter<size;counter++){
            if(temp.getData()==number)
                return true;
            temp = temp.next;
        }
        return false;
    }
    public void clear(){    
        System.out.println("\nRemoving all the elements in the List: "+size);
        start = null;
        size=0;
    }
    public void displayList(){    
        Node temp=start;  //Save start into a temp Variable
        if(size>0)
            System.out.println("Size: "+size);
        else
            System.out.println("No elements to display.");
        
        for(int i=0;i<size && temp!=null;i++){
            System.out.print(temp.getData()+", ");
            temp=temp.getNext();
        }
    }
}
----------

package datastructure.linkedlist;
//Author Deepak Kumar Modi
public class SinglyLinkedListTest {
    public static void main(String a[]){
        SinglyLinkedList list=new SinglyLinkedList();
        System.out.println("Adding at Begining...");
        list.addAtFirst(10); list.addAtFirst(60);  list.addAtFirst(3); list.addAtFirst(2); list.addAtFirst(70);
        list.displayList(); 
        System.out.println("\nlist.getNodeAt(3): "+list.getNodeAt(3));
        list.clear();
        list.displayList();
        
        System.out.println("\nAdding at End...");
        list.addAtEnd(10);   list.addAtEnd(60);    list.addAtEnd(3);   list.addAtEnd(2);   list.addAtEnd(70);
        list.displayList();
        
        list.reverseList();
        list.displayList();        
        
        System.out.println("\nGet Last Element: list.getLast(): "+list.getLast());
        System.out.println("\nContent Check: list.contains(3): "+list.contains(3));
        System.out.println("Content Check: list.contains(13): "+list.contains(13));
        
        System.out.println("\nNode Check: list.getNodeAt(3): "+list.getNodeAt(3));
        System.out.println("Node Check: list.getNodeAt(10): "+list.getNodeAt(10));
        
        list.removeAtPosition(3);
        list.displayList();
        System.out.println("\nNode Check: list.getNodeAt(3): "+list.getNodeAt(3));
    }
}
-----------------------------------
//Output:
Adding at Begining...
Size: 5
70, 2, 3, 60, 10, 
list.getNodeAt(3): 60

Removing all the elements in the List: 5
No elements to display.

Adding at End...
Size: 5
10, 60, 3, 2, 70, 
Reversing the List now.
Size: 5
70, 2, 3, 60, 10, 
Get Last Element: list.getLast(): 10

Content Check: list.contains(3): true
Content Check: list.contains(13): false

Node Check: list.getNodeAt(3): 60
Node Check: list.getNodeAt(10): null

Removing from position: 3
Size: 4
70, 2, 3, 10, 
Node Check: list.getNodeAt(3): 10
-----------------------------------------------------------
Another useful algorithm for Singly Linked List:
Practice Question: Determine whether a linked list contains a cycle.
    
Ans: Traversal of a linked list with a cycle will never end, so there needs to be some method to keep track 
    of what nodes have been encountered. One idea is to mark nodes that have been seen, either by adding a flag 
    to the node itself or storing information about the node in a separate data structure. Unfortunately, this 
    method requires modification of the node and/or additional space.

    With linked list problems, the solution usually takes advantage of multiple pointers. How can we use another 
    pointer to help us out? The previous problem advanced two pointers at a fixed interval between each other, 
    but that doesn’t seem to help. A better idea is to advance the pointers at two different speeds.

    One pointer will travel at twice the speed of the other, so in an acyclic list, the fast one will reach the end. 
    However, in a cyclic list, both pointers loop endlessly, but the faster pointer will lap the slower pointer at 
    some point, so if the faster pointer ever catches up to the slower pointer, the list has a cycle.

    To make one pointer “faster” than the other, just advance it two nodes instead of one. However, be aware of null 
    pointers.

The running time for this algorithm is O(n). For the ACYCLIC case, the faster pointer will reach the last node 
after traversing the entire list. For the CYCLIC case, the slower pointer will only go around a loop at most once, 
and the faster pointer will only go through a loop at most twice, so in the worst case 3n nodes are examined, which 
is still an O(n) algorithm. 

Code:
----------------
public static boolean hasCycle(Node head) {
    Node fast = head;
    Node slow = head;
 
    while (fast != null && slow != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
 
        if (slow == fast) {
            return true;
        }
    } 
    return false;
}
==================END=======================

Linear / Sequential Search and Binary Search in Java

=================Linear Search================
Start from the leftmost element of arr[] and one by one compare x with each element of arr[], if x matches 
with an array element, return the index/location. If x doesn’t match with any of elements, return -1. Array
need not be in Sorted order.

//LinearSearch.java
package array;
public class LinearSearch {
    public static void main(String[] args) {
        int array[]={1,4,6,7,9,12,34,56,78,90};

        System.out.println(search(array,5));  // -1
        System.out.println(search(array,4));  //  1
        System.out.println(search(array,90)); //  9
    }
    public static int search(int arr[], int x){
        int i;
        for (i=0; i<arr.length; i++)
            if (arr[i] == x)
                return i;
        return -1;
    }
}

The time complexity of above algorithm is O(n).

=================Binary Search================
The idea of binary search is to use the information that the array is sorted and reduce the time 
complexity is O(Logn). We basically ignore half of the elements just after one comparison.
1) Compare x with the middle element.
2) If x matches with middle element, we return the mid index.
3) Else If x is greater than the mid element, then x can only lie in right half sub-array after the 
   mid element. So we do recursion for right half.
4) Else (x is smaller) do recursion for the left half.

//BinarySearch.java
package array;
import java.util.Arrays;
public class BinarySearch {
    static int ARRAY_UNORDERED = -2;

    public static void main(String[] args) {
        int[] array= {2,3,45,65,31,32,90,5,6,9};
        int x=5;
        
        Arrays.sort(array);
        System.out.print("Elements After Sorting :");
        for(int i=0;i<array.length;i++) {
            System.out.print(array[i]+", ");
        }
        
        //Calling binarySearch method
        int element=binarySearch(array,0,array.length-1,x);
        
        System.out.println("\nPlace Of Element In Array: "+element);
    }
    static int binarySearch(int[] array, int lower, int upper, int target ){
        int center=0;        
        
        if( array[lower] > array[upper] )
            return ARRAY_UNORDERED;
        
        center = lower+ (upper-lower)/2;

        if( target == array[center] ){
            return center;
        } 
        else if( target < array[center] ){
            return binarySearch( array, lower, center - 1, target );  //Calling binarySearch() recursively
        } 
        else {
            return binarySearch( array, center + 1, upper, target );  //Calling binarySearch() recursively
        }
    }
}
//Output:
Elements After Sorting :2, 3, 5, 6, 9, 31, 32, 45, 65, 90, 
Place Of Element In Array: 2

Performance: A binary search is O(log(n)) because half of the search is eliminated on each iteration.      

Selection, Bubble, Insertion Sort in Java

Dear reader,

I am writing here 3 Sorting algorithms for an Array/Collection elements:
1. Selection Sort
2. Exchange Sort (Also called Bubble Sort)
3. Insertion Sort.

Other two important sorting algorithms are Quick Sort and Merge Sort. Quick Sort I have discussed
at this link: http://www.deepakmodi2006.blogspot.in/2012/03/quicksort-in-java.html

However I have not written Merge Sort till now. Will write later.

If you already know the logics of Selection, Bubble and Insertion Sort, please go at the end
of the blog, a full program I have written in a very lucid manner else go line by line.

---------------------------------------------------
Selection Sort: In selection sort algorithm we find the minimum value in the array. First assign 
minimum index in key (index_of_min=x). Then find the minimum value and assign the index of minimum 
value in key (index_of_min=y). Then swap the minimum value with the value of minimum index. 
At next iteration leave the value of minimum index position and sort the remaining values by following 
same steps.
It is simplest algorithm.

Time efficiency:
The complexity of selection sort algorithm is in worst-case, average-case, and best-case run-time of O(n2), 
assuming that comparisons can be done in constant time.  

//sArray[]={4,5,3,2,6,1,7,8,9,4,7};
int temp;
for(int i=0; i<sArray.length-1; i++){
    for(int j=i+1; j<sArray.length; j++){
        if(sArray[i] > sArray[j]){
            temp = sArray[i];
            sArray[i] = sArray[j];
            sArray[j] = temp;
        }
    }
}

---------------------------------------------------
Exchange Sort (Bubble sort) is a simplest sorting algorithm. The traversal logic is quite simple, please see
the code below. The algorithm follow the same steps repeatedly until the values of array is sorted. 

In this algorithm we are comparing first two values and put the larger one at higher index. Then we take next 
two values compare these values and place larger value at higher index. This process do iteratively until the 
largest value is not reached at last index. Then start again from zero index up to n-1 index. The algorithm 
follows the same steps iteratively unlit elements are not sorted. 

Time efficiency:
In worst-case the complexity of bubble sort is O(n2).

//eArray[]={4,5,3,2,6,1,7,8,9,4,7};  
    temp=0;
    for(int i=0; i<eArray.length-1; i++){
        for(int j=0; j<(eArray.length-1)-i; j++){
            if(eArray[j] > eArray[j+1]){
                temp = eArray[j];
                eArray[j] = eArray[j+1];
                eArray[j+1] = temp;
            }
        }
    }
    
---------------------------------------------------
Insertion sorting algorithm is similar to bubble sort. But insertion sort is more efficient than bubble 
sort because in insertion sort the elements comparisons are less as compare to bubble sort. 
In insertion sorting algorithm we compare one value until all the prior elements in Array are lesser.
This mean that the all previous values are lesser than compared value. 

Insertion sort is a good choice for small values and for nearly-sorted values. There are more efficient 
algorithms such as quick sort, heap sort, or merge sort for large values .

Positive feature of insertion sorting: 
1.It is simple to implement. 
2.It is efficient on (quite) small data values. 
3.It is efficient on data sets which are already nearly sorted.

Time efficiency:
The complexity of insertion sorting is O(n) at best case of an already sorted array and  O(n2) at worst case.

//iArray[]={4,5,3,2,6,1,7,8,9,4,7};  
    temp=0;        
    for(int i=1;i<iArray.length;i++){
        int j = i;
        temp=iArray[i];                            //mark this element
        while((j > 0) && (iArray[j-1] >= temp)){ //until element is smaller.
            iArray[j] = iArray[j-1];             //shift them to right
            j--;                                 //Move one position left
        }
        iArray[j] = temp;
    }    
---------------------------------------------------

Complete program having all these Sorting Strategies:
//SortingProgram.java
public class SortingProgram {
    public static void main(String[] args) {
        //Array Used in Selection sort: sArray
        //Array Used in Exchange (also called Bubble sort) sort: eArray  
        //Array Used in Insertion sort: iArray
        int sArray[]={4,5,3,2,6,1,7,8,9,4,7};
        int eArray[]={4,5,3,2,6,1,7,8,9,4,7};
        int iArray[]={4,5,3,2,6,1,7,8,9,4,7};

        //***********Selection sort logic starts here:
        int temp;
        System.out.println("Array elements before Selection sorting:");
        for(int num:sArray)
            System.out.print(num+", ");

        for(int i=0; i<sArray.length-1; i++){
            for(int j=i+1; j<sArray.length; j++){
                if(sArray[i] > sArray[j]){
                    temp = sArray[i];
                    sArray[i] = sArray[j];
                    sArray[j] = temp;
                }
            }
        }
        System.out.println("\nArray elements After Selection sorting:");
        for(int num:sArray)
            System.out.print(num+", ");


        //***********Exchange sort logic starts here:
        //Showing ArrayElements again below for better visibility.
        //eArray[]={4,5,3,2,6,1,7,8,9,4,7};  
        System.out.println("\nArray elements before Exchange sorting:");
        for(int num:eArray)
            System.out.print(num+", ");
        temp=0;
        
        for(int i=0; i<eArray.length-1; i++){
            for(int j=0; j<(eArray.length-1)-i; j++){
                if(eArray[j] > eArray[j+1]){
                    temp = eArray[j];
                    eArray[j] = eArray[j+1];
                    eArray[j+1] = temp;
                }
            }
        }
        System.out.println("\nArray elements After Exchange sorting:");
        for(int num:eArray)
            System.out.print(num+", ");


        //***********Insertion sort logic starts here:
        //Showing ArrayElements again below for better visibility.
        //iArray[]={4,5,3,2,6,1,7,8,9,4,7};  
        System.out.println("\nArray elements before Insertion sorting:");
        for(int num:iArray)
            System.out.print(num+", ");
        temp=0;
        
        for(int i=1;i<iArray.length;i++){
            int j = i;
            temp=iArray[i];               //mark this element
            while((j > 0) && (iArray[j-1] >= temp)){ //until element is smaller.
                iArray[j] = iArray[j-1];             //shift them to right
                j--;                                 //Move one position left
            }
            iArray[j] = temp;
        }
        System.out.println("\nArray elements After Insertion sorting:");
        for(int num:iArray)
            System.out.print(num+", ");
    }
}
//
//Output:
Array elements before Selection sorting:
4, 5, 3, 2, 6, 1, 7, 8, 9, 4, 7, 
Array elements After Selection sorting:
1, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9, 
Array elements before Exchange sorting:
4, 5, 3, 2, 6, 1, 7, 8, 9, 4, 7, 
Array elements After Exchange sorting:
1, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9, 
Array elements before Insertion sorting:
4, 5, 3, 2, 6, 1, 7, 8, 9, 4, 7, 
Array elements After Insertion sorting:
1, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9, 

=============================END==========================