code forum

Fail Fast And Fail Safe Iterator In Java

2016-05-29T08:07:00.004-07:00

In this post we will be discussing about fail-fast and fail-safe iterators present in java.

Sections in this post:

Concurrent Modification
Fail Fast Iterator
How Fail Fast Iterator works
Fail Safe Iterator
Examples
Difference between fail fast and fail safe iterator

What is Concurrent Modification?

When one or more threads are iterating over a collection and in between, one of the thread changes the structure of the collection (either adding the element to the collection or by deleting the element from the collection or by updating the value at particular position in the collection) is known as Concurrent Modification.

Fail fast Iterator

While iterating through the collection, Fail fast iterators instantly throws Concurrent Modification Exception if there is structural modification of the collection. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

How Fail Fast Iterator come to know that the internal structure is modified ?

Fail Fast Iterators read underlying collection object data directly. The internal data should not be modified while iterating through the collection. To ensure this it maintains an internal flag "modCount". Iterator checks the "modCount" flag whenever it gets the next value (using hasNext() method and next() method). Value of mods flag changes whenever there is an structural modification. Thus indicating iterator to throw "ConcurrentModificationException".

Fail safe Iterator

Fail Safe Iterator makes a copy of the underlying collection object and iterates over the copied collection object. Any structural modification done to the iterator affects the copied data structure so, original data structure remains structurally unchanged. Hence, no ConcurrentModificationException is thrown by the fail safe iterator.

Two issues associated with Fail Safe Iterator are :

Overhead of maintaining the copied data structure i.e memory.
Fail safe iterator does not guarantee that the data being read is the latest data from the underlying original collection object.

Lets see a fail fast iterator example:

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

public class FailFastExample
{
    public static void main(String[] args)
    {
        Map<string,String> premiumPhone =  
                       new HashMap<string,String>();
        premiumPhone.put("Apple", "iPhone");
        premiumPhone.put("HTC", "HTC one");
        premiumPhone.put("Samsung","S5");
        
        Iterator iterator = premiumPhone.keySet()
                                         .iterator();
        
        while (iterator.hasNext())
        {
            System.out.println(premiumPhone.get(
                                    iterator.next()));
            premiumPhone.put("Sony", "Xperia Z");
        }
    }
}

Output:                                                  
                    ================================================================

      iPhone

      Exception in thread "main" java.util.ConcurrentModificationException

      at java.util.HashMap$HashIterator.nextEntry(Unknown Source)

      at java.util.HashMap$KeyIterator.next(Unknown Source)

      at FailFastExample.main(FailFastExample.java:20)

We can see that as soon as we try to put a new entry ("Sony", "Xperia Z"), fail-fast iterator immediately throws ConcurrentModificationException.

lest's see Fail Safe Iterator Example now :

import java.util.concurrent.ConcurrentHashMap;
import java.util.Iterator;

public class FailSafeExample
{
    public static void main(String[] args)
    {
        Map<string,String> premiumPhone = 
                     new ConcurrentHashMap<string,String>();
        premiumPhone.put("Apple", "iPhone");
        premiumPhone.put("HTC", "HTC one");
        premiumPhone.put("Samsung","S5");
        
        Iterator iterator = premiumPhone.keySet()
                                          .iterator();
        
        while (iterator.hasNext())
        {
            System.out.println(premiumPhone
                               .get(iterator.next()));
            premiumPhone.put("Sony", "Xperia Z");
        }
    }
}

Output:

=============================================

HTC one

iPhone

Below table summarizes major differences between fail-fast and fail-safe iterator.

	Fail Fast Iterator	Fail Safe Iterator
Throw ConcurrentModification Exception	Yes	No
Clone object	No	Yes
Memory Overhead	No	Yes
Examples	HashMap,Vector,ArrayList,HashSet	CopyOnWriteArrayList, ConcurrentHashMap

Stack of Strings Implemented in Java

2015-03-10T07:38:00.002-07:00

In my previous post we talked about stack implementation using character array.

In this post I will be sharing my code for a stack implementation which can hold String values in other words stack implemented using array of String in java.

Sections in this post:

String Array Based Implementation of stack.

Let see the code directly as it is self explanatory

public class StackOfStrings {
 // Every stack has a maximum capacity i.e. number of objects it can hold, 
 private static final int CAPACITY = 10;
 // Top will always point to most recently added element in stack 
 //therefore top = -1 implies stack is empty 
 private int top = -1;
 //array to hold stack elemnts.lt is initialized to capacity of stack
 private String[] stackArray = new String[CAPACITY];

 public static void main(String[] args) {
  StackOfStrings stack = new StackOfStrings();
  stack.pop();
  stack.push("aa");
  stack.push("bb");
  stack.push("cc");
  stack.push("dd");
  stack.push("ee");
  stack.printStack();
  System.out.println("=============================");
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
 }

 public boolean isEmpty() {
  return top == -1;
 } 

 public boolean push(String data) {
  
   // Check if stack is full
   // If it is full then we show Stack overflow message
   
  if (isFull()) {
   System.out.println("Stack overflow");
   return false;
  } else {
   stackArray[++top] = data;
   return true;
  }
 }

 public String pop() {
  
   // Check if stack is empty
   //  If it is empty then we show Stack underflow message
   
  if (isEmpty()) {
   System.out.println("Stack underflow");
  } else {
   // decrementing top by one to sake second element from top as top
   top--;
   // we will be returning top+1 value from array 
   //as we have already made top to point second element in stack
   return stackArray[top + 1];
  }
  return null;
 }

 public String peek() {
  // we implement peek by first popping top element then pushing it back
  String element = null;
  if (!isEmpty()) {
   element = pop();
   push(element);
  }
  return element;
 } 

 public boolean isFull() {
  return top == CAPACITY - 1;
 }

 
  // this method just gives view of the stack.
  // As there are only two operation for stack 
  // i.e. push and pop so in theory we can never print a stack
  // without calling those two methods
  
 public void printStack() {
  System.out.print("[");
  for (int i = top; i >= 0; i--) {
   System.out.print(" " + stackArray[i]);
  }
  System.out.println(" ]");
 } 
}

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

Output

================================================================================

Stack underflow
[ ee dd cc bb aa ]
=============================
ee
dd
cc
bb
aa
Stack underflow
null
Stack underflow
null

Please share your comments if you find anything incorrect, or you want to share more information about the topic discussed above.

For further reading:

practice questions on stack

Stack Implementation using int array

Stack Implementation using char array

Stack implementation using link list

Stack implementation by link list node,

Stack implementation using doubly link list

Stack implementation by doubly link list node .

For complete listing see data structure and algorithm page

Stack Implementaion in Java Using Character Array

2015-03-02T07:22:00.000-08:00

In my previous post we talked about basic stack terminologies and simple stack implementation using integer array.

In this post I will be sharing my code for a stack implementation which can hold char values in other words stack implemented using char array in java.

Sections in this post:

char Array Based Implementation of stack.

Let see the code directly as it is self explanatory

public class StackUsingCharArray {


    // Every stack has a maximum capacity i.e. number of objects it can hold,
    private static final int CAPACITY = 10;
    
    // Top will always point to most recently added element in stack therefore 
    // top = -1 implies stack is empty
     private    int top = -1;
       //array to hold stack elemnts.lt is initialized to capacity of stack
    private    char[] stackArray = new char[CAPACITY];

    public static void main(String[] args) {
        StackUsingCharArray stack = new StackUsingCharArray();
        stack.pop();
        stack.push('a');
        stack.push('b');
        stack.push('c');
        stack.push('d');
        stack.push('e');
        stack.printStack();       
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }
    public boolean isEmpty() {
        return top == -1;
    }

    public boolean push(char data) {
        
         //Check if stack is full
         //If it is full then we show Stack overflow message
         
        if(isFull()) {
            System.out.println("Stack overflow");
            return false;
        }

        else {
            stackArray[++top] =data;
            return true;
        }
    }
    public Character pop() {
        
         // Check if stack is empty
         //If it is empty then we show Stack underflow message 
         
        if(isEmpty()) {
            System.out.println("Stack underflow");
            return null;
        }
        else {
            //decrementing top by one to make second element from top as top element
            top --;
            //we will be returning top+1 value from array as we have already made 
            //top to point second element in stack
            
            return stackArray[top+1];
        }
    }
    public Character peek() {
        // we implement peek by first popping top element then pushing it back
        Character element = null ;
        if(!isEmpty()){
            element = pop();
            push(element);
        }
        return element;
    }
    
    // this method just gives view of the stack. 
    //As there are only two operation for stack i.e. push and pop
    //so in theory we can never print a stack 
    //without calling those two methods
     
    public void printStack() {
        System.out.print("[");
        for(int i = top; i>=0;i--){
            System.out.print("    "+stackArray[i]);
        }
        System.out.println("    ]");
    }
   
    public boolean isFull() {
        return top == CAPACITY -1;
    }
}

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

Output

================================================================================

Stack underflow
[ e d c b a ]
e
d
c
b
a
Stack underflow
null
Stack underflow
null

Please share your comments if you find anything incorrect, or you want to share more information about the topic discussed above.

For further reading:

practice questions on stack

Stack Implementation using int array

Stack Implementation using array of strings

Stack implementation using link list

Stack implementation by link list node,

Stack implementation using doubly link list

Stack implementation by doubly link list node .

For complete listing see data structure and algorithm page

Stack Implementaion in Java Using Integer Array

2015-02-18T09:15:00.002-08:00

This is my first post on stack data structure. In this post I am sharing my code of a simple Stack of integers which is internally implemented using integer array.

Stack

A stack is a basic data structure that can be logically thought as linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack. The basic concept can be illustrated by thinking of your data set as a stack of plates or books where you can only take the top item off the stack in order to remove things from it.

Sections in this post:

Basic stack operations.

Push and Pop
peek
is Full and is Empty

My Stack Interface.
Array Based Implementation.

Basic stack Operations:

Push and Pop

A stack has two fundamental operations - Push and Pop.

The Push operation stores something on the top of the stack and the Pop operation retrives something from the top of the stack.

Peek

Peek operation returns top element from the stack without removing it from the stack. Peek is not a fundamental stack operation but it is usually implemented in stack ADT.

Is Empty and Is Full

When stack is empty and pop operation is called then stack should throw "Stack underflow error" and if stack is already full and pop operation is called then we should throw "Stack overflow error".

So as to avoid these two errors we implement Is Empty and Is Full methods. Similar to peek, "Is Empty" and "Is Full" are also not fundamental stack operation.

My Stack Interface

I am creating Stack interface for my Stack ADT. Lets see the code:

public interface StackInterface {
 
  //Method to push data onto stack
  
 public boolean push(int data);
 
  //Method to pop topmost element from stack or most recently added element in stack
  
 public Integer pop();
 
  // This is not a basic stack operation
  // This method should allow a user to see the top most element in stack
  // it is similar to popping and pushing element again.
  
 public Integer peek();
 
  //method should return true if stack is empty else false
  
 public boolean isEmpty();
 
  //Method should return true if stack is full else false

 public boolean isFull();
}

Array Based Implementation

In an array-based implementation we maintain the following fields:

an array A of a default size (≥ 1),
the variable top that refers to the top element in the stack and
the capacity that refers to the array size.

We say that a stack is empty when top = -1, and the stack is full when top = capacity-1. The variable top changes from -1 to capacity - 1.

Below is my code for implementing integer stack using array:

public class StackUsingIntArray implements StackInterface {
    // Every stack has a maximum capacity i.e. number of objects it can hold.
     private static final int CAPACITY = 10;
 
    //Top will always point to most recently added element in stack therefore
    //top * -1 implies stack is empty
  
    private int top = -1;
    // array to hold stack elemnts.lt is initialized to capacity of stack 
     private int[] stackArray = new int[CAPACITY];        
        
 @Override
 public boolean push(int data) {
  
    //Check if stack is fullIf it is full then we show Stack overflow message
   
     if (isFull()) {
         System.out.println("Stack overflow");
         return false;
     } else {
         stackArray[++top] = data;
         return true;
     }
 }

 @Override
 public Integer pop() {
  
   //Check if stack is empty If it is empty then we show Stack underflow message
   
  if (isEmpty()) {
     System.out.println("Stack underflow");
  } else {
   
    //decrementing top by one to make second element from top as top
   
     top--;

    //we will be returning top+1 value from array as we have already
    //made top to point second element in stack
    
     return (Integer) stackArray[top + 1];

  }
  return null;
 }

 @Override
 public Integer peek() {
     // we implement peek by first popping top element then pushing it back
      Integer element = null;
      if (!isEmpty()) {
         element = pop();
         push(element);
      }
       return element;
 } 
        
 @Override
 public boolean isEmpty() {
     return top == -1;
 }

 @Override
 public boolean isFull() {  
     return top == CAPACITY-1;
 }
        

  //This method just gives view of the stack. As there are only two operation
  //for stack i.e. push and pop so in theory we can never print a stack
  //without calling those two methods
  
 public void printStack() {
     System.out.print("[");
     for (int i = top; i >= 0; i--) {
        System.out.print(" " + stackArray[i]);
     }
     System.out.print(" ]");
 }
        
 public static void main(String[] args) {
  StackUsingIntArray stack = new StackUsingIntArray();
  stack.pop();
  stack.push(40);
  stack.pop();
  stack.push(50);
  stack.pop();
  stack.push(50);
  stack.push(11);
  stack.pop();
  stack.push(50);
  stack.push(32);
  stack.pop();
  stack.pop();
  stack.push(55);
  stack.pop();
  stack.push(68);
  stack.pop();
  stack.push(75);
  stack.push(-12);
  stack.printStack();
  System.out.println();
  System.out.println("=============================");
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  stack.push(1);
  stack.push(2);
  stack.push(3);
  stack.push(4);
  stack.push(5);
  stack.printStack();
 }
}

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

Output

================================================================================

Stack underflow
[ -12 75 50 ]
====================

-12
75
50
Stack underflow
null
Stack underflow
null
Stack underflow
null
Stack underflow
null
[ 5 4 3 2 1 ]

Please share your comments if you find anything incorrect, or you want to share more information about the topic discussed above.

For further reading:

Stack Implementation using char array

Stack Implementation using array of strings

Stack implementation using link list

Stack implementation by link list node,

Stack implementation using doubly link list

Stack implementation by doubly link list node .

For complete listing see data structure and algorithm page

Data structure Questions on Link List

2015-02-16T07:32:00.003-08:00

In my previous posts we talked about single link list, doubly link list. In this post I am sharing my code solution for few practice question which are also frequently asked in interviews too.

Section in this post:

Get Nth node value from end of link list.

Print middle node value.

Get number of occurrence of a number in link list.

Detect loop and print node where loop is present in link list using Floyd Cycle-Finding Algorithm:

Detect loop using Richard Brent's algorithm:

Get Nth node value from end of link list

Given a Linked List and a number n, we need to write a method that returns the value at the nth node from end of the Linked List.

Solution: We maintain two references say First and Second. First we move First to n nodes from head.After that we move both references one by one until First reaches end. Now Second will point to nth node from the end.

Lets see in the code now:

public class LinkListPrograms {
        //Refer my link list post for link list implementation details
 SLL myList = new SLL();

 public static void main(String[] args) {
  LinkListPrograms myProg = new LinkListPrograms();
                
                myProg.myList.insert(new Node(11),1);
  myProg.myList.insert(new Node(42),2);
  myProg.myList.insert(new Node(43),1);
  myProg.myList.insert(new Node(44),1);
  myProg.myList.insert(new Node(45),2);  

  myProg.myList.insert(51,1);
  myProg.myList.insert(52,2);
  myProg.myList.insert(53,1);
  myProg.myList.insert(54,1);
  myProg.myList.insert(55,2);
  myProg.myList.insert(56,4);

  myProg.myList.insertAtStart(1);
  myProg.myList.insertAtStart(2);
  myProg.myList.insertAtStart(3);
  myProg.myList.insertAtStart(4);

  myProg.myList.insertAtStart(new Node(11));
  myProg.myList.insertAtStart(new Node(12));
  myProg.myList.insertAtStart(new Node(13));
  myProg.myList.insertAtStart(new Node(14));
  myProg.myList.printList(myProg.myList.getHead());
  System.out.println("Nth element form last is: "+myProg.getNthFromLast(5));
      }

      public Integer getNthFromLast(int n) {
  // Check if list is already Empty
  if (myList.isEmpty()) {
   System.out.println("List is empty returning null;");
   return null;
  }
  Node firstNode, secondNode;
  firstNode = secondNode = myList.getHead();
  for (int i = 0; i < n; i++) {
   firstNode = firstNode.getNext();
   if (firstNode == null) {
    System.out.println("invalid number given returning null");
    return null;
   }
  }
  while (firstNode != null) {
   firstNode = firstNode.getNext();
   secondNode = secondNode.getNext();
  }
  return secondNode.getData();
 }
}

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

Output

========================================================================

List is: [ 14 13 12 11 4 3 2 1 54 55 53 56 51 52 44 45 43 11 42 ]
Nth element form last is: 44

Print middle node value

We traverse linked list using two pointers. Moving one pointer by one and other pointer by two. When the fast pointer reaches end slow pointer will reach middle of the linked list.

Lets see the code now:

public class LinkListPrograms {
        //Refer my link list post for link list implementation details
 SLL myList = new SLL();

 public static void main(String[] args) {
  LinkListPrograms myProg = new LinkListPrograms();
                
                myProg.myList.insert(new Node(11),1);
  myProg.myList.insert(new Node(42),2);
  myProg.myList.insert(new Node(43),1);
  myProg.myList.insert(new Node(44),1);
  myProg.myList.insert(new Node(45),2);  

  myProg.myList.insert(51,1);
  myProg.myList.insert(52,2);
  myProg.myList.insert(53,1);
  myProg.myList.insert(54,1);
  myProg.myList.insert(55,2);
  myProg.myList.insert(56,4);

  myProg.myList.insertAtStart(1);
  myProg.myList.insertAtStart(2);
  myProg.myList.insertAtStart(3);
  myProg.myList.insertAtStart(4);

  myProg.myList.insertAtStart(new Node(11));
  myProg.myList.insertAtStart(new Node(12));
  myProg.myList.insertAtStart(new Node(13));
  myProg.myList.insertAtStart(new Node(14));
  myProg.myList.printList(myProg.myList.getHead());
                myProg.printMiddle();
      }

      /* method to get the middle of the linked list */
 public void printMiddle() {
 /*
 * We will Traverse linked list using two reference namely fastRef and
 * slowRef Move one first by one and other by two.When the fast ref
 * reaches end slow ref will reach middle of the linked listCheck if
 * list is already Empty
 */

      if (myList.isEmpty()) {
          System.out.println("List is empty");
      }
      Node fastRef, slowRef;
      fastRef = slowRef = myList.getHead();
      while (fastRef != null && fastRef.getNext() != null) {
         fastRef = fastRef.getNext().getNext();
  slowRef = slowRef.getNext();
     }
     System.out.println("Middle node is: " + slowRef.getData()); 
   }
}

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

Output

========================================================================

List is: [ 14 13 12 11 4 3 2 1 54 55 53 56 51 52 44 45 43 11 42 ]
Middle node is: 55

Get number of occurrence of a number in link list

We are require to find how many time a number is present in the list.

Lets see the code now:

public class LinkListPrograms {
        //Refer my link list post for link list implementation details
 SLL myList = new SLL();

 public static void main(String[] args) {
  LinkListPrograms myProg = new LinkListPrograms();
                
                myProg.myList.insert(new Node(11),1);
  myProg.myList.insert(new Node(42),2);
  myProg.myList.insert(new Node(43),1);
  myProg.myList.insert(new Node(44),1);
  myProg.myList.insert(new Node(45),2);  

  myProg.myList.insert(51,1);
  myProg.myList.insert(52,2);
  myProg.myList.insert(53,1);
  myProg.myList.insert(54,1);
  myProg.myList.insert(55,2);
  myProg.myList.insert(56,4);

  myProg.myList.insertAtStart(1);
  myProg.myList.insertAtStart(2);
  myProg.myList.insertAtStart(3);
  myProg.myList.insertAtStart(4);

  myProg.myList.insertAtStart(new Node(11));
  myProg.myList.insertAtStart(new Node(12));
  myProg.myList.insertAtStart(new Node(13));
  myProg.myList.insertAtStart(new Node(14));
  myProg.myList.printList(myProg.myList.getHead());
                System.out.println("occurrence is: "+myProg.getOccurrence(11));
      }

        /*
  * Counts the no. of occurrences of a node (search_for) in a linked list
  * (head)
  */
 Integer getOccurrence(int numTosearchFor) {
  // Check if list is already Empty
  if (myList.isEmpty()) {
   System.out.println("List is empty returning null;");
   return null;
  }
  Node currentNode = myList.getHead();
  int count = 0;
  while (currentNode != null) {
   if (currentNode.getData() == numTosearchFor) {
    count++;
   }
   currentNode = currentNode.getNext();
  }
  return count;
 }
}

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

Output

========================================================================

List is: [ 14 13 12 11 4 3 2 1 54 55 53 56 51 52 44 45 43 11 42 ]
occurrence is: 2

Floyd's Cycle-Finding Algorithm

Floyd's cycle-finding algorithm, also called the "tortoise and the hare algorithm" is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds.

Traverse linked list using two pointers. Move one pointer by one and other pointer by two. If these pointers meet at some node then there is a loop. If pointers do not meet then linked list doesn’t have loop.

Lets see the code now:

public class LinkListPrograms {
        //Refer my link list post for link list implementation details
 SLL myList = new SLL();

 public static void main(String[] args) {
  LinkListPrograms myProg = new LinkListPrograms();
                
                myProg.myList.insert(new Node(11),1);
  myProg.myList.insert(new Node(42),2);
  myProg.myList.insert(new Node(43),1);
  myProg.myList.insert(new Node(44),1);
  myProg.myList.insert(new Node(45),2);  

  myProg.myList.insert(51,1);
  myProg.myList.insert(52,2);
  myProg.myList.insert(53,1);
  myProg.myList.insert(54,1);
  myProg.myList.insert(55,2);
  myProg.myList.insert(56,4);

  myProg.myList.insertAtStart(1);
  myProg.myList.insertAtStart(2);
  myProg.myList.insertAtStart(3);
  myProg.myList.insertAtStart(4); 

               /*
               * Adding two nodes to make a cycle
               */ 
               Node nodeForLoop1 = new Node(22);
        Node nodeForLoop2 = new Node(23);
        nodeForLoop2.setNext(nodeForLoop1); 
                
        myProg.myList.insertAtEnd(nodeForLoop1);
  myProg.myList.insertAtEnd(nodeForLoop2);
      }

      /* Floyd's Cycle-Finding Algorithm */
 public boolean detectloop() {
  /*
   * The fastest way to detect the loop is to use Floyd's Cycle-Finding
   * Algorithm Move one pointer by one and other pointer by two. If these
   * pointers meet at some node then there is a loop. If pointers do not
   * meet then linked list doesn't have loop.
   */

  // Check if list is already Empty
  if (myList.isEmpty()) {
   System.out.println("List is empty returning false:");
   return false;
  }
  Node fastRef, slowRef;
  fastRef = slowRef = myList.getHead();
  while (fastRef != null && fastRef.getNext() != null) {   
   fastRef = fastRef.getNext().getNext();
   slowRef = slowRef.getNext();   
   if (slowRef == fastRef) {
                                //Below method will print node where cycle is present
    getLoopStart(slowRef, fastRef);
    return true;
   }
  }
  return false;
 }

 private void getLoopStart(Node slowRef, Node fastRef) {
  /*
   * Move slowRef to Head. Keep fastRef at Meeting Point. Each are k steps
   * /* from the Loop Start. If they move at the same pace, they must *
   * meet at Loop Start.
   */
  slowRef = myList.getHead();
  while (slowRef != fastRef) {
   slowRef = slowRef.getNext();
   fastRef = fastRef.getNext();
  }
  // Now n2 points to the start of the loop.
  System.out.println("loop at: " + fastRef.getData());
 }
}

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

Output

============================================================================

loop at: 22
Is loop present: true

Richard Brent's Cycle-Finding Algorithm

In 1980, Brent invented an algorithm that not only worked in linear time, but required less stepping than Floyd's Tortoise and the Hare algorithm (however it is slightly more complex).

Brent's algorithm features a moving rabbit and a stationary, then teleporting, turtle. Both turtle and rabbit start at the top of the list. The rabbit takes one step per iteration. If it is then at the same position as the stationary turtle, there is obviously a loop. If it reaches the end of the list, there is no loop.

Of course, this by itself will take infinite time if there is a loop. So every once in a while, we teleport the turtle to the rabbit's position, and let the rabbit continue moving. We start out waiting just 2 steps before teleportation, and we double that each time we move the turtle.

Why move the turtle at all? Well, the loop might not include the entire list; if a rabbit gets stuck in a loop further down, without the turtle, it will go forever. Why take twice as long each time? Eventually, the length of time between teleportations will become longer than the size of the loop, and the turtle will be there waiting for the rabbit when it gets back.

Note that like Floyd's Tortoise and Hare algorithm, this one runs in O(N). However you're doing less stepping than with Floyd's (in fact the upper bound for steps is the number you would do with Floyd's algorithm). According to Brent's research, his algorithm is 24-36% faster on average for implicit linked list algorithms.

Lets see the code now:

public class LinkListPrograms {
        //Refer my link list post for link list implementation details
 SLL myList = new SLL();

 public static void main(String[] args) {
  LinkListPrograms myProg = new LinkListPrograms();
                
                myProg.myList.insert(new Node(11),1);
  myProg.myList.insert(new Node(42),2);
  myProg.myList.insert(new Node(43),1);
  myProg.myList.insert(new Node(44),1);
  myProg.myList.insert(new Node(45),2);  

  myProg.myList.insert(51,1);
  myProg.myList.insert(52,2);
  myProg.myList.insert(53,1);
  myProg.myList.insert(54,1);
  myProg.myList.insert(55,2);
  myProg.myList.insert(56,4);

  myProg.myList.insertAtStart(1);
  myProg.myList.insertAtStart(2);
  myProg.myList.insertAtStart(3);
  myProg.myList.insertAtStart(4);

  myProg.myList.insertAtStart(new Node(11));
  myProg.myList.insertAtStart(new Node(12));
  myProg.myList.insertAtStart(new Node(13));
  myProg.myList.insertAtStart(new Node(14));
  myProg.myList.printList(myProg.myList.getHead());
                System.out.println(myProg.hasLLoop(myProg.myList.getHead()));
      }

     /*
  * Richard Brent's algo: Richard Brent described an alternative cycle
  * detection algorithm,which is pretty much like the hare and the tortoise
  * [Floyd’s cycle] except the slow node here doesn't move, but is later
  * " teleported" to the position of fast node at fixed intervals
  */
 public boolean hasLLoop(Node root) {
  if (root == null) {
   return false;
  }
  Node slow = root, fast = root;
  int taken = 0, limit = 2;
  while (slow.getNext() != null && fast.getNext() != null) {
   fast = fast.getNext();
   taken++;
   if (slow == fast) {
    return true;
   }

   if (taken == limit) {
    taken = 0;

    limit <<= 1; // equivalent to limit *= 2
    slow = fast; // teleporting the turtle to the hare's position
   }
  }
  return false;
 }
}

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

Output

============================================================================

true

Please share your comments if you find anything incorrect, or you want to share more information about the topic discussed above.

I will keep adding more Question here :)

Privacy Policy

2014-06-10T02:39:00.001-07:00

If you require any more information or have any questions about our privacy policy, please feel free to contact us by email at ashvinbhide@gmail.com.

At www.binary-imaginers.blogspot.com, the privacy of our visitors is of extreme importance to us. This privacy policy document outlines the types of personal information is received and collected by www.binary-imaginers.blogspot.com and how it is used.

Log Files
Like many other Web sites, www.binary-imaginers.blogspot.com makes use of log files. The information inside the log files includes internet protocol ( IP ) addresses, type of browser, Internet Service Provider ( ISP ), date/time stamp, referring/exit pages, and number of clicks to analyze trends, administer the site, track user’s movement around the site, and gather demographic information. IP addresses, and other such information are not linked to any information that is personally identifiable.

Cookies and Web Beacons
www.binary-imaginers.blogspot.com does not use cookies.

DoubleClick DART Cookie
.:: Google, as a third party vendor, uses cookies to serve ads on www.binary-imaginers.blogspot.com.
.:: Google's use of the DART cookie enables it to serve ads to users based on their visit to www.binary-imaginers.blogspot.com and other sites on the Internet.
.:: Users may opt out of the use of the DART cookie by visiting the Google ad and content network privacy policy at the following URL - http://www.google.com/privacy_ads.html

Some of our advertising partners may use cookies and web beacons on our site. Our advertising partners include ....
Google Adsense

These third-party ad servers or ad networks use technology to the advertisements and links that appear on www.binary-imaginers.blogspot.com send directly to your browsers. They automatically receive your IP address when this occurs. Other technologies ( such as cookies, JavaScript, or Web Beacons ) may also be used by the third-party ad networks to measure the effectiveness of their advertisements and / or to personalize the advertising content that you see.

www.binary-imaginers.blogspot.com has no access to or control over these cookies that are used by third-party advertisers.

You should consult the respective privacy policies of these third-party ad servers for more detailed information on their practices as well as for instructions about how to opt-out of certain practices. www.binary-imaginers.blogspot.com's privacy policy does not apply to, and we cannot control the activities of, such other advertisers or web sites.

If you wish to disable cookies, you may do so through your individual browser options. More detailed information about cookie management with specific web browsers can be found at the browsers' respective websites.

java program to count minimum number of bits required to convert a given number into another number

2014-06-02T10:07:00.000-07:00

Question: Write a Java program that will return the number of bits that will need to be changed in order to convert an integer, X, into another integer, Y and vice versa.

Explanation: The method should accept two different integers as input. For example, if your method is passed the integers 12 and 16 then your method should return a 3 .

Let's take a closer look at the example given to us. It says that for the input of a 12 and 16, the output of the method should be a 3. Since we are looking for the number of bits that will need to be changed, let's convert 12 and 16 to binary to further understand this bit manipulation problem. The binary representation of 12 is 01100 and the binary representation of 16 is 10000. Comparing the binary representation of those two numbers, we can see that the first 3 digits are different, which means that to convert 12 to 16 or 16 to 12 we would have to change 3 numbers. And that is why the method that we write should output a 3.

Solution:The binary operator that is perfect for this exercise is the XOR operator. If you need a refresher on how that operator works you can read this: XOR in Java. This is because the XOR operator will return true when the binary digits being compared are different, but will return false when they are the same. So, if we just XOR the two numbers being passed in, the result of the XOR operation will be binary number that will have a binary 1 each and every time there is a different bit between the inputs x and y, and a binary 0 when the bits in the input x and y are the same. So, for example, if we XOR 1001 and 0101 the result of the XOR operation would be a 1100 because the 2 leftmost bits are different, so the result of XOR'ing those 2 bits would be a 1 but the 2 rightmost bits in our inputs are the same, so the result of XOR would be a 0.

So, the algorithm to solve this bit manipulation interview question would be:

First, XOR the two numbers being passed in - call them x and y - and then call the result Z.

Then, just count the number of binary 1′s in Z since that count represents the number of different bits in the two numbers x and y. In order to count the number of binary 1′s in Z, we can just take Z, and perform the binary AND operation with the number 1. When the result of that operation is a 1 then we know that the very last binary digit in Z is a 1. Then, we can shift Z by 1 bit and repeat until there is nothing left to shift - which is when Z is equal to 0.

Here is the Java implementation of that algorithm and our final answer to this problem:

Bit-wise and bit shift operations:

public class BitDiffernce {
    public  int findNumberOfBits(int x, int y) {
        int bitCount = 0;
        int z = x ^ y;  //XOR x and y

        while (z != 0) {
            //increment count if last binary digit is a 1:

            bitCount += z & 1;       
            z = z >> 1;  //shift Z by 1 bit to the right
        }
        return bitCount;
    }

    public static void main(String args[]) {
        BitDiffernce bd = new BitDiffernce();
        System.out.println("No of bits needed to change are: "+
                   bd.findNumberOfBits(12, 46));        
    }
}

You will get following output:

Output:                                                      
======================================================

No of bits needed to change are:2

Bitwise and Bit Shift Operators in Java

2014-06-02T09:33:00.000-07:00

This post is all about basic understanding of operators that perform bit-wise and bit shift operations on integral types that Java programming language provides.

Section in this post:

The bitwise operators:

Operator	Name	Example	Result	Description
`a & b`	and	3 & 5	1	1 if both bits are 1.
`a \| b`	or	3 \| 5	7	1 if either bit is 1.
`a ^ b`	xor	3 ^ 5	6	1 if both bits are different.
`~a`	not	~3	-4	Inverts the bits.
`n << p`	left shift	3 <<< 2	12	Shifts the bits of n left p positions. Zero bits are shifted into the low-order positions.
`n >> p`	right shift	5 >> 2	1	Shifts the bits of n right p positions. If n is a 2's complement signed number, the sign bit is shifted into the high-order positions.
`n >>> p`	right shift	-4 >>> 28	15	Shifts the bits of n right p positions. Zeros are shifted into the high-order positions.

Note: "<<<" is not an operator, because it would be redundant. Lets see each operator one by one:

The unary bitwise complement operator:

The unary bitwise complement operator "~" inverts a bit pattern; it can be applied to any of the integral types, making every "0" a "1" and every "1" a "0".
For example: A byte contains 8 bits; applying this operator to a value whose bit pattern is "00000000" would change its pattern to "11111111"

The bitwise `&` operator:

Bitwise AND operator works similar to logical AND operator (&&) and returns 1 if both operands are 1. Difference with bitwise AND and logical AND also known as short-circuit AND operator is that, logical AND operator applies only to boolean type. Also bitwise AND operator is denoted by singe & while short circuit AND operator is denoted by &&.

For example:If A represent 0010 and B represent 1010 then result of A&B would be 0010.

The bitwise `^` operator:

Bitwise XOR operator is denoted by ^ and also work on individual bits. There is no short-circuit XOR operator in Java and result of bitwise XOR operator is XOR operation of individual bits. see the truth table of XOR operation for predicting result. in short bitwise XOR operators will return 1 if both bits are different and return 0 if both bits are same.

The bitwise `|` operator:

Bitwise OR operator is also similar to bitwise AND operator and applies to individual bits. It’s different than short-circuit OR operator, which is denoted by (||) and operates on boolean variable. Bitwise OR operator produce result of OR operation on two bits. Like other bitwise operator in Java, bitwise OR is only applicable to integral types.

Left shift (<<)

Integers are stored, in memory, as a series of bits. For example, the number 6 stored as a 32-bit int would be:

00000000 00000000 00000000 00000110

Shifting this bit pattern to the left one position (6 << 1) would result in the number 12:

00000000 00000000 00000000 00001100

As you can see, the digits have shifted to the left by one position, and the last digit on the right is filled with a zero.

Note: Shifting left is equivalent to multiplication by powers of 2. So 6 << 1 is equivalent to 6 * 2, and 6 << 3 is equivalent to 6 * 8. A good optimizing compiler will substitute shifts for multiplications when possible.

Non-circular shifting :

Please note that these are not circular shifts. Shifting this value to the left by one position (3,758,096,384 << 1):

11100000 00000000 00000000 00000000

results in 3,221,225,472:

11000000 00000000 00000000 00000000

The digit that gets shifted "off the end" is lost. It does not wrap around

Logical right shift (>>>)

A logical right shift is the converse to the left shift. Rather than moving bits to the left, they simply move to the right. For example, shifting the number 12:

00000000 00000000 00000000 00001100

to the right by one position (12 >>> 1) will get back our original 6:

00000000 00000000 00000000 00000110

So we see that shifting to the right is equivalent to division by powers of 2.

Lost bits are gone

However, a shift cannot reclaim "lost" bits. For example, if we shift this pattern:

00111000 00000000 00000000 00000110

to the left 4 positions (939,524,102 << 4), we get 2,147,483,744:

10000000 00000000 00000000 01100000

and then shifting back ((939,524,102 << 4) >>> 4) we get 134,217,734:

00001000 00000000 00000000 00000110

We cannot get back our original value once we have lost bits.

Arithmetic right shift (>>)

The arithmetic right shift is exactly like the logical right shift, except instead of padding with zero, it pads with the most significant bit. This is because the most significant bit is the sign bit, or the bit that distinguishes positive and negative numbers. By padding with the most significant bit, the arithmetic right shift is sign-preserving.

For example, if we interpret this bit pattern as a negative number:

10000000 00000000 00000000 01100000

we have the number -2,147,483,552. Shifting this to the right 4 positions with the arithmetic shift (-2,147,483,552 >> 4) would give us:

11111000 00000000 00000000 00000110

or the number -134,217,722.

So we see that we have preserved the sign of our negative numbers by using the arithmetic right shift, rather than the logical right shift. And once again, we see that we are performing division by powers of 2.

Here a simple java program showing Bit-wise and bit shift operations:

public class tetBitOperator{
 
public static void main(String args[]) {
      int a = 60; /* 60 = 0011 1100 */  
      int b = 13; /* 13 = 0000 1101 */
      int c = 0;

      System.out.println("a="+a);
      System.out.println("b="+b);
      
      c = a & b;       /* 12 = 0000 1100 */ 
      System.out.println("a & b = " + c );

      c = a | b;       /* 61 = 0011 1101 */
      System.out.println("a | b = " + c );

      c = a ^ b;       /* 49 = 0011 0001 */
      System.out.println("a ^ b = " + c );

      c = ~a;          /*-61 = 1100 0011 */
      System.out.println("~a = " + c );

      c = a << 2;     /* 240 = 1111 0000 */
      System.out.println("a << 2 = " + c );

      c = a >> 2;     /* 215 = 1111 */
      System.out.println("a >> 2  = " + c );

      c = a >>> 2;     /* 215 = 0000 1111 */
      System.out.println("a >>> 2 = " + c )
 }
}

Output

==========================================================================

a & b = 12
a | b = 61
a ^ b = 49
~a = -61
a << 2 = 240
a >> 2  = 15
a >>> 2 = 15

Producer Consumer Problem's solution in Java

2014-05-30T04:03:00.000-07:00

From the Wikipedia definition, the producer–consumer problem (also known as the bounded-buffer problem) is a classic example of a multi-process synchronization problem. The problem describes two processes, the producer and the consumer, who share a common, fixed-size buffer used as a queue. The producer's job is to generate a piece of data, put it into the buffer and start again. At the same time, the consumer is consuming the data (i.e., removing it from the buffer) one piece at a time. The problem is to make sure that the producer won't try to add data into the buffer if it's full and that the consumer won't try to remove data from an empty buffer.

The solution for the producer is to either go to sleep or discard data if the buffer is full. The next time the consumer removes an item from the buffer, it notifies the producer, who starts to fill the buffer again. In the same way, the consumer can go to sleep if it finds the buffer to be empty. The next time the producer puts data into the buffer, it wakes up the sleeping consumer. The solution can be reached by means of inter-process communication. An inadequate solution could result in a deadlock where both processes are waiting to be awakened. The problem can also be generalized to have multiple producers and consumers.

In this post I am sharing my producer-consumer solution written in Java.

Producer class:

import java.util.Vector;

public class MyProducer implements Runnable{
 /*taking vector to use as buffer, 
         *it will keep numbers produced by Producer 
  *and work as synchronisation object
        */
 Vector<Integer> sharedQ;
 // Size will store the maximum size of buffer
 int SIZE;
 /*
  * Constructor for Producer class
  */
 public MyProducer(Vector<Integer> sharedQ, final int size) {
  this.sharedQ =sharedQ;
  this.SIZE= size;
 }
 @Override
 public void run() {
  int i=0;
  while(true){
   i++;
   produce(i);
  }
 }
 /*
  * This method has the logic for producing numbers 
         *and synchronization with consumer
  */
 public void produce(int i) {
  //testing if buffer is already full
  while(sharedQ.size() == SIZE) {
   synchronized (sharedQ) {
    try {
     System.out.println("producer waiting...");
     //waiting until some space is made in buffer
     sharedQ.wait();
    } catch (InterruptedException e) {
     // TODO Auto-generated catch block
     e.printStackTrace();
    }
   }
  }
  //adding numbers in buffer
  synchronized(sharedQ) {
   sharedQ.add(i);
   System.out.println("Producer produced: "+i);
   //notifying other thread which are waiting on sharedQ
   sharedQ.notifyAll();
  }
  try {
   /*
    * making thread to sleep for random time after producing  
    *so as to make output more readable and understandable
    *we can set any arbitrary sleeping time
    */
   Thread.sleep(((long)((Math.random())*10000)));
  } catch (InterruptedException e) {
   e.printStackTrace();
  }
 }
}

Consumer class:

import java.util.Vector;

public class MyConsumer implements Runnable {
 
        /*taking vector to use as buffer, 
         *it will keep numbers produced by Producer 
  *and work as synchronisation object
        */ 
        Vector<Integer> sharedQ;
 
 public MyConsumer(Vector<Integer> sharedQ) {
  this.sharedQ = sharedQ;
 }
 
 @Override
 public void run() {
  /*
   * loop will go on forever
   */
  while(true) {
      consumed();
     /*
      * making thread to sleep for random time after consuming  
      *so as to make output more readable and understandable
      *we can set any arbitrary sleeping time
      */
      try {
   Thread.sleep(((long)((Math.random())*20000)));
   
      } catch (InterruptedException e) {   
   e.printStackTrace();
      }
       }
 }
 /*
  * This method has the logic for consuming numbers 
         *and synchronization with producer
  */
 public void consumed() {
  // cheacking if buffer is empty-then consumer has to wait
   while(sharedQ.isEmpty()) {
    synchronized(sharedQ) {
     try {
      System.out.println(Thread.currentThread().getName()+" waiting...");
      sharedQ.wait();
     } catch (InterruptedException e) {
      
      e.printStackTrace();
     }
     
    }
   }
   //consuimng a number from the buffer
   synchronized(sharedQ) {
      System.out.println(Thread.currentThread().getName()+" consumed "+sharedQ.remove(0));
      //notifying other thread which are waiting on sharedQ
      sharedQ.notifyAll();
   }
  }
 
}

Test class:

import java.util.Vector;

public class MyProducerConsumerTest { 
 
 public static void main(String args[]) {
  
        /*taking vector to use as buffer, 
         *it will keep numbers produced by Producer 
  *and work as synchronisation object
         */  
        Vector<Integer> sharedQ = new Vector<Integer>();
        // Size will store the maximum size of buffer
  final int SIZE = 5;
 //Making producer and consumer thread
 Thread producer = new Thread(new MyProducer(sharedQ,SIZE),"producer");
 Thread consumer = new Thread(new MyConsumer(sharedQ),"consumer");
  
 //starting producer/consumer threads
 producer.start();
 consumer.start();
 /*
  * this join is optional- 
  * after join this main thread will never finish as consumer/producer willl run forever
  * to see effect of join we need to make consumer/producer to run for some specific time
  */
  
 try {
  producer.join();
  consumer.join();
   
 } catch (InterruptedException e) {   
  e.printStackTrace();
 }
 /*
  * this will never get printed 
  * unless we remove join call made above or finish execution of producer/consumer threads
  */
 System.out.println("all done");
 }
}

We can make this code to work for multiple producer/consumer scenario just by changing test class and creating multiple threads for producer and consumer.

Modified Test class:

import java.util.Vector;

public class MyProducerConsumerTest { 
 
 public static void main(String args[]) {
  
        /*taking vector to use as buffer, 
         *it will keep numbers produced by Producer 
  *and work as synchronisation object
         */  
        Vector<Integer> sharedQ = new Vector<Integer>();
        // Size will store the maximum size of buffer
  final int SIZE = 5; 
 
     //Making producer and consumer thread
 Thread producer1 = new Thread(new MyProducer(sharedQ,SIZE),"producer1");
        Thread producer2 = new Thread(new MyProducer(sharedQ,SIZE),"producer2"); 
        Thread producer3 = new Thread(new MyProducer(sharedQ,SIZE),"producer3");
        Thread consumer1 = new Thread(new MyConsumer(sharedQ),"consumer1");
        Thread consumer2 = new Thread(new MyConsumer(sharedQ),"consumer2");
        Thread consumer3 = new Thread(new MyConsumer(sharedQ),"consumer3");
        Thread consumer4 = new Thread(new MyConsumer(sharedQ),"consumer4"); 
  
       //starting producer/consumer threads
 producer1.start();
        producer2.start();
        producer3.start(); 
        consumer1.start();
        consumer2.start();
        consumer3.start();
       consumer4.start(); 
        /*
  * this join is optional- 
  * after join this main thread will never finish as consumer/producer willl run forever
  * to see effect of join we need to make consumer/producer to run for some specific time
  */
  
 try {
  producer1.join();
                producer2.join();
               producer3.join(); 
                consumer1.join();
                consumer2.join();
                consumer3.join();
                consumer4.join(); 
        } catch (InterruptedException e) {   
  e.printStackTrace();
 }
 /*
  * this will never get printed 
  * unless we remove join call made above or finish execution of producer/consumer threads
  */
 System.out.println("all done");
 }
}

immutability in Java

2014-05-29T00:55:00.000-07:00

An object is considered immutable if its state cannot change after it is constructed.

Immutable objects are particularly useful in concurrent applications. Since they cannot change state, they cannot be corrupted by thread interference or observed in an inconsistent state.

Sections in this post:

Strategy for Defining Immutable Objects

The following rules define a simple strategy for creating immutable objects.

Don't provide "setter" methods — methods that modify fields or objects referred to by fields.
Make all fields final and private.
Set all instance data in the constructor.
Don't allow sub-classes to override methods. The simplest way to do this is to declare the class as final. A more sophisticated approach is to make the constructor private and construct instances in factory methods.
If the instance fields include references to mutable objects, don't allow those objects to be changed:
- Don't provide methods that modify the mutable objects.
- Clone mutable objects for which a reference to them is returned.
- Clone mutable objects for which a reference to them is received.
- Implement a deep clone if the default shallow clone is not correct for a properly behaved immutable object.

Lets add all above rules and make something concrete class implementation.

By making class final:

This is the most simple way of making a class mutable.

public final class FinalPersonClass {       

      private final String name;
      private final int age;      

      public FinalPersonClass(final String name, final int age) { 

            super();
            this.name = name;
            this.age = age; 
      } 

      public int getAge() { 

            return age;
      } 

      public String getName() { 

            return name;
      }
}

Using Factory methods and making constructor private:

//No need to make class final here 
public class FinalPerson { 
          
     private final String name;
      private final int age;       

      private FinalPerson(final String name, final int age) { 

            super();
            this.name = name;
            this.age = age;
      } 

      public int getAge() { 

            return age;
      } 

      public String getName() { 

            return name; 
      } 

      public FinalPerson getFinalPerson(final String name, final int age) {
           return new FinalPerson(final String name, final int age);
     }
}

Making a class immutable in Java, which includes mutable member variable.

When an immutable class is implemented, mutable objects passed to or returned from an immutable object must be properly cloned. Consider the following class declarations: a DiskDriveInfo class and a User class. The DiskDriveInfo is intended to be immutable. The User encapsulates which user has shared access to the disk drive. The User object with shared access is stored as part of the DiskDriveInfo object. In the following example, the designer of the class was careful to make the class final and all fields private, and to provide only getter methods. Is the DiskDriveInfo class immutable? If not, what needs to be done to make it so?

class User
{
  private String userName;
  private String userID;
  private int userNode;

  User(String name, int node)
  {
    userName = name;
    userNode = node;
  }
  public void setUserName(String name)
  {
    userName = name;
  }
  public void setUserID(String userid)
  {
    userID = userid;
  }
  public void setUserNode(int node)
  {
    userNode = node;
  }
  public String userName()
  {
    return userName;
  }
}

final class DiskDriveInfo
{
  private int driveSize;
  private String volumeLabel;
  private User driveShare;

  DiskDriveInfo(int size, String volLabel, User share)
  {
    driveSize = size;
    volumeLabel = volLabel;
    driveShare = share;
  }
  public int size()
  {
    return driveSize;
  }
  public String label()
  {
    return volumeLabel;
  }
  public User share()
  {
    return driveShare;
  }
}

The DiskDriveInfo class is not immutable. Objects of this class can be changed. Consider the following code that creates a DiskDriveInfo object and tests its immutability:

class Test
{
  private static final int sizeInMeg = 200;
  public static void main(String args[])
  {
    User share1 = new User("Duke", 10);                       //1
    DiskDriveInfo dd = new DiskDriveInfo(sizeInMeg, "myDrive",
                                         share1);             //2
    User share = dd.share();
    System.out.println("User with shared access is " +
                       share.userName());

    share1.setUserName("Fred");                               //3
    System.out.println("User with shared access is " +
                       share.userName());
  }
}

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

Output

================================================================================

User with shared access is Duke
User with shared access is Fred

What went wrong? This code creates a User object, share1, at //1, with the user name Duke. A supposedly immutable DiskDriveInfo object is created at //2 and is passed a reference to the User object. The DiskDriveInfo object is queried, and the shared owner, Duke, is printed. The User object, share1, changes its name to Fred at //3. When the DiskDriveInfo object is queried again for the user name, it discovers that the name changed from Duke to Fred.
The problem is that the DiskDriveInfo constructor receives a reference to the User object and does not make a copy, or clone, of this object. Therefore, the DiskDriveInfo constructor receives a copy of the reference to the User object. Now the DiskDriveInfo object's driveShare field and the local variable, share1, in main of class Test, reference the same object. Therefore, any changes made through either reference affect the same object. Figure shows the object layout after the code at //1 is executed.

After the code at //2 is executed, the object layout looks as shown in Figure

Notice that because the reference to the User object is not cloned, both the share1 and driveShare references share the same User object. After the code at //3 is executed, the object layout as shown in Figure.

To correct this problem, the DiskDriveInfo class must clone any mutable object to which it receives a reference. It then has a reference to its own copy of the object that cannot be changed by other code.
The modified DiskDriveInfo class that supports cloning looks like this:

final class DiskDriveInfo
{
  //As before...
  DiskDriveInfo(int size, String volLabel, User share)
  {
    driveSize = size;
    volumeLabel = volLabel;
    driveShare = (User)share.clone();
  }
  public User share()
  {
    return (User)driveShare.clone();
  }
}

Because you are cloning the User object, its definition must change as well.

class User implements Cloneable
{
  //As before...
  public Object clone()
  {
    try {
      return super.clone();
    }
    catch (CloneNotSupportedException e) {
      //This should not happen, since this class is Cloneable.
      throw new InternalError();
    }
  }
}

With these changes to the User object, running the previous test code produces the correct output:

Output

================================================================================

User with shared access is Duke
User with shared access is Fred

Because the User object is cloned on the constructor call, the code that subsequently changes the User object at //1 has no effect on the DiskDriveInfo object. The implementation of the immutable DiskDriveInfo class is now correct. The object layout looks as shown in Figure

Achieving Immutability with Builder Design Pattern:

In most of the classes in our real applications there are many fields. Also, most of these fields are not mandatory for object creation. For example, a user in a real application will have a username, password, firstname, lastname, creationDate, emailAddress, etc., but for user creation here, only a username and password are required.

The Builder Pattern separates the construction of a complex object from its representation so that the same construction process can create different representations.
The builder design pattern provides a way for you to build complex immutable objects. The process is:

The client calls a constructor (or static factory) with all the required parameters and gets a builder object.
The client calls setter like methods to set each optional parameter of interest.
Finally the client calls the build method to generate the object which is immutable.

import java.math.BigDecimal;

/**
* Immutable, hence thread safe CashBalance objec
*/

public final class CashBalance {
  
 private BigDecimal initialBalance, totCredits, totDebits;
  
  //construct
  public CashBalance(CashBalanceBuilder builder) {
  this.initialBalance = builder.initialBalance;
  this.totCredits = builder.totCredits;
  this.totDebits = builder.totDebits;
 }
    
 public static class CashBalanceBuilder {
   
  //has same fields as the object it is going to build
   protected BigDecimal initialBalance, totCredits, totDebits;
  //define the setters that return itself
   CashBalanceBuilder setInitialBalance(BigDecimal initialBalance) {
   this.initialBalance = initialBalance;
   return this;
  }
   CashBalanceBuilder setTotCredits(BigDecimal totCredits) {
    this.totCredits = totCredits;
   return this;
  }
  CashBalanceBuilder setTotDebits(BigDecimal totDebits) {
   this.totDebits = totDebits;
   return this;
  }
 }
  
 //only getter methods and no setter methods as it is an immutable object
}

The client code will look like this :

public static void main(String[] args) {
   CashBalance.CashBalanceBuilder builder = 
           new CashBalance.CashBalanceBuilder(
                    .setInitialBalance(BigDecimal.valueOf(250.00))
                    .setTotCredits(BigDecimal.valueOf(250.00))
                    .setTotDebits(BigDecimal.valueOf(250.00));
                    CashBalance bal = new CashBalance(builder);
}

How to use Date object in immutable class

This is a commonly asked scenario in interviews while discussing about immutable classes.
Some time you may need to write immutable class which includes mutable classes like java.util.Date, despite storing Date into final field it can be modified internally, if internal date is returned to the client. In order to preserve immutability in such cases, its advised to return copy of original object.

Consider the below code:

public final class ImmutableReminder{

    private final Date remindingDate;
  

    public ImmutableReminder (Date remindingDate)
    {
        if(remindingDate.getTime() < System.currentTimeMillis()){

            throw new IllegalArgumentException("Can not
                   set reminder” + “ for past time: " + remindingDate);
         }
         // creating new object of Date first
this.remindingDate = new Date(remindingDate.getTime());
    }

    public Date getRemindingDate() {
      //returning clone of the date object 
     return (Date) remindingDate.clone();
    }
}

serialVersionUID

2014-05-28T06:01:00.001-07:00

When you serialize an object using Serialization mechanism (by implementing Serializable interface), there is a possibility that you may face versioning issues and because of these versioning issues, you will not be able to deserialize the object.

Sections in this post:

Problem to face
Root of the problem
Solution
What is serialVersionUID
Example
When to update serialVersionUID

Compatible changes
Incompatible changes

Problem scenario....

lets say you created a class, instantiated it, and wrote it out to an object stream. That flattened object sits in the file system for some time. Meanwhile, you update the class file, perhaps adding a new field. Now try to read the flattened object. An exception "java.io.InvalidClassException" will be thrown.

Root of the problem

lets first see what is actually causing this problem? Why should any change in a serialized class throw "InvalidClassException". During object serialization, the default Java serialization mechanism writes the metadata about the object, which includes the class name, field names and types, and superclass. All this information is stored as part of the serialized object.
When you deserialize the object, this information is read to reconstitute the object. But to perform the deserialization, the object needs to be identified first and this will be done by serialVersionUID. So everytime an object is serialized the java serialization mechanism automatically computes a hash value using ObjectStreamClass’s computeSerialVersionUID() method by passing the class name, sorted member names, modifiers, and interfaces to the secure hash algorithm (SHA), which returns a hash value, the serialVersionUID.

Now when the serilaized object is retrieved, the JVM first evaluates the serialVersionUID of the serialized class and compares the serialVersionUID value with the one of the object. If the sserialVersionUID values match then the object is said to be compatible with the class and hence it is de-serialized. If not InvalidClassException exception is thrown.

And the solution is...

The solution is very simple. Instead of relying on the JVM to generate the serialVersionUID, you explicitly mention (generate) the serialVersionUID in your class. The syntax is:

 private final static long serialVersionUID = <integer value>

What is serialVersionUID?

Its a static, private variable in the class. Once you define the serialVersionUID in your class explicitly, you don't need to update it until and unless you make the incompatible changes.

Example:

Consider the same example taken from serialization post to explain the issue and importance of maintaining serialVersionUID.


import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.Calendar;
import java.util.Date;

public class MyDateObject implements Serializable{
   
    //first time we keep serial VersionUID as 1L
    private static final long serialVersionUID = 1L;
    private Date date;

    public MyDateObject() {
        //date= Calendar.getInstance().getTime();
         calculateCurrentTime();
    }

    public Date getDate() {
        return date;
    }

    public void setDate(Date date) {
        this.date=date;
     } 
    
    private void calculateCurrentTime(){
        date = Calendar.getInstance().getTime();
    }
    
    private void writeObject(ObjectOutputStream out) throws IOException {
        out.defaultWriteObject();
    }

    private void readObject(ObjectInputStream in) 
        throws IOException, ClassNotFoundException{

        // our "pseudo-constructor"
        in.defaultReadObject();
        // now perfrom same operation you need to do in constructor
        calculateCurrentTime();
    }
}

Class to serialize MayDate object :

import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectOutputStream;

//Class to persist the time in a flat file time.ser
public class WriteSerialClass {

  public static void main(String [] args) {
      String filename = "c://time.txt";

      if(args.length > 0){
          filename = args[0];
      }
       
      MyDateObject time = new MyDateObject();
      FileOutputStream fos = null;
      ObjectOutputStream out = null;

      try{
          fos = new FileOutputStream(filename);
          out = new ObjectOutputStream(fos);
          out.writeObject(time);
          out.close();
      }catch(IOException ex){
          ex.printStackTrace();
      }
   }
}

Class to De-serialize MydateObject:

import java.io.FileInputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.util.Calendar;

public class ReadSerialClass   {

     public static void main(String [] args) {
            String filename = "c://time.txt";

            if(args.length > 0){
                filename = args[0];
            }
            
            MyDateObject time = null;
            FileInputStream fis = null;
            ObjectInputStream in = null;

            try{
                fis = new FileInputStream(filename);
                in = new ObjectInputStream(fis);
                time = (MyDateObject)in.readObject();
                in.close();
            }catch(IOException ex){
                ex.printStackTrace();
            }catch(ClassNotFoundException cnfe){
                cnfe.printStackTrace();
            }

            // print out restored time
            System.out.println("Restored time: " + time.getDate());

            // print out the current time
            System.out.println("Current time: " 
                + Calendar.getInstance().getTime());

         }
     }

Output:

=======================================================

Restored time: Wed May 28 18:11:41 IST 2014
Current time: Wed May 28 18:11:42 IST 2014

Now run the following program again by changing serialVersionUID value in myDateObject class:

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.Calendar;
import java.util.Date;

public class MyDateObject implements Serializable{
   
   //Now we change serial VersionUID as 2L
    private static final long serialVersionUID = 2L;
    private Date date;

    public MyDateObject() {
        //date= Calendar.getInstance().getTime();
         calculateCurrentTime();
    }

    public Date getDate() {
        return date;
    }

    public void setDate(Date date) {
        this.date=date;
     } 
    
    private void calculateCurrentTime(){
        date = Calendar.getInstance().getTime();
    }
    
    private void writeObject(ObjectOutputStream out) throws IOException {
        out.defaultWriteObject();
    }

    private void readObject(ObjectInputStream in) 
        throws IOException, ClassNotFoundException{

        // our "pseudo-constructor"
        in.defaultReadObject();
        // now perfrom same operation you need to do in constructor
        calculateCurrentTime();
    }
}

Output:

=========================================================

java.io.InvalidClassException: com.MyDateObject; local class incompatible: stream classdesc serialVersionUID = 1, local class serialVersionUID = 2
    at java.io.ObjectStreamClass.initNonProxy(Unknown Source)
    at java.io.ObjectInputStream.readNonProxyDesc(Unknown Source)
    at java.io.ObjectInputStream.readClassDesc(Unknown Source)
    at java.io.ObjectInputStream.readOrdinaryObject(Unknown Source)
    at java.io.ObjectInputStream.readObject0(Unknown Source)
    at java.io.ObjectInputStream.readObject(Unknown Source)

The reason of the above error is the version change and exactly this is the reason for maintaining the version.
By maintaining version we keep the serialization/de-serialiation consistent

When to update serialVersionUID?

Adding serialVersinUID manually to the class does not mean that it should never be updated and never need not be updated. There is no need to update the serialVersionUID if the change in the class is compatible but it should be updated if the change is incompatible

Some of compatible changes are:

Adding field.
Adding classes.
Removing classes.
Adding writeObject/readObject methods.
Removing writeObject/readObject methods.
Adding java.io.Serializable.
Changing the access to a field.
Changing a field from static to nonstatic or transient to nontransient.

Some of the Incompatible changes are:

Deleting fields.
Moving classes up or down the hierarchy.
Changing a nonstatic field to static or a nontransient field to transient.
Changing the declared type of a primitive field.
Changing the writeObject or readObject method.
Changing a class from Serializable to Externalizable or visa-versa.
Removing either Serializable or Externalizable.
Adding the writeReplace or readResolve method.

Serialization in Java

2014-05-28T03:48:00.003-07:00

Serialization is the process of converting an object's state (including its references) to a sequence of bytes, as well as the process of rebuilding those bytes into a live object at some future time.

Sections in this post:

Some uses of serailization
Serializable Interface
Serialization steps
readObject and writeObjectMethods
FAQ

Serialization is used when you want to persist the object. It is also used by RMI to pass objects between JVMs, either as arguments in a method invocation from a client to a server or as return values from a method invocation. In general, serialization is used when we want the object to exist beyond the lifetime of the JVM.

Here are some uses of serialization

To persist data for future use.
To send data to a remote computer using such client/server Java technologies as RMI or socket programming.
To "flatten" an object into array of bytes in memory.
To exchange data between applets and servlets.
To store user session in Web applications.
To activate/passivate enterprise java beans.
To send objects between the servers in a cluster.

Java provides Serialization API, a standard mechanism to handle object serialization. To persist an object in java, we need to follow following steps.

the first step is to flatten the object. For that the respective class should implement "java.io.Serializable" interface. We don't need to implement any methods as this interface do not have any methods. This is a marker interface/tag interface. Marking a class as Serializable indicates the underlying API that this object can be flattened.

import java.io.Serializable;
import java.util.Calendar;
import java.util.Date;

public class MyDateObject implements Serializable{

    private static final long serialVersionUID = -5315058568373987829L;
    private Date date;

    public MyDateObject() {
        date= Calendar.getInstance().getTime();
    }

    public Date getDate() {
        return date;
    }

    public void setDate(Date date) {
        this.date=date;
     }
}

2. Next step is to actually persist the object. To persist an object we need to use node stream to write to file systems or transfer a flattened object across a network. We can use java.io.ObjectOutputStream class for this. So to write an object you use "writeObject(<<instance>>)" method of "java.io.ObjectOutputStream" class and to read an object you use "readObject()" method of "java.io.ObjectOutputStream" class.

Note: "readObject()" can read only serialized object, that means if the class does not implement "java.io.Serializable" interface, "readObject()" cannot read that object.

import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectOutputStream;


//Class to persist the time in a flat file time.txt
public class WriteSerializeClass {

  public static void main(String [] args) {
       String filename = "c://time.txt";
       if(args.length > 0){
          filename = args[0];
       }       

      MyDateObject time = new MyDateObject();
      FileOutputStream fos = null;
      ObjectOutputStream out = null;

      try{

          fos = new FileOutputStream(filename);
          out = new ObjectOutputStream(fos);
          out.writeObject(time);
          out.close();
      }catch(IOException ex){
          ex.printStackTrace();
      }
   }
}

import java.io.FileInputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.util.Calendar;
//Class to read the time from a flat file time.txt
public class ReadSerializeClass   {

  public static void main(String [] args) {
         String filename = "c://time.txt";

         if(args.length > 0){
             filename = args[0];
         }
   
         MyDateObject time = null;
         FileInputStream fis = null;
         ObjectInputStream in = null;

         try{
             fis = new FileInputStream(filename);
             in = new ObjectInputStream(fis);
             time = (MyDateObject)in.readObject();
             in.close();
         }catch(IOException ex){
             ex.printStackTrace();
         }catch(ClassNotFoundException cnfe){
             cnfe.printStackTrace();
         }

         // print out restored time
         System.out.println("Restored time: " + time.getDate());

         // print out the current time
         System.out.println("Current time: " 
                      + Calendar.getInstance().getTime());
      }
  }

readObject and writeObject methods:

To enhance the normal process of serialization/de-serialization provide two methods inside your serializable class. Those methods are:

private void writeObject(ObjectOutputStream out) throws IOException;
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException;

Let's look at one example

Without readObjet()/writeObject()

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.Calendar;
import java.util.Date;

public class MyDateObject implements Serializable{
    
 
    private static final long serialVersionUID = -5315058568373987829L;
    private Date date;

    public MyDateObject() {
        //date= Calendar.getInstance().getTime();
        calculateCurrentTime();
    }

    public Date getDate() {
        return date;
    }

    public void setDate(Date date) {
     this.date=date;
     } 
    
    private void calculateCurrentTime(){
        date = Calendar.getInstance().getTime();
    }
 }

Output:
=================================================================

Restored time: Wed May 28 15:54:31 IST 2014
Current time: Wed May 28 15:54:34 IST 2014

Now we will add the two methods: readObjet()/writeObject()

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.Calendar;
import java.util.Date;

public class MyDateObject implements Serializable{    
 
   private static final long serialVersionUID = -5315058568373987829L;
   private Date date;

    public MyDateObject() {
        //date= Calendar.getInstance().getTime();
        calculateCurrentTime();
    }

    public Date getDate() {
        return date;
    }

    public void setDate(Date date) {
        this.date=date;
     } 
    
    private void calculateCurrentTime(){
        date = Calendar.getInstance().getTime();
    }    //Adding writObject()
    private void writeObject(ObjectOutputStream out) throws IOException {
        out.defaultWriteObject();
    }      //Adding readObject()
    private void readObject(ObjectInputStream in) 
                         throws IOException, ClassNotFoundException{

         in.defaultReadObject();
        // now perfrom same operation you need to do in constructor
        calculateCurrentTime();
    }
}

Output:

=========================================================================

Restored time: Wed May 28 16:08:26 IST 2014
Current time: Wed May 28 16:08:26 IST 2014

So by overriding these two methods, we can easily get desired serialization/de-serialization behavior.

Note: serialization does not care about access modifiers. It serializes all private, public and protected fields.

Again there is one more way to serialize the object - create your own protocol with the Externalizable interface. Instead of implementing the Serializable interface, you can implement Externalizable, which contains two methods:

public void writeExternal(ObjectOutput out) throws IOException;
public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException;

The Externalization is discussed as separate post. Check it out here .

Some FAQ:

why readObject And writeObject declared as private?

Ans: We don't want these methods to be overridden by subclasses. Instead, each class can have its own writeObject method, and the serialization engine will call all of them one after the other. This is only possible with private methods (these are not overridden). (The same is valid for readObject.)
That's why both methods are declared private . The trick here is that the virtual machine will automatically check to see if either method is declared during the corresponding method call. The virtual machine can call private methods of your class whenever it wants but no other objects can. Thus, the integrity of the class is maintained and the serialization protocol can continue to work as normal.

2. How stop from serailizing one of the sub class of a serializable class?

Ans:To stop the automatic serialization, we can once again override the readObject/writeObject methods to just throw the NotSerializableException in our class.

private void writeObject(ObjectOutputStream out) throws IOException{

    throw new NotSerializableException("Dont Serialize");
}

private void readObject(ObjectInputStream in) throws IOException{

    throw new NotSerializableException("Dont Serialize");
}

Simple Example to show Dependency inversion using Spring

2014-05-12T23:54:00.004-07:00

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/

Java Program to merge two sorted Arrays

2014-03-29T05:24:00.002-07:00

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

2014-03-29T05:10:00.001-07:00

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

2014-03-29T04:55:00.002-07:00

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

Tree Terminology

2014-03-26T03:24:00.000-07:00

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

Cloning in Java

2014-03-04T03:42:00.004-08:00

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:

Default Java cloning

Cloneable Interface

Shallow cloning

Deep cloning

Deep cloning by overriding clone method
Deep cloning using copy constructor
Deep cloning using The factory Method
Deep cloning by Serialzation

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

First statement guarantees that cloned object will have separate memory address assignment.
Second statement suggest that original and cloned objects should have same class type, but it is not mandatory.
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

Tower of Hanoi solution using recursion in java

2014-02-26T06:24:00.001-08:00

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:

Problem statement
Iterative solution
Alternate iterative solution
Recursive solution
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:

Only one disk can be moved at a time.
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.
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 2ⁿ - 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 2ⁿ-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:

move n−1 discs from A to B. This leaves disc n alone on peg A
move disc n from A to C
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

2014-02-26T05:57:00.001-08:00

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);
}
}

Doubly Link List In Java

2014-02-20T21:59:00.004-08:00

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.

Sections in this post:

Link List Interface
Link List Node
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.

Link list Implementation in Java

2014-02-20T21:51:00.003-08:00

linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence.

A linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list.

Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, including lists (the abstract data type), stacks, queues, associative arrays.

Sections in this post:

Link List Interface
Link List Node
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
    private int data;

    // Reference(Pointer) to next node
    private Node next;

    public Node(int data) {
        super();
        this.data = data;
        this.next = 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;
    }
}

Implementation

Now lets see how to implement link list. Whenever I am saying link list I am referring to singly link list. refer my other posts for Doubly link list and circular link list .

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 specified 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 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 specified to insert node");
            return false;
          }

            /* Now we need to insert new node at this location.
             * So we 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 empty,can not perform 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();
        head = head.getNext();
        return deletedNodeValue;
    }

    @Override
    public Integer deleteLast() {

        //Check if list is already Empty 
 if(isEmpty()) {
  System.out.println("List is empty, return null, can not perform delete operation");  
  return null;
 }

 if(head.getNext() == null) {
  int deletedNode = head.getData() ;
  head = null;
  return deletedNode;
 }
 Node currentNode = head.getNext();
 Node prevNode = head;
 while(currentNode.getNext() != null) { 
  prevNode =currentNode;
  currentNode = currentNode.getNext();
 }
 int deletedNode = currentNode.getData(); 
 currentNode = null; 
 prevNode.setNext(null); 
 return deletedNode;
    }

    @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 specified to delete");
            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 specified to delete");
            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 don't want to execute this check twice
         * by putting below isEmpty check at start of this method call
         */
        
        if (isEmpty()) {

          System.out.println("List empty,can not perform 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 specified to insert node
Invalid Location specified to insert node
Node you are trying to insert is null
Invalid Location specified 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   ]
===========================deletefirst=============================
List is: [   11   4   3   2   1   54   55   53   56   44   52   45   43   46   21   22   23   24   31   32   33   34   ]
==========================delete from location========================
Invalid Location specified to delete node
Invalid Location specified 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   ]
==========================delete this(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   ]

In next post we will talk about doubly Link List and Circular Link List and then some commonly asked question based on link list.

Key codes for java script

2011-12-28T23:17:00.000-08:00

Key Code Reference Table

0		10		20	Caps Lock	30		40	Arrow Down
1		11		21		31		41
2		12		22		32		42
3		13	Enter	23		33	Page Up	43
4		14		24		34	Page Down	44
5		15		25		35	End	45	Insert
6		16	Shift	26		36	Home	46	Delete
7		17	Ctrl	27	Esc	37	Arrow Left	47
8	Backspace	18	Alt	28		38	Arrow Up	48	0
9	Tab	19	Pause/Break	29		39	Arrow Right	49	1

50	2	60		70	f	80	p	90	z
51	3	61	=+	71	g	81	q	91	Windows
52	4	62		72	h	82	r	92
53	5	63		73	i	83	s	93	Right Click
54	6	64		74	j	84	t	94
55	7	65	a	75	k	85	u	95
56	8	66	b	76	l	86	v	96	0 (Num Lock)
57	9	67	c	77	m	87	w	97	1 (Num Lock)
58		68	d	78	n	88	x	98	2 (Num Lock)
59	;:	69	e	79	o	89	y	99	3 (Num Lock)
100	4 (Num Lock)	110	. (Num Lock)	120	F9	130		140
101	5 (Num Lock)	111	/ (Num Lock)	121	F10	131		141
102	6 (Num Lock)	112	F1	122	F11	132		142
103	7 (Num Lock)	113	F2	123	F12	133		143
104	8 (Num Lock)	114	F3	124		134		144	Num Lock
105	9 (Num Lock)	115	F4	125		135		145	Scroll Lock
106	* (Num Lock)	116	F5	126		136		146
107	+ (Num Lock)	117	F6	127		137		147
108		118	F7	128		138		148
109	- (Num Lock)	119	F8	129		139		149

150		160		170		180		190	.>
151		161		171		181		191	/?
152		162		172		182	My Computer	192	`~
153		163		173		183	My Calculator	193
154		164		174		184		194
155		165		175		185		195
156		166		176		186		196
157		167		177		187		197
158		168		178		188	,<	198
159		169		179		189		199
200		210		220	\\|	230		240
201		211		221	]}	231		241
202		212		222	'"	232		242
203		213		223		233		243
204		214		224		234		244
205		215		225		235		245
206		216		226		236		246
207		217		227		227		227
208		218		228		238		248
209		219	[{	229		239		249

AJAX Notes

2011-11-21T22:56:00.001-08:00

AJAX

1. AJAX= Asynchronous JavaScript and XML

2. AJAX applications are Browser and platform independent

3. XMLHttpRequest object: - is used to exchange data with a server behind the scenes. This means that it is possible to update parts of a web page without reloading the whole page.

4. Syntax for creating XMLHttpRequest object:

Variable xmlhttp =new XMLHttpRequest (); //for IE 7+, Firefox and chrome

Variable xmlhttp = new ActiveXObject (“Microsoft.XMLHTTP”); //for IE 5 and IE 6

5. To handle both type of browser:

Var xmlhttp;

If (window.XMLHTTPRequest)

{

// code for IE 7+, Firefox, chrome, opera, safari

Xmlhttp= new XMLHTTPRequest ();

}

Else

{

// code for IE 5 and IE 6

Xmlhttp= new ActiveXObject (“Microsoft.XMLHTTP”);

}

6. to send a request to a server, we use open() and send() methods of XMLHttpRequest object

xmlhttp.open (“GET”,”ajax.info.txt”,true);

xmlhttp.send ();

7. Syntax is:

Open (method,URL,async)

Send (String) //String is only used for post

8. Two XMLHttpRequest object properties are:

a. responseText

b. responseXML

9. the onereadystatechange event is triggered every time the ready state changes.

10. Three important properties of the XMLHttpRequest object:

Property	Description
onreadystatechange	Stores a function (or the name of a function) to be called automatically each time the readyState property changes
readyState	Holds the status of the XMLHttpRequest. Changes from 0 to 4: 0: request not initialized 1: server connection established 2: request received 3: processing request 4: request finished and response is ready
status	200: "OK" 404: Page not found

JQuery short notes

2011-11-17T23:41:00.001-08:00

1. JQuery is a JavaScript library

2. Features of JQuery

· HTML element selection

· HTML element manipulation

· CSS manipulation

· HTML event functions

· JavaScript effect and animation

· AJAX

· Utilities

3. To add JQuery to a page

<head>

</script>

</head>

JQury tag should be inside <head > tag

4. Two version of JQuery are available

· Minified

· Uncompressed( for debugging and testing purpose)

5. To use hosted library from Google

<head>

</script>

</head>

6. JQuery Syntax:

$(selector).action()

7. Document Ready function skeleton

$(document).ready(function){

- - - - - - - - -

- - - -- - - - - -

});

This is done to prevent any JQuery code from running before the document is finished loading

Ex.:- Trying to hide an element that doesn’t exist

Trying to get size of an image that is not loaded

8. JQuery selector allows to select HTML element by

· Element name

· Attribute name

· Content

9. Element selector example:

· $("p") selects all <p> elements.

· $("p.intro") selects all <p> elements with class="intro".

· $("p#demo") selects all <p> elements with id="demo".

10. Attribute selection Example: jQuery uses XPath expressions to select elements with given attributes.

· $("[href]") select all elements with a href attribute.

· $("[href='#']") select all elements with a href value equal to "#".

· $("[href!='#']") select all elements with a href attribute NOT equal to "#".

· $("[href$='.jpg']") select all elements with a href attribute that ends with ".jpg".

11. CSS selection example:

· $("p").css("background-color","blue");

12. Some more Examples

Selector	Example	Selects
*	$("*")	All elements
.class.class	$(".intro.demo")	All elements with the classes "intro" and "demo"
:first	$("p:first")	The first p element
:last	$("p:last")	The last p element
:even	$("tr:even")	All even tr elements
:odd	$("tr:odd")	All odd tr elements

:eq(index)	$("ul li:eq(3)")	The fourth element in a list (index starts at 0)
:gt(no)	$("ul li:gt(3)")	List elements with an index greater than 3
:lt(no)	$("ul li:lt(3)")	List elements with an index less than 3
:not(selector)	$("input:not(:empty)")	All input elements that are not empty
:animated	$(":animated")	All animated elements
:contains(text)	$(":contains('W3Schools')")	All elements which contains the text
:empty	$(":empty")	All elements with no child (elements) nodes
[attribute=value]	$("[href='default.htm']")	All elements with a href attribute value equal to "default.htm"
[attribute$=value]	$("[href$='.jpg']")	All elements with a href attribute value ending with ".jpg"

13. To put JQuery functions in a separate file is always a god idea. To use that js file

14. The jQuery noConflict() method specifies a custom name (like jq), instead of using the dollar sign.

<html>

<head>

var jq=jQuery.noConflict();

- jq(document).ready(function(){

- - - - -

});

</script>

</head>

</html>

15. The syntax of jQuery's method for making custom animations is:

$(selector).animate({params},[duration],[easing],[callback])

16. JavaScript statements are executed line by line. However, with animations, the next line of code can be run even though the animation is not finished. This can create errors. To prevent this, you can create a callback function. A callback function is executed after the current animation (effect) is finished.

17. Changing HTML Content

· $(selector).html(content)

· $(selector).append(content)

· $(selector).prepend(content)

· $(selector).after(content)

· $(selector).before(content)

18. The css() method has three different syntaxes, to perform different tasks.

· css(name) - Return CSS property value

· css(name,value) - Set CSS property and value

· css({properties}) - Set multiple CSS properties and values

19. The jQuery load() method is a simple (but very powerful) AJAX function. It has the following syntax:

$(selector).load(url,data,callback)

20. $.ajax(options) is the syntax of the low level AJAX function.

code forum

Fail Fast And Fail Safe Iterator In Java

What is Concurrent Modification?

Fail fast Iterator

How Fail Fast Iterator come to know that the internal structure is modified ?

Fail safe Iterator

Stack of Strings Implemented in Java

Stack Implementaion in Java Using Character Array

Stack Implementaion in Java Using Integer Array

Stack

Basic stack Operations:

Push and Pop

Peek

Is Empty and Is Full

My Stack Interface

Array Based Implementation

Data structure Questions on Link List

Get Nth node value from end of link list

Print middle node value

We traverse linked list using two pointers. Moving one pointer by one and other pointer by two. When the fast pointer reaches end slow pointer will reach middle of the linked list.

Get number of occurrence of a number in link list

Floyd's Cycle-Finding Algorithm

Richard Brent's Cycle-Finding Algorithm

Privacy Policy

java program to count minimum number of bits required to convert a given number into another number

Bitwise and Bit Shift Operators in Java

The bitwise operators:

The unary bitwise complement operator:

The bitwise & operator:

The bitwise ^ operator:

The bitwise | operator:

Left shift (<<)

Non-circular shifting :

Logical right shift (>>>)

Lost bits are gone

Arithmetic right shift (>>)

Producer Consumer Problem's solution in Java

Consumer class:

Test class:

We can make this code to work for multiple producer/consumer scenario just by changing test class and creating multiple threads for producer and consumer.

Modified Test class:

immutability in Java

Strategy for Defining Immutable Objects

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

serialVersionUID

Serialization in Java

Simple Example to show Dependency inversion using Spring

Java Program to merge two sorted Arrays

Java Program to find all combinations of a string

java Program to find if two Strings are Anagrms

Tree Terminology

Traversals

Binary Search Trees

Insertion

Searching

Deletion

Cloning in Java

Java cloning

Shallow Cloning

Deep cloning

2. Deep Cloning Using Copy Constructors

4. Deep cloning with serialization

The Summery

Tower of Hanoi solution using recursion in java

Iterative solution

Simpler statement of iterative solution

Equivalent iterative solution

Recursive solution

Factorial of a number using recursion in Java

The bitwise `&` operator:

The bitwise `^` operator:

The bitwise `|` operator: