Monday, May 12, 2014

Simple Example to show Dependency inversion using Spring

This is a simple example to explain difference between a program having dependency inversion and one without it.

First we will see program without Dependency Inversion.

Example code without Dependency Inversion

public class VotingBooth {

      VoteRecorder voteRecorder = new VoteRecorder();

       public void vote(Candidate candidate) {
             voteRecorder.record(candidate);
       }

       class VoteRecorder {
             Map hVotes = new HashMap();

             public void record(Candidate candidate) {

                    int count = 0;
                    if (!hVotes.containsKey(candidate)){
                            hVotes.put(candidate, count);
                     } else {
                           count = hVotes.get(candidate);
                     }

                     count++;
                     hVotes.put(candidate, count);
            }
     }
}
In this example, the VotingBooth class is directly dependent on VoteRecorder, which has no abstractions and is the implementing class.

A dependency “inverted” version of this code might look a little different. First, we would define our VoteRecorder interface.

Code with Dependency Inversion in Spring:

We can use our code exactly as is. All we need to do is inform Spring through an XML configuration file that the recorder bean is implemented by the LocalVoteRecorder class. We do this with the following line:

public interface VoteRecorder {
       public void record(Candidate candidate) ;
}
And our implementing classes

The LocalVoteRecorder, which implements the VoteRecorder interface:

public class LocalVoteRecorder implements VoteRecorder {

      Map hVotes = new HashMap();

      public void record(Candidate candidate) {

            int count = 0;

            if (!hVotes.containsKey(candidate)){
                      hVotes.put(candidate, count);
            } else {
                     count = hVotes.get(candidate);
            }

            count++;
            hVotes.put(candidate, count);
    }
}
And the VotingBooth class:

public class VotingBooth {
     VoteRecorder recorder = null;

     public void setVoteRecorder(VoteRecorder recorder) {
          this.recorder = recorder;
     }

     public void vote(Candidate candidate) {
         recorder.record(candidate);
 }

  Now all we need to do is inform Spring through an XML configuration file that the recorder bean is implemented by the LocalVoteRecorder class. We do this with the following line:

<bean id="recorder" class="com.springindepth.LocalVoteRecorder" />
Then we simply map the recorder bean to the VotingBooth bean by setter injection in that beans definition.

<bean id="votingBooth" class="com.springindepth.VotingBooth">
     <property name="voteRecorder" ref="recorder"/>
</bean>
**Example taken from http://www.springbyexample.org/

Saturday, March 29, 2014

Java Program to merge two sorted Arrays

To merge two sorted array is one of the very commonly asked Interview question.

below is my code of merging two sorted arrays with explanation




import java.util.Arrays;
public class MergeSortedArray {  

  int [] a = {1,3,5,7,9,10};// -----> first sorted array
  int [] b = {2,4,6,8,8};   // -----> Second sorted array 

  public static void main(String[] args) {
    MergeSortedArray msa = new MergeSortedArray();
    /*

     * printing all three arrays 

     */  

  System.out.println("First Sorted Array is:");
  System.out.println(Arrays.toString(msa.a));
  System.out.println();
  System.out.println("Second Sorted Array is:");
  System.out.println(Arrays.toString(msa.b));
  System.out.println();
  System.out.println("Merged Sorted Array is:");
  System.out.println(Arrays.toString(

                            msa.getSortedMergedArray(msa.a, msa.b)));
  } 

   /*

    *Method to merged array which will be to get combined sorted array

    */

  public  int[] getSortedMergedArray(int[] a, int[] b) {  

   // defining new array of size first+second array 

    int[] mergedArray = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;  

    /*

    *iterating till last element of any of the array

    * We only loop till we reach at the end of any of the two arrays

    */ 


    while (i < a.length && j < b.length) {
         if (a[i] < b[j]) {
             mergedArray[k++] = a[i++];
         }

         else {       
             mergedArray[k++] = b[j++];  
         }
     }  

     /* 

      * loop to add reaming elements of either of the remaining array  
     */  

     while (i < a.length) { 
         mergedArray[k++] = a[i++];
     }

     while (j < b.length) {
         mergedArray[k++] = b[j++];
     }

     return mergedArray;
 }
}

OUTPUT:
===========================================================================

First Sorted Array is:
[1, 3, 5, 7, 9, 10]

Second Sorted Array is:
[2, 4, 6, 8, 8]

Merged Sorted Array is:
[1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 10]

Java Program to find all combinations of a string

To find All combinations of a string is another commonly asked Interview question.

Below is my code for finding all the combinations of a given string with explanation:

public class AllStringCombinations { 
// taking String Builder object as we need to modify many time
     private StringBuilder outputString = new StringBuilder(); 
 
    private final String inputString; 
 
     /*
     *Constructor 
     */

    public AllStringCombinations( final String str ){
        inputString = str;
        System.out.println("The input string  is  : " + inputString);
    }    
    
    public static void main (String args[])
    {
        AllStringCombinations allStringCombinations =
                                    new AllStringCombinations("wxyz"); 
System.out.println("");
        System.out.println("All possible combinations are :  ");
        System.out.println("");
        allStringCombinations.getCombination(0);
    } 
     /*
      *Method to print all possible combinations recursively
      */ 

     public void getCombination(int start) { 
      
     for( int i = start; i <= inputString.length()-1; ++i ){
            outputString.append( inputString.charAt(i) );
            System.out.println( outputString );
            if ( i <= inputString.length() ) 

            // Recursive call

            getCombination( i + 1);
            outputString.setLength( outputString.length() - 1 );
        }
    }
}
 
OUTPUT:
===========================================================================
The input string  is  : wxyz

All possible combinations are :  

w
wx
wxy
wxyz
wxz
wy
wyz
wz
x
xy
xyz
xz
y
yz
z

java Program to find if two Strings are Anagrms



To find if two given Strings are Anagram of each other is very commonly asked interview Question.

Any word or phrase that exactly reproduces the letters in another order is an anagram.
for example "William Shakespeare " and  "I am a weakish speller " are Anagrams.

In a perfect anagram, every letter must be used, with exactly the same number of occurrences as in the anagrammed word or phrase.

Below is my code of checking if two given strings are anagrams.




public class Anagram { 
 
        boolean isAnagram(String s1,String s2) {       

           char a1[]= s1.toCharArray();
           char a2[]= s2.toCharArray();
           int []index1= new int[26];
           int []index2= new int[26];

           int i = 0;
           for(i=0;i<a1.length;i++) {
               index1[a1[i]-'a']++;
           }

           for(i=0;i<a2.length;i++) {
               index2[a2[i]-'a']++;           
           }

           for(i=0;i<26;i++) {
               if(index1[i]!=index2[i])
                     return false;
           }
           return true;
      }

      public static void main(String[] args) {
    
          String s1="xyzabc";
          String s2 = "abcxyz";

          Anagram anagram = new Anagram();

          if(anagram.isAnagram(s1,s2)==true)
               System.out.println(" String "+s1+" is anagram of "+s2);
          else
               System.out.println(" String "+s1+" is not anagram of "+s2);
      }
}

Output:
==================================================================
 String xyzabc is anagram of abcxyz


Wednesday, March 26, 2014

Tree Terminology

This is my quick recap guide for commonly used tree terminologies:



  • The depth of a node is the number of edges from the root to the node.
  • The height of a node is the number of edges from the node to the deepest leaf.
  • The height of a tree is a height of the root.
  • A full binary tree is a binary tree in which each node has exactly zero or two children.
  • A complete binary tree is a binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right.
 

 

Traversals

A traversal is a process that visits all the nodes in the tree. Since a tree is a nonlinear data structure, there is no unique traversal. We will consider several traversal algorithms with we group in the following two kinds
  • depth-first traversal
  • breadth-first traversal
There are three different types of depth-first traversals, :
  • PreOrder traversal - visit the parent first and then left and right children;
  • InOrder traversal - visit the left child, then the parent and the right child;
  • PostOrder traversal - visit left child, then the right child and then the parent;
There is only one kind of breadth-first traversal--the level order traversal. This traversal visits nodes by levels from top to bottom and from left to right.
As an example consider the following tree and its four traversals:

PreOrder - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3
InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11
PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8
LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2
   
The next picture demonstrate the order of node visitation. Number 1 denote the first node in a particular traversal and 7 denote the last node.

 

  Binary Search Trees

   A BST is a binary tree where nodes are ordered in the following way:
  • each node contains one key (also known as data)
  • the keys in the left subtree are less then the key in its parent node, in short L < P;
  • the keys in the right subtree are greater the key in its parent node, in short P < R;
  • duplicate keys are not allowed.
  In the following tree all nodes in the left subtree of 10 have keys < 10 while all nodes in the right subtree > 10. Because both the left and right subtrees of a BST are again search trees; the above definition is recursively applied to all internal nodes:

Insertion


We start at the root and recursively go down the tree searching for a location in a BST to insert a new node. If the element to be inserted is already in the tree, we are done (we do not insert duplicates). The new node will always replace a NULL reference.
 

 

Searching


Searching in a BST always starts at the root. We compare a data stored at the root with the key we are searching for. If the node does not contain the key we proceed either to the left or right child depending upon comparison. If the result of comparison is negative we go to the left child, otherwise - to the right child.

 

Deletion


There are few cases to consider.
  • is not in a tree;
  • is a leaf;
  • has only one child;
  • has two children.
If  node to delete is not in the tree, there is nothing to delete. If  node to delete has only one child the procedure of deletion is identical to deleting a node from a linked list - we just bypass that node being deleted


Deletion of an internal node with two children is less straightforward. If we delete such a node, we split a tree into two subtrees and therefore, some children of the internal node won't be accessible after deletion. In the picture below we delete 8:


We replace the node being deleted with the largest node in the left subtree and then delete that largest node. By symmetry, the node being deleted can be swapped with the smallest node is the right subtree
**taken from http://www.cs.cmu.edu

Tuesday, March 4, 2014

Cloning in Java

A clone is an exact copy of the original. In java, it essentially means the ability to create an object with similar state as the original object.

Sections in this post: 
  1. Default Java cloning
  2. Cloneable Interface
  3. Shallow cloning
  4. Deep cloning
    1. Deep cloning by overriding clone method
    2. Deep cloning using copy constructor
    3. Deep cloning using The factory Method
    4. Deep cloning by Serialzation
  5. Summery

Java cloning

 

By default, java cloning is ‘field by field copy’ i.e. as the Object class does not have idea about the structure of class on which clone() method will be invoked. So, JVM when called for cloning, do following things:

1) If the class has only primitive data type members then a completely new copy of the object will be created and the reference to the new object copy will be returned.

2) If the class contains members of any class type then only the object references to those members are copied and hence the member references in both the original object as well as the cloned object refer to the same object.

In java, if a class needs to support cloning it has to do following things:

A) It must implement Cloneable interface.
B) It must override clone() method from Object class.

Cloneable Interface
public interface Cloneable
A class implements the Cloneable interface to indicate to the Object.clone() method that it is legal for that method to make a field-for-field copy of instances of that class. Invoking Object's clone method on an instance that does not implement the Cloneable interface results in the exception CloneNotSupportedException being thrown.
By convention, classes that implement this interface should override Object.clone (which is protected) with a public method.

Java docs about clone() method says:

1. x.clone() != x will be true
2. x.clone().getClass() == x.getClass() will be true, 
                           but these are not absolute requirements.
3. x.clone().equals(x) will be true, this is not an absolute requirement 
  1.  First statement guarantees that cloned object will have separate memory address assignment.
  2. Second statement suggest that original and cloned objects should have same class type, but it is not mandatory.
  3. Third statement suggest that original and cloned objects should have be equal using equals() method, but it is not mandatory.
Cloning can be categorized in two types:

 

Shallow Cloning 

 

This is default implementation in java. In overridden clone method, if you are not cloning all the object types (not primitives), then you are making a shallow copy. Let's see one example:

Class Employee implements cloneable Interface and has Department as its member variable

public class Employee implements Cloneable{

   private int employeeId;
   private String employeeName;
   private Department department;

   public Employee(int id, String name, Department dept) {
     this.empoyeeId = id;
     this.employeeName = name;
     this.department = dept;
   }   
   
   public int getEmployeeId() {
     return empoyeeId;
   }

   public void setEmployeeId(int employeeId) {
     this.employeeId = empoyeeId;
   }

   public String getEmployeeName() {
     return employeeName;
  }

   public void setEmployeeName(String employeeName) {
     this.employeeName = employeeName;
  }

   public Department getDepartment() {
     return department;
   }

   public void setDepartment(Department department) {
     this.department = department;
   }

   @Override
   protected Object clone() throws CloneNotSupportedException {
     return super.clone();
 }
}
  Class Department:

public class Department
{
 private int id;
 private String name;

 public Department(int id, String name)
 {
  this.id = id;
  this.name = name;
 }

 public int getId() {
  return id;
 }

 public void setId(int id) {
  this.id = id;
 }

 public String getName() {
  return name;
 }

 public void setName(String name) {
  this.name = name;
 }
}
  Test Class:

public class TestCloning {

    public static void main(String[] args)

               throws CloneNotSupportedException {

         Department dept = new Department(1, "Human Resource");
         Employee original = new Employee(1, "Admin", dept); 

        //Lets create a clone of original object

         Employee cloned = (Employee) original.clone();


        //Let verify using employee id, if cloning actually worked

          System.out.println(cloned.getEmpoyeeId());

        //Verify JDK's rules
    //Must be true and objects must have different memory addresses
         System.out.println(original != cloned);

    //As we are returning same class; so it should be true 
         System.out.println(original.getClass() == cloned.getClass());


     //Default equals method checks for references so it should be false.
        // If we want to make it true,
        //we need to override equals method in Employee class.
        System.out.println(original.equals(cloned));
    }
} 
 
Output:
========================================================================== 
 1
true
true
false
 What will happen if we don't implement cloneable Interface???

Check the following code for Class Employee, I have not Implemented Cloneable interface this time but clone method is still there. No compilation error will be shown but when we run the code run-time Exception will come.

public class Employee {

   private int empoyeeId;
   private String employeeName;
   private Department department;

   public Employee(int id, String name, Department dept) {
     this.empoyeeId = id;
     this.employeeName = name;
     this.department = dept;
   }   
   
   public int getEmpoyeeId() {
     return empoyeeId;
 }

 public void setEmpoyeeId(int empoyeeId) {
  this.empoyeeId = empoyeeId;
 }

 public String getEmployeeName() {
  return employeeName;
 }

 public void setEmployeeName(String employeeName) {
  this.employeeName = employeeName;
 }

 public Department getDepartment() {
  return department;
 }

 public void setDepartment(Department department) {
  this.department = department;
 }

 @Override
   protected Object clone() throws CloneNotSupportedException {
     return super.clone();
 }
}

Output
===========================================================================

Exception in thread "main" java.lang.CloneNotSupportedException:
 com.Employee
 at java.lang.Object.clone(Native Method)
 at com.Employee.clone(Employee.java:48)
 at com.TestCloning.main(TestCloning.java:13)
  We can see even if Object class has clone method still we need to implement Cloneable interface to use clone method.

 

Deep cloning


We want a clone which is independent of original and making changes in clone should not affect original.

But before seeing how deep cloning works, lets see what happens when we create two objects of employee class:

public class TestCloning {

 public static void main(String[] args) 
 
  Department hr = new Department(1, "Human Resource");
  Employee original = new Employee(1, "Admin", hr);
  Employee cloned = (Employee) original.clone();

  //Let change the department name in cloned object 
  //and we will verify in original object
  cloned.getDepartment().setName("Finance");

  System.out.println(original.getDepartment().getName());
 }
}

Output: 
========================================================================== 
Finance

cloned object changes are visible in original also. To prevent this from happening we need to do deep cloning.

Let see how it can be done

1. Deep Cloning by overriding clone() 
  Modified clone() method in Employee class

@Override
protected Object clone() throws CloneNotSupportedException {
 Employee cloned = (Employee)super.clone();
 cloned.setDepartment((Department)cloned.getDepartment().clone());
 return cloned;
}
 override clone method in Department class also:
 
@Override
protected Object clone() throws CloneNotSupportedException {
 return super.clone();
}
  Test class:

public class TestCloning {

 public static void main(String[] args) 
                        throws CloneNotSupportedException { 
 
    Department hr = new Department(1, "Human Resource");
    Employee original = new Employee(1, "Admin", hr);
    Employee cloned = (Employee) original.clone();

    //Let's change the department name in cloned object 
                //and we will verify in original object
    cloned.getDepartment().setName("Finance");

   System.out.println(original.getDepartment().getName());
 }
}
 
Output: 
========================================================================== 
Human Resource
So deep cloning requires satisfaction of following rules.
  • All the member classes in original class should support cloning and in clone method of original class in context should call super.clone() on all member classes.
  • If any member class does not support cloning then in clone method, one must create a new instance of that member class and copy all its attributes one by one to new member class object. This new member class object will be set in cloned object.

 

2. Deep Cloning Using Copy Constructors


A copy constructor is a constructor that takes only one argument which is of the type as the class in which the copy constructor is implemented. For example, let us assume a class namely Employee and it has a constructor called copy constructor which expects only one argument of type Employee.

Let’s see an example

public class Employee {

   private int empoyeeId;
   private String employeeName;
   private Department department;

      
   public int getEmpoyeeId() {
     return empoyeeId;
   }

   public void setEmpoyeeId(int empoyeeId) {
     this.empoyeeId = empoyeeId;
   }

   public String getEmployeeName() {
     return employeeName;
  }

   public void setEmployeeName(String employeeName) {
     this.employeeName = employeeName;
  }

   public Department getDepartment() {
     return department;
   }

   public void setDepartment(Department department) {
     this.department = department;
   }
   public Employee(int id, String name, Department department) {

        this.id = id;

        this.name = name;

        this.department = department;

    } 
 
   //copy constructor
public Employee(Employee oldEmployee) {

        this.id = oldEmployee.id;
        this.name = oldEmployee.name;
        this.department = oldEmployee.department;  //shallow cloning
    }
} 
  Class Department:

public class Department
{
 private int id;
 private String name;

 public Department(int id, String name)
 {
  this.id = id;
  this.name = name;
 }

 public int getId() {
  return id;
 }

 public void setId(int id) {
  this.id = id;
 }

 public String getName() {
  return name;
 }

 public void setName(String name) {
  this.name = name;
 }
 public Department(int id, String name) {

      this.id = id;

      this.name = name;

 } 
 
  //copy constructor
 public Department(Department oldDepartment) {

      this.id = oldDepartment.id;
      this.name = oldDepartment.name;
  }
 }
  Test Class

public class CopyConstructorTest {
 
 public static void main(String[] args) {

        Department department = new Department(1, "Finance");
        Employee originalEmployee = new Employee(1, "Ram", department);

        Employee clonedEmployee = new Employee(originalEmployee);

        System.out.println("Original:- " + originalEmployee);
        System.out.println("Duplicate:- " + clonedEmployee);
        System.out.println();

        clonedEmployee.setId(2);
        clonedEmployee.setName("Laxman");
        clonedEmployee.getDepartment().setName("HR");

        System.out.println("Original:- " + originalEmployee);
        System.out.println("Duplicate:- " + clonedEmployee);
    }
}
Output
============================================================================
Original:- Employee Id: 1   Employee Name: Ram  Department Id: 1
Department Name: Finance
Duplicate:- Employee Id: 1  Employee Name: Ram  Department Id: 1
Department Name: Finance
Original:- Employee Id: 1   Employee Name: Ram  Department Id: 1
Department Name: HR
Duplicate:- Employee Id: 2  Employee Name: Laxman   Department Id: 1
Department Name: HR
What happens in the above example is, when we change the department name of clonedEmployee, the change comes up with the originalEmployee also. Why it behaves so because what we implement here is shallow cloning

Let’s have a small change in the copy constructor of Employee class to implement Deep cloning 

public Employee(Employee oldEmployee) {
  this.id = oldEmployee.id;
  this.name = oldEmployee.name;
 this.department = newDepartment(oldEmployee.department); //deep cloning
}
  Now we test again and the output is

Original:-  Employee Id: 1  Employee Name: Ram  Department Id: 1    Department Name: Finance
Duplicate:- Employee Id: 1  Employee Name: Ram  Department Id: 1    Department Name: Finance
Original:-  Employee Id: 1  Employee Name: Ram  Department Id: 1    Department Name: Finance
Duplicate:- Employee Id: 2  Employee Name: Laxman   Department Id: 1    Department Name: HR
 Now everything goes fine and this is what we call deep cloning using copy constructors.

But wait until Inheritance comes

let's have one class Manager which inherit Employee

Class Manager:

public class Manager extends Employee{        
private int managerId;
           
    public int getManagerId() {
        return managerId;
    }

    public void setManagerId(int managerId) {
        this.managerId = managerId;
    }

    public Manager (Employee obj, int ManagerId) {
        super(obj);
        this.managerId= ManagerId;
    }
   
    public Manager(Manager obj) {
        super(obj);
        this.managerId= obj.managerId;
    }
}

Test class:

public class TestCloning {        

   public static void main(String[] args) {

        Department department1 = new Department(1, "Finance");
        Department department2 = new Department(2, "It");       

        Employee employee1 = new Employee(1, "Ram", department1);
        Employee employee2 = new Employee(1, "Laxman", department2); 
 
        Manager manager1 = new Manager(employee2,1);
 
        Employee clone1 = new Employee(employee1);
        Employee clone2 = new Employee(manager1);       

        System.out.println("clone1:- " +clone1.toString());
        System.out.println(clone1.getClass());
        System.out.println("clone2:- " + clone2.toString());
        System.out.println(clone2.getClass());
    }
}
Output
===================================================================
clone1:- Employee Id: 1    Employee Name: Ram    Department Id: 1    Department Name: Finance
class com.Employee
clone2:- Employee Id: 1    Employee Name: Laxman    Department Id: 2    Department Name: It
class com.Employee
What just happened here? We passed Manger object to clone2 to but we got Employee class object after cloning.

3. Deep cloning by The Factory Method:

In certain situations we can’t make our copy constructor public, so it has to be private. Now we need to think about an equivalent and yes, fortunately we are able to find out another workaround for achieving the same result- The Factory Method. Let’s have a look.

Class Employee

public class Employee {
    
private String name;
    private int id;
    private Department department;

    public Department getDepartment() {
        return department;
    }
 
    public String getName() {
        return name;
    }

    public int getId() {
        return id;
    }

    public void setDepartment(Department department) {
        this.department = department;
    }

    public void setName(String name) {
        this.name = name;
    }

    public void setId(int id) {
        this.id = id;
    }

    public Employee(int id, String name, Department department) {
        this.id = id;
        this.name = name;
        this.department = department;
    }

    private Employee(Employee oldEmployee) {
        this.id = oldEmployee.id;
        this.name = oldEmployee.name;
        //deep cloning
        this.department = new Department(oldEmployee.department);
    }

    @Override
    public String toString() {
        return "Employee Id: " + id + "\tEmployee Name: " + name + "\t" 
       + department;
    }

    public static Employee copy(Employee originalEmployee) {
        return new Employee(originalEmployee);
    }
}
Test Class:

public class TestCloning {   
public static void main(String[] args) {

        Department department = new Department(1, "Finance");
        Employee originalEmployee = new Employee(1, "Ram", department);
        Employee clonedEmployee = Employee.copy(originalEmployee);

        System.out.println("Original:- " + originalEmployee);
        System.out.println("Duplicate:- " + clonedEmployee);
        System.out.println();

        clonedEmployee.setEmployeeId(2);
        clonedEmployee.setEmployeeName("Laxman");
        clonedEmployee.getDepartment().setName("HR");

        System.out.println("Original:- " + originalEmployee);
        System.out.println("Duplicate:- " + clonedEmployee);
    }  
}
Output
===================================================================
Original:- Employee Id: 1    Employee Name: Ram    Department Id: 1    Department Name: Finance
Duplicate:- Employee Id: 1    Employee Name: Ram    Department Id: 1    Department Name: Finance

Original:- Employee Id: 1    Employee Name: Ram    Department Id: 1    Department Name: Finance
Duplicate:- Employee Id: 2    Employee Name: Laxman    Department Id: 1    Department Name: HR

4. Deep cloning with serialization

Java serialization is convenient. Many classes are made serializable by simply declaring them to implement java.io.Serializable. Thus, a whole hierarchy of classes can be made cloneable by deriving them from a base Serializable class 

Lets see the code sample:

public Employee clone(Employee obj) {
   
 try
    {
        ByteArrayOutputStream out = new ByteArrayOutputStream ();
        ObjectOutputStream oout = new ObjectOutputStream (out);
        oout.writeObject (obj);
       
        ObjectInputStream in = new ObjectInputStream (
            new ByteArrayInputStream (out.toByteArray ())); 
 
            //This returned Employee object will be a cloned object
return (Employee)in.readObject ();
    }
    catch (Exception e)
    {
        throw new RuntimeException ("cannot clone class [" +
            obj.getClass ().getName () + "] via serialization: " +
            e.toString ());
    }
}
For more details about Serialization refer to serialization in Java.

 

The Summery

 

The following table recaps the properties of all cloning approaches from several perspectives: speed, resource utilization, class design constraints, object graph handling.

Object.clone()
Speed High
Resource utilization Low
Class design constraints Does not work with deep final fields; does not work with inner classes; must implement Cloneable; medium amount of manual class maintenance
Object graphs Does not handle object graphs transparently
Copy construction
Speed High
Resource utilization Low
Class design constraints Superclasses and subclasses must cooperate; copy constructor required; a lot of manual class maintenance
Object graphs Does not handle object graphs transparently
Serialization
Speed Low
Resource utilization High; creates redundant immutable fields
Class design constraints Must implement Serializable; first non-Serializable class needs an accessible no-arg constuctor
Object graphs Handles object graphs
Reflection
Speed Medium
Resource utilization Medium
Class design constraints Does not work with final fields; does not work with inner classes; each class must provide no-arg constructor
Object graphs Handles object graphs



Wednesday, February 26, 2014

Tower of Hanoi solution using recursion in java

Tower of hanoi is one of the basic questions to learn recursion and very commonly asked interview question at beginner and intermediate level.

Section in this post:
  1. Problem statement
  2. Iterative solution
  3. Alternate iterative solution
  4. Recursive solution
  5. Java Implementation

The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower, and sometimes pluralised) is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
  3. No disk may be placed on top of a smaller disk.
 With three disks, the puzzle can be solved in seven moves. The minimum number of moves required to solve a Tower of Hanoi puzzle is 2n - 1, where n is the number of disks.

Iterative solution

 

Alternate moves between the smallest piece and a non-smallest piece. When moving the smallest piece, always move it to the next position in the same direction (to the right if the starting number of pieces is even, to the left if the starting number of pieces is odd). If there is no tower position in the chosen direction, move the piece to the opposite end, but then continue to move in the correct direction. For example, if you started with three pieces, you would move the smallest piece to the opposite end, then continue in the left direction after that. When the turn is to move the non-smallest piece, there is only one legal move. Doing this will complete the puzzle in the fewest number of moves.

 

Simpler statement of iterative solution

 

Alternating between the smallest and the next-smallest disks, follow the steps for the appropriate case:
For an even number of disks:
  • make the legal move between pegs A and B
  • make the legal move between pegs A and C
  • make the legal move between pegs B and C
  • repeat until complete
For an odd number of disks:
  • make the legal move between pegs A and C
  • make the legal move between pegs A and B
  • make the legal move between pegs C and B
  • repeat until complete
In each case, a total of 2n-1 moves are made.

Equivalent iterative solution

 

Another way to generate the unique optimal iterative solution:
Number the disks 1 through n (largest to smallest).
  • If n is odd, the first move is from the Start to the Finish peg.
  • If n is even, the first move is from the Start to the Using peg.
Now, add these constraints:
  • No odd disk may be placed directly on an odd disk.
  • No even disk may be placed directly on an even disk.
  • Never undo your previous move (that is, do not move a disk back to its immediate last peg).
Considering those constraints after the first move, there is only one legal move at every subsequent turn.
The sequence of these unique moves is an optimal solution to the problem equivalent to the iterative solution described above.

Recursive solution

 

A key to solving this puzzle is to recognize that it can be solved by breaking the problem down into a collection of smaller problems and further breaking those problems down into even smaller problems until a solution is reached. For example:
  • label the pegs A, B, C — these labels may move at different steps
  • let n be the total number of discs
  • number the discs from 1 (smallest, topmost) to n (largest, bottommost)
To move n discs from peg A to peg C:
  1. move n−1 discs from A to B. This leaves disc n alone on peg A
  2. move disc n from A to C
  3. move n−1 discs from B to C so they sit on disc n
The above is a recursive algorithm, to carry out steps 1 and 3, apply the same algorithm again for n−1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1. This step, moving a single disc from peg A to peg B, is trivial.



Below is my Java code to solve the problem recursively.

Class TowerOfHanoi:

public class TowerOfHanoi {

  public static void solveHanoi(int nTop, char fromTower, char midTower,
                              char toTower) {
    if (nTop == 1){
      System.out.println("Disk 1 from " + fromTower + " to " + toTower);
    }else {
      solveHanoi(nTop - 1, fromTower, toTower, midTower);
      System.out.println("Disk " + nTop + " from " + fromTower 
                 + " to " + midTower);
      solveHanoi(nTop - 1, midTower, fromTower, toTower);
    }
  }

  public static void main(String[] args) {
    int nDisks = 3;
    solveHanoi(nDisks, 'A', 'B', 'C');
  }
}

output :
===================================================================
Disk 1 from A to C
Disk 2 from A to B
Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A
Disk 2 from B to C
Disk 1 from A to C


Factorial of a number using recursion in Java


Java program to calculate factorial of integer using recursion


public class Factorial
{
     public int fact(int n) {
if(n==1) {
return 1;
}
else {
return  fact(n-1) * n;
}
    }

public static void main(String args[]){
       int number =4;
Factorial factorial = new factorial();
System.out.println("The factorial of the number is : " + factorial.fact(number);
     }
}

Thursday, February 20, 2014

Doubly Link List In Java

In my previous post  I made a simple link list which holds integer values. Moving ahead in  this post I am creating my own doubly link list .

A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.

The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list.

It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.
A doubly-linked list whose nodes contain three fields: an integer value, the link to the next node, and the link to the previous node.

A doubly-linked list whose nodes contain three fields: an integer value, the link to the next node, and the link to the previous node.

Sections in this post: 
  1. Link List Interface
  2. Link List Node
  3. Implementation

Link List Interface

Below is my Link List Interface. It is not at  all mandatory to write Interface for link list . I have written so as to make code more understandable and  to follow good code writing practices.

public interface LLInterface {
 /*
  * different overloaded insert
  */
 public boolean insertAtStart(Node nodeToInsert);
 public boolean insertAtStart(int data);
 public boolean insertAtEnd(Node nodeToInsert);
 public boolean insertAtEnd(int data);
 public boolean insert(Node nodeToInsert, int loc);
 public boolean insert(int data, int loc);

 /*
  * different overloaded delete
  */
 public Integer deleteFirst();
 public Integer deleteLast();
 public Integer delete(int loc);
 public boolean deleteThis(int data);

 /*
  * ADT method to know if list is empty
  * we will be using this method at many places such as
  * before deleting a node to make sure list is already not empty
  */
 public boolean isEmpty();

 /*
  * ADT method to print entire list
  *
  */
 public void printList(Node head);


 /* ADT method to get number of nodes present after the given node.
        *If head is passed as argument then it will return size of list
         *This method should be avoided at places such as,
         *to validate given insertion or deletion location as it
         *internally traverse complete list once.
  */
 public int getSize(Node head);
}


Link List Node

In Link list data is stored in nodes. therefore let's see how to implement a node. For the sake of simplicity I am considering nodes having only integer values but this can be changed easily.

public class Node {
 // data variable will hold integer value 
 private int data;
 //Reference(Pointer) to next node in list 
 private Node next;
 //Reference(Pointer) to previous node in list 
 private Node prev;
 
 public Node(int data) { 
  super();
  this.data = data; 
  this.next = null; 
  this.prev = null;
 }
 
 public Node(){ 
  super();
 }

 /*
  * Getter and setters 
  */
 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 Node getPrev() { 
  return prev;
 }

 public void setPrev(Node prev) { 
  this.prev = prev;
 }
}


Implementation

package single;

public class SLL implements LLInterface {

    private Node head;

    @Override
    public boolean insertAtStart(Node nodeToInsert) {
        // Check if node is not null else return
        // We add this check as there can be situation where object is set to
        // null or
        // some one has used default constructor make the node object etc.
        if (nodeToInsert == null) {
            System.out.println("Node you are trying to insert is null");
            return false;
        }
        // check if list is empty then set node as head
        if (isEmpty()) {
            head = nodeToInsert;
        }
        // make nodeToInsert as head and head as second
        // node(nodeToInsert-->head-->....)
        else {
            nodeToInsert.setNext(head);
            head = nodeToInsert;
        }
        return true;
    }

    @Override
    public boolean insertAtStart(int data) {

        /*
         * we can have two approaches to get new node
         * 
         * First Approach: Use default constructor and then set values using
         * setters
         * 
         * Node nodeToInsert = new Node(); nodeToInsert.setData(data);
         * nodeToInsert.setNext(null);
         * 
         * Second approach: Use overloaded constructor of Node class
         */
        Node nodeToInsert = new Node(data);

        // As we already have a method to insert node at beginning having node
        // object
        // as parameter we will just call that
        // else we can add all the code of that method here itself
        return insertAtStart(nodeToInsert);

    }

    @Override
    public boolean insertAtEnd(Node nodeToInsert) {
        // Check if node is not null else return
        // We add this check as there can be situation where object is set to
        // null or
        // one has used default constructor make the node object etc.
        if (nodeToInsert == null) {
            System.out.println("Node you are trying to insert is null");
            return false;
        }
        // Check if list is empty then set node as head
        if (isEmpty()) {
            head = nodeToInsert;
            return true;
        }
        Node currentNode = head;
        while (currentNode.getNext() != null) {
            currentNode = currentNode.getNext();
        }
        currentNode.setNext(nodeToInsert);
        return true;
    }

    @Override
    public boolean insertAtEnd(int data) {

        /*
         * we can have two approaches to get new node
         * 
         * First Approach: Use default constructor and then set values using
         * setters
         * 
         * Node nodeToInsert = new Node(); nodeToInsert.setData(data);
         * nodeToInsert.setNext(null);
         * 
         * Second approach: Use overloaded constructor of Node class
         */
        Node nodeToInsert = new Node(data);

        // As we already have a method to insert node at end having node object
        // as
        // parameter we will just call that
        // else we can add all the code of that method here itself
        return insertAtEnd(nodeToInsert);
    }

    @Override
    public boolean insert(Node nodeToInsert, int loc) {
        // Check if node is not null else return
        // We add this check as there can be situation where object is set to
        // null or
        // some one has used default constructor make the node object etc.
        if (nodeToInsert == null) {
            System.out.println("Node you are trying to insert is null");
            return false;
        }
        // validate given location to add node, we wont check with list size
        // here as
        // it internally traverse complete list once
        if (loc < 1) {
            System.out.println("Invalid Location specifed to insert node");
            return false;
        }
        if (loc == 1) {
            insertAtStart(nodeToInsert);
        } else {
            Node currentNode = head;
            // Now we will reach the required location so that we can add node
            // there
            // note that we will stop one place before we want to add node and
            // keep in
            // mind current node is already at first node i.e head
            // e.g. if we want to add new node at location five, then we will
            // traverse
            // till node four
            // we will also check whether current node is not null as location
            // given
            // can be more then list size
            for (int i = 0; i < loc - 2 && currentNode != null; i++) {
                currentNode = currentNode.getNext();
            }
            if (currentNode == null) {
                System.out.println("Invalid Location specifed to insert node");
                return false;
            }
            // Now we need to insert new node at this location
            // so we will make new node's next to point to current node's next
            // and current node will point to new node
            // Note that order is important here
            nodeToInsert.setNext(currentNode.getNext());
            currentNode.setNext(nodeToInsert);
            return true;
        }
        return false;
    }

    @Override
    public boolean insert(int data, int loc) {
        /*
         * we can have two approaches to get new node
         * 
         * First Approach: Use default constructor and then set values using
         * setters
         * 
         * Node nodeToInsert = new Node(); nodeToInsert.setData(data);
         * nodeToInsert.setNext(null);
         * 
         * Second approach: Use overloaded constructor of Node class
         */
        Node nodeToInsert = new Node(data);

        // As we already have a method to insert node at end having node object
        // as parameter we will just call that
        // else we can add all the code of that method here itself
        return insert(nodeToInsert, loc);
    }

    @Override
    public Integer deleteFirst() {
        // Check if list is already Empty
        if (isEmpty()) {
            System.out.println("List is empty, can not eprform delete operation");
            return null;
        }
        /* First save head value to return then Make head to point next node in the list
         *Again order is important
        */
        int deletedNodeValue = head.getData();
        if(null != head.getNext()) {
           head.getNext().setPrev(null);
    head = head.getNext();
 }
 else {
    head = null;
 }
        return deletedNodeValue;
    }

    @Override
    public Integer deleteLast() {
        // Check if list is already Empty
        if (isEmpty()) {
            System.out.println("List is empty, can not eprform delete operation");
            return null;
        }
        Node currentNode = head;
        // TODO
        return null;
    }

    @Override
    public Integer delete(int loc) {
        // validate given location to delete node, we wont check with list size
        // here
        // as it internally traverse complete list once
        if (loc < 1) {
            System.out.println("Invalid Location specifed to delete node");
            return null;
        }
        Node currentNode = head;
        if (loc == 1) {
            return deleteFirst();
        }
        // we will also check whether current node is not null as location given
        // can
        // be can be more then list size
        for (int i = 0; i < loc - 2 && currentNode != null; i++) {
            currentNode = currentNode.getNext();
        }
        if (currentNode == null) {
            System.out.println("Invalid    Location specifed to delete node");
            return null;
        }
        int deletedNodeValue = currentNode.getData();
        currentNode.setNext(currentNode.getNext().getNext());
        return deletedNodeValue;
    }

    @Override
    public boolean deleteThis(int data) {

        if (head.getData() == data) {            
            return (deleteFirst()!= null);
        }
        // Check if list is already Empty
        // We are checking isEmpty after checking for head data as deleteFirst
        // also
        // has list empty check
        // and we do'nt want to execute this check twice by putting below
        // isEmpty
        // check at start of this method call
        if (isEmpty()) {
            System.out.println("List is empty, can not eprform delete operation");
            return false;
        }

        Node currentNode = head;

        //Iterate list until node to delete is reached or list ends
        while (currentNode.getNext() != null) {
            if (currentNode.getNext().getData() == data) {
                currentNode.setNext(currentNode.getNext().getNext());
                return true;
            }
            currentNode = currentNode.getNext();
        }
        System.out.println("data not present in the list");
        return false;
    }

    /*
     * This method will return true if List is Empty else false List will be
     * empty when head is null
     */
    @Override
    public boolean isEmpty() {
        return null == head;
    }

    @Override
    public void printList(Node head) {
        if (head == null) {

            System.out.println("Invalid node given");
            return;
        }
        Node currentNode = head;
        System.out.print("List is: [");
        while (currentNode != null) {
            System.out.print("    "+currentNode.getData());
            currentNode = currentNode.getNext();
        }
        System.out.println("    ]");
    }

    public void printList() { 
 if(head == null) { 
  System.out.println("Invalid node given"); 
  return;
 }
 Node currentNode = head;
 System.out.print("List is: [ "); 
 while(currentNode != null) {
  System.out.print(currentNode.getData() +" ");
  currentNode = currentNode.getNext();
 }
 System.out.println("]");
  }
 
     @Override
    public int getSize(Node head) {
        int count = 0;
        Node currentNode = head;
        while (currentNode != null) {
            count++;
            currentNode = currentNode.getNext();
        }
        return count;
    }

    public static void main(String[] args) {
        SLL myLst = new SLL();

        myLst.insert(new Node(41),0);
        myLst.insert(new Node(42),2);
        myLst.insert(new Node(43),1);
        myLst.insert(new Node(44),1);
        myLst.insert(new Node(45),2);
        myLst.insert(new Node(46),4);
        myLst.insert(null,3);

        myLst.insert(51,0);
        myLst.insert(52,2);
        myLst.insert(53,1);
        myLst.insert(54,1);
        myLst.insert(55,2);
        myLst.insert(56,4);

        myLst.insertAtStart(1);
        myLst.insertAtStart(2);
        myLst.insertAtStart(3);
        myLst.insertAtStart(4);

        myLst.insertAtStart(new    Node(11));
        myLst.insertAtStart(new    Node(12));
        myLst.insertAtStart(new    Node(13));
        myLst.insertAtStart(new    Node(14));
        myLst.insertAtStart(null);

        myLst.insertAtEnd(21);
        myLst.insertAtEnd(22);
        myLst.insertAtEnd(23);
        myLst.insertAtEnd(24);

        myLst.insertAtEnd(new Node(31));
        myLst.insertAtEnd(new Node(32));
        myLst.insertAtEnd(new Node(33));
        myLst.insertAtEnd(new Node(34));
        myLst.insertAtEnd(null);

        myLst.printList(myLst.head);
        System.out.println("===========================deletefirst=================");
        myLst.deleteFirst();
        myLst.deleteFirst();
        myLst.deleteFirst();
        myLst.printList(myLst.head);
        System.out.println("=========delete from location==============");        
        myLst.delete(0);
        myLst.delete(1);
        myLst.delete(30);        
        myLst.delete(2);
        myLst.printList(myLst.head);
        System.out.println("=========delete this(data)========");
        myLst.deleteThis(31);
        myLst.deleteThis(131);
        myLst.deleteThis(45);
        myLst.printList(myLst.head);
    }
}

If we run the program we will get output like this:

Output
==========================================================================
Invalid Location specifed to insert node
Invalid Location specifed to insert node
Node you are trying to insert is null
Invalid Location specifed to insert node
Node you are trying to insert, is null
Node you are trying to insert is null
List is: [14    13    12    11    4    3    2    1    54    55    53    56    44    52    45    43    46    21    22    23    24    31    32    33    34    ]
===========================delecefirst================================
List is: [11    4    3    2    1    54    55    53    56    44    52    45    43    46    21    22    23    24    31    32    33    34    ]
 ============================deleteloc================================
Invalid Location specifed to delete node
Invalid Location specifed to delete node
List is: [4    2    1    54    55    53    56    44    52    45    43    46    21    22    23    24    31    32    33    34    ]
============================deletethis(data)============================
data not present in the list
List is: [4    2    1    54    55    53    56    44    52    43    46    21    22    23    24    32    33    34    ]
 ============================deletelast================================
34
List is: [4    2    1    54    55    53    56    44    52    43    46    21    22    23    24    32    33    ]

In next post we will talk about circular link list and then we will see some commonly asked question on link list.