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