Singleton pattern in java and singleton implentation

Singleton Pattern: 
Singleton pattern in java means there should only be a single instance(object) of the class across the application.

Implementation :
Singleton can be implemented in various ways, following program depicts Singleton implementation.
Comments are given for each type of singleton implementation.

There are certain issues which can break Singleton pact:

•  Using Reflection one can call the constructor and initialize an Object. - To prevent throw an exception inside constructor.
• Using Serialization - To prevent return same instance in readResolve().
• Using clone - To prevent throw error in clone().

import java.lang.reflect.Constructor;

/**
 * @author vikky.agrawal
 * @see http://stackoverflow.com/questions/20421920/what-are-the-different-ways-we
 *      -can-break-a-singleton-pattern-in-java
 */

public class Singleton {
// here volatile works with java 1.5 and above.
    private volatile static Singleton single_instance;

    private Singleton() {
        // preventing reflection
        if (single_instance != null) {
            throw new IllegalStateException(
                    "Singleton instance already created.");
        }
        System.out.println("Singleton constructor running");

    }

    public static Singleton getSingleton() {

        // double lock mechanism
        if (single_instance == null) {
            // if 1st thread is executing here then second thread might have checked 
            // above condition hence both threads may exist here.
            synchronized (Singleton.class) {
                // prevent multiple threads from creating 2 instances.(2 phase
                // lock)
                if (single_instance == null)
                    single_instance = new Singleton();
            }
        }
        return single_instance;
    }

    // preventing de-serialization
    protected Object readResolve() {
        return getSingleton();
    }

    // preventing cloning
    @Override
    public Object clone() throws CloneNotSupportedException {
        // return INSTANCE
        throw new CloneNotSupportedException();
    }

    public static void main(String args[]) throws Exception {
        // Breaking the singleton pact

        Singleton s = Singleton.getSingleton();

        Class<Singleton> clazz = Singleton.class;

        Constructor<Singleton> cons = clazz.getDeclaredConstructor();
        cons.setAccessible(true);

        Singleton s2 = (Singleton) cons.newInstance();
        System.out.println(s.hashCode());
        System.out.println(s2.hashCode());
    }

}

// using static class pattern

class BillPughSingleton {

    @SuppressWarnings("unused")
    private static final long serialVersionUID = 1L;

    private BillPughSingleton() {
    }

    private static class LazyHolder {
        private static final BillPughSingleton INSTANCE = new BillPughSingleton();

    }

    public static BillPughSingleton getInstance() {
        return LazyHolder.INSTANCE;
    }

    protected Object readResolve() {
        return getInstance();
    }
}
// Using early instantiation -- static

class SingletonStatic {
    private static SingletonStatic instance = new SingletonStatic();

    private SingletonStatic() {
        System.out.println("Singleton(): Initializing Instance");
    }

    public static SingletonStatic getInstance() {
        return instance;
    }
}

// Using Enum

enum SingletonEnum {

    INSTANCE;

    public void distributePresents() {
        // elided
    }

    /** Demonstrate use of SantaClaus. */
    public static void main(String... aArgs) {
        SingletonEnum fatGuy = SingletonEnum.INSTANCE;
        fatGuy.distributePresents();

    }
}

Count all the possible paths from top left to bottom right of a M*N matrix with the constraints that from each cell you can either move only to right or down.

Following program counts all the possible paths from top left to bottom right of a M*N matrix with the constraints that from each cell you can either move only to right or down.

/**
 * @author vikky.agrawal
 *
 */
public class RightDownPaths {

  int[][] arr;
  int length;

  RightDownPaths() {
    this.length = 4;
    arr = new int[length][length];
  }

  /**
   * @param args
   */
  public static void main(String[] args) {
    new RightDownPaths().operate();

  }

  public void operate() {
    this.calculate(arr);
  }

  public void calculate(int[][] arr) {

    System.out.println("initial array :");
    printArray(arr);

    int length_ = length - 1;

    arr[length_][length_] = 0;

    // Initialize last row and column with 1.
    for (int k = 0; k < length; k++) {
      arr[k][length_] = 1;
      arr[length_][k] = 1;
    }

    //Building array from bottom to top
    for (int row = length_ - 1; row >= 0; row--) {
      for (int column = length_ - 1; column >= 0; column--) {
        arr[row][column] = arr[row][column + 1] + arr[row + 1][column];
        //Total paths =   paths(right)    +   paths(down)
      }
    }
    System.out.println("Array after processing");
    printArray(arr);

    System.out
        .println("Total number of paths going right/down from [0,0] is = "
            + arr[0][0]);

  }

  public void printArray(int[][] arr) {
    int length_ = length;

    for (int row = 0; row < length_; row++) {
      for (int column = 0; column < length_; column++) {
        System.out.print(arr[row][column] + " ");
      }
      System.out.println(" ");
    }
  }

}

Program to find whether sum of two numbers equals to a given no in a sorted array.

A sorted array is given and a number is given, following program finds whether sum of any two numbers in the array is equal to given number.

Rather than traversing whole array from start and end index this program smartly checks whether middle is a viable index if yes then point to that index+1 since array is already sorted, otherwise increments/decrements pointer.

A helper function also given to print all pairs whose sum equal to given number.

/**
 * @author vikky.agrawal 
 */
public class findSum {

    public static void main(String arg[]) {

        findSum obj = new findSum();
        int sum=108;
        System.out.println("whether sum: "+sum+" exists :"
                + obj.find(new int[] { 1, 3, 6, 8, 9, 10, 19, 31, 34, 42, 56,
                        76, 89, 99 }, 108));
        sum=15;
        System.out.println("\nPrinting all pairs for given sum : "+sum);
        obj.printAllPairs(new int[] { 6,7,8,9,10},sum);
    }

    /**
     * O(n) solution to check whether sum of 2 numbers equals to any given number
     */
    
    public boolean find(int arr[], int givenSum) {
        int len = arr.length;

        for (int i = 0, j = len - 1; i <= j;) {
            if (arr[i] + arr[j] == givenSum) {
                System.out.println("Given no : "+givenSum+" found at index : " + i + " value :" + arr[i]+ " and index : " + j + " value : " + arr[j]);
                return true;
            } else if (arr[i] + arr[j] < givenSum) {
                //Rather than blind increment
                //Smartly checks whether middle is a viable index if yes then point to that index+1
                if (arr[(i + j) / 2] + arr[j] < givenSum) {
                    i = ((i + j) / 2) + 1;
                } else {
                    //otherwise increment pointer
                    i++;
                }
            } else if (arr[i] + arr[j] > givenSum) {
                //Decrement; same as above
                if (arr[i] + arr[(i + j) / 2] > givenSum) {
                    j = ((i + j) / 2) - 1;
                } else {
                    j--;
                }
            }
        }
        return false;
    }

    /**
     * Prints all pairs(unique) which equate to given sum
     */
    public void printAllPairs(int[] arr, int givenSum){
        
        int len=arr.length;
        
        for(int i=0, j=len-1; i<=j ; ){
            
            if(arr[i]+arr[j]==givenSum){
                System.out.println("Pair :"+arr[i]+" , "+arr[j]);
                i++;
                j--;
            }else if(arr[i]+arr[j]<givenSum){
                i++;
            }else{
                j--;
            }
        }
    }
    
}

Given an array in range 1..n a value is repeated twice and a value is missing. Find that duplicate in O(n)

An array is given with values in range from 1...n and a number is repeated twice and a number is missing in that range(1..n).
Following program finds the missing value and repeated element in O(n).

/**
 * @author vikky.agrawal
 */


public class FindDuplicate {

    /**
     * @param args
     */
    public static void main(String[] args) {
        FindDuplicate obj = new FindDuplicate();
        int arr[]= new int[]{1,2,3,4,5,6,6,8,9};
        
        obj.findDuplicate(arr, 9);

    }
    
    public void findDuplicate(int[] arr, int n){
        
        if(n<=0){
            return;
        }
        
        int sum=(n*(n+1))/2;
        int squareSum = (n*(n+1)*((2*n)+1))/6;
        
        int sumofArray=0;
        int squareSumofArray=0;
        
        for(int a: arr){
            sumofArray+=a;
            squareSumofArray+=(a*a);
        }
        
        int a_b= sumofArray-sum; //a-b
        int a2_b2= squareSumofArray-squareSum; //a^2-b^2
        
        // (a+b)= (a^2-b^2)/(a-b)
        
        
        int aplusb=a2_b2/a_b;
        int a2=a_b+aplusb;
        int b= aplusb-(a2/2);
        
        System.out.println("Missing element is :"+b);
        System.out.println("Duplicate element is :"+(a2/2));
    }
    
 }

Step by Step Guide to Prepare for Java Interviews

This guide assumes that the reader is clear with Java language basics, hence just giving the basic idea of each listed topic and links to interview questions for each topic is given at the end of synopsis. To prepare for the interview a lot of coding practice is required and basics must be clear, so once done with any topic try to write some code and check output, post comments and discuss if any difficulty.

Contents

• 1 Object oriented design principles
  • 1.1 Encapsulation
  • 1.2 Inheritance
  • 1.3 Polymorphism
• 2 Classes and Object fundamentals
• 3 Exceptions
• 4 String
• 5 Serialization
• 6 Collections
• 7 Generics
• 8 Threads
• 9 Garbage collection
• 10 Misc

Object oriented design principles

While dealing with OOPS one should know about important principles related to OOPS. Encapsulation,Inheritance,Polymorphism are main principles related to OOPS. While looking at open source code we can see a lot of design patterns such as Singleton pattern, Factory pattern etc, but first one should command over the basic principles. Listing these principles here one by one:

Encapsulation

Definition : Encapsulation is the process to bind code and data together. By binding code and data together means we have certain set of rules through which data can be accessed and modified. In case of Java a class contains data(variables) and methods to operate on that data and binding that data means that code can be accessed through well defined method signature. By specifying access modifiers(public, private,default) we restrict access to data within a class, marking a method private will restrict access for other objects outside the class, hence hiding the complexity and providing abstraction.

Inheritance

Definition : Inheritance is the process by which one object acquires properties of another object. Inheritance describes a hierarchical approach in which a subtype inherits the properties defined by its super-type. In Java using interfaces and programming to interfaces makes programs much easier to maintain and provides more abstraction while making use of inheritance. Inheritance also make uses of encapsulation,for example: data members of a super class defined as private are not visible to its subclasses.

Polymorphism

Definition : Polymorphism means one name multiple aspects. In Java polymorphism is implemented mainly in two forms: 1. Overloading -- Same method name but different signature (static polymorphism) 2. Overriding -- Same method name and same signature (subclass overrides method from super class) (dynamic polymorphism) Overloading deals with the same method name but different signature, for example:

public void fun(int a){ //do something }

public void fun(String str){ //do something }

The thing to keep in mind is, at compile time reference variable decides which method will be invoked but at run time actual object decides which method to invoke . This process is known as virtual method invocation or dynamic dispatch. For example:

class Employee{
 public void print(){
  System.out.println("Inside employee");
 }
}

class Developer extends Employee{
 public void print(){
  System.out.println("Inside Developer");
 }
}

class Main{
public static void main(String[] arg){
  Employee emp = new Employee();
  Employee dev = new Developer();
  emp.print();  //prints :Inside employee
  dev.print();  //prints :Inside Developer
}
}

So at compile time both the calls to print checks the reference variable, since reference variable is same in both cases, compiler will know that method in Employee class is being called, but at the run time actual object determines which method to invoke, hence method in Developer gets invoked in second case.

Classes and Object fundamentals

Points to note:
1. A constructor always invoked when a new object is created, and the call goes all the way up to Object class through inheritance hierarchy.
2. Instance members are accessible only after call to super completed.
3. Static members (methods and variables) belong to a class.
4. Static block(s) gets executed only once when the class is loaded. Static blocks gets executed in the order they are declared.
5. Static can't refer 'this' and 'super'.
6. To instantiate an object all instance variables in class and it's superclass must be initialized first.
7. While creating a new object, order of invocation will be: complete super class instance variable invocation -> complete super class constructor invocation -> complete own instance variable invocation ->complete own constructor invocation.

Exceptions

Exception: An exception is an event which disrupts the normal flow of the program. Exceptions are objects in Java

Figure : Exception Hierarchy

 Java supports exception mechanism in which two types of Exceptions exists

1. Checked exceptions: Exception and its subclasses other than RuntimeException and its subclasses comes into checked exception category. Handle or declare strategy states that either handle the exception using try-catch-finally block or declare using throws keyword. Checked exceptions are exceptions which strictly follows handle or declare strategy. By marking an exception checked one must need to surround it using try-catch-finally or use throws keyword. Eg: IOException

2. Un-checked exceptions: Subtypes of Error and RuntimeException comes into unchecked exception category. Any unchecked exception need not to be handled or declared. As a programmer one can handle/declare it but compiler won't complain in case its NOT handled or declared. Eg: ArrayIndexOutOfBoundException

 Finally block: finally block ALWAYS executes, except in following cases.
* If the JVM exits while the try or catch code is being executed, then the finally block may not execute.
 * Likewise, if the thread executing the try or catch code is interrupted or killed, the finally block may not execute even though the application as a whole continues.
 * Finally block overrides any exception or return statement in try/catch block, it means if there is any return statement or exception in catch block finally will still execute.

String

String objects are immutable.That means once a String object is created it can't be changed. Any operation on String object returns a new object. String literals are kept in String constant pool, whenever a new String literal created compiler checks in the pool whether it already exists, if it does, then reference points to existing literal. For example:

String str="Hello"; // a string object created and placed in string pool
String st=new String("Hello"); //here 2 objects created, 
/**
a new string object created and placed in non pool memory
and a literal "Hello" will be placed in string pool.
Invoking any method on string object will create new object.
**/
eg: str= str.toUpperCase();  
/**
reference str will refer to new object,
and reference to old object lost now
*/

Use of StringBuffer or StringBuilder: StringBuffer class is mutable hence whenever a lot of modifications required on String object use StringBuffer. StringBuilder class is same as StringBuffer with only difference that methods in StringBuilder are not synchronized hence its not thread safe but runs faster than StringBuffer.

Equals vs '==' for String objects

String s1="abc";
String s2="abc";   // same string literal will be referenced
String s3= new String("abc"); 
System.out.println(s1==s2);   // true same literals in string pool
System.out.println(s1==s3);   // false 
//since object creation using new operator doesn't point to literal in string pool
System.out.println(s1.equals(s3));  //true,equals method checks contents of objects 

Serialization

Serialization is a process by which Object is written to stream and actual object could be re-constructed from that stream. Primary use of serialization is to construct stream of object,transfer through network and reconstruct over there.Serialization is also useful in Remote method invocation. Serializable is a marker interface, without any methods. By implementing Serializable an indication to compiler/JVM sent to handle Java serialization. SerialVersionUID used to indicate the version of the class and to ensure that the same class is loaded while de-serializing the object.In case any mismatch in SerialVersionUID an InvalidClassException is thrown. SerialVersionUID is written to the stream while serializing the object, in case there are any changes in class and a new version need to be released change SerialVersionUID to indicate the new version. SerialVersionUID is static final field, though static fields are not related to Object hence not serialized , but in case of SerialVersionUID, it is an exception to above condition.

Collections

Equals and HashCode contract: case 1: If x.equals(y) = true then x.hashCode=y.hashCode (Must); similarly if x.hashCode != y.hashCode then x.equals(y) = false (Must) Its NOT the same, other way round, i.e. case 2: if x.hashCode = y.hashCode then there is no constraint on x.equals(y); similarly if x.equals(y) = false then no constraint on hashCode. This concept is very handy, while hashing of an object(HashMap, HashSet etc). The contract states that if two objects pass equality test then they must land to same bucket hence hashCode must be same. In case hashCode is not same it will indicate that the objects must land in different buckets, hence objects must fail equality test. If we talk about case 2: there might be two objects which has same hash code hence land to same bucket(collision) but it may or may not pass equality, since there may exist multiple entry at the same bucket. following is a diagram for important interfaces and classes of Collection framework.

1. List : Sequence of elements  
2. Set : Collection of unique elements  
3. Queue: Things arranged in order in which they are to be processed. (typically first in first out)  
4. Map : Stores association between key(uniqueID) and value.  

1. List : provides index based access. Implementing classes   1.1 ArrayList : Dynamic arrays which provides fast iteration and fast random access(due to index based implementation), slow insertion/deletion.   1.2 Vector : Same as ArrayList with synchronized methods.   1.3 LinkedList: Doubly linked list implementation, makes fast insertion or deletion but slow iteration.  

2. Set : Contains only unique elements   2.1 HashSet : Uses HashMap internally, unordered & unsorted collection of unique elements.   2.2 LinekdHashSet: Ordered version of HashSet   2.3 TreeSet : Sorted version of HashSet

 3. Queue : Things arranged in order in which they are to be processed. (typically first in first out) 3.1 PriorityQueue : Creates a queue that is based on the queue's Comparator or natural ordering.

 4. Map : Stores association of unique key to values
4.1 HashMap : Stores key value pairs based on hashCode of key, in case of collision a link to previous entry stored and while accessing values hashCode is used to determine actual bucket and then equals method to identify actual value.
4.2 Hashtable : Same as HashMap with synchronized methods.
4.3 LinkedHashMap: Maintains insertion order.
4.4 TreeMap : Sorted Map. Iterators: General purpose standardized way of accessing elements from collections(though not implemented by Maps)


Comparable interface: Objects of the classes implementing Comparable can be ordered (i.e. TreeSet, sorted collection of unique items) the objects that need to be sorted must implement Comparable interface(sorting requires comparison). To implement Comparable a class must implement compareTo(Object anotherobj) method which returns an integer as follows: negative if thisobj < anotherobj positive if thisobj > anotherobj zero if thisobj == anotherobj

Comparator interface: Comparable interface requires the class to modify whose instances we need to sort by implementing conpareTo method inside the class. If a class can't be modified then a separate class can be created which implements Comparator and defines its method compare(Object objone, Object objtwo) which acts same as compareTo method of Comparable.

Generics

Points to note:
1. Generic type safety is for compile time, compiler checks for parametric type safety. After compilation all parameters related to Generic type removed.
2. Generic type is only for Objects, not for primitives.To use primitives, Java uses autoboxing.
 3. Mixture of generic and non generic code compiles fine, but a cast is required while accessing objects. Casting may fail at runtime, if its a wrong cast with classCastException.
4. Polymorphic assignments does not work to Generic type, for example:
  List < Animal > animal = new ArrayList < Dog >
 //polymorphic assignment not allowed. (assuming Dog is a subclass of Animal)

Threads

A process may contain multiple threads. Threads share same address space while each thread having its own stack,program counter, registers. To understand more basics about threads check these lecture notes: Threads Lecture Notes

Figure: Thread States

To create a thread in Java either implement Runnable or extend Thread class, implementing Runnable is preferable until unless there is a requirement to override any method from Thread class. To start a thread call the method start(), calling method run() directly, will not start a new thread.

Java provides locking mechanism for synchronization between threads, each Object in Java has its own lock and each class has a lock(Class lock) associated with it.
Object level lock and class level locks are different, the class has only a single lock. Access to class's static fields is controlled by a lock that's distinct from the lock for any instance of the class. Synchronization is achieved by acquiring a lock on object(or class). Once a thread acquires a lock on an object no other thread can acquire lock on that object,hence only one thread can execute inside the synchronized block. wait,notify,notifyAll methods defined in Object class, used to signal between threads and must be called from inside synchronized block.
While waiting for a signal,thread releases its lock. Sleeping thread(sleep method call) doesn't releases its lock. A thread executing notify on an object gives chances to a waiting thread to continue, once the notifying thread releases its lock the waiting thread may acquire the lock and continue. sleep and yield methods are defined as static methods in Thread class since these methods are applied on a thread rather than on object. wait, notify, notifyAll are applied on a object hence non-static.

volatile keyword is an indicator to compiler to use a variable's value from main memory rather from cached copy of any thread.

Garbage Collection

In Java, memory allocation and de-allocation is handled by JVM, an object without any reference is said to be eligible for garbage collection. JVM uses mark and sweep algorithm to determine which objects have live references. This algorithm traverses all object references (object graph) and marks all the objects which have live references. Apart from live objects, all other objects are eligible for garbage collection, so heap memory containing these objects reclaimed. Marking process is very time consuming in case all the objects need to be scanned, so JVM uses generational garbage collection.

Figure : GC Generartions

The heap is divided in following sections:
1. Young generation
   1.1 Eden space - Part of the heap memory from which memory is initially allocated for most objects. 
   1.2 Survivor space - Part of the heap memory containing objects that have survived the garbage collection of the Eden space.

2. Old generation(Tenured space) - Part of the heap memory containing objects that have existed for some time in the survivor space.  

3. Permanent generation - The pool(non-heap) containing all the reflective data of the virtual machine itself, such as class and method objects. With Java VMs that use class data sharing, this generation is divided into read-only and read-write areas. When young generation fills, a minor garbage collection performed, surviving objects first moved to survivor space and eventually moved to old generation. When old generation fills, a major garbage collection is performed. The permanent generation is included in full garbage collection.

Finalize() method is called before performing garbage collection on an object and it is invoked only once for an object's life-cycle. In case of any exception in finalize method it is ignored and garbage collection of that object terminates. Garbage collector is a daemon thread, garbage collection can't be forced but a request can be placed for garbage collection in following ways:
1. Invoking gc() method of Runtime class.
2. Invoking System.gc()

Find maximum sum subarray

Question: Given an array of integers(positive/negative) find a sub-array such that it gives max sum.  

Solution(s):
Method 1: Using divide and conquer: Divide the given array in 2 sub-arrays from middle and find maximum sum in those sub-arrays.
case 1 : maximum sum is in left subarry
case 2 : maximum sum is in right subarry
case 3 : maximum sum may exist at the crossing point including both the sub-arrays Find the maximum from all these 3 cases that will give the maximum sum sub-array.

Method 2: Using Kadane's algorithm In this algorithm we scan the array and keep track of elements and based on the condition that either adding the current value will increment variable or not, we update the variables. Following program implements divide and conquer approach and Kadane's algorithm.

/**
 * @author Vikky.Agrawal
 * 
 */
public class MaxSumSubArray {

 int arr[];

 MaxSumSubArray() {
      arr = new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
     //arr = new int[] { -2, -1, -3, -4, -1, -2, -1, -5, -4 };
 }

 public static void main(String[] args) {
  new MaxSumSubArray().operate();

 }

 public void operate() {
  System.out.println("Max sum is " + findMaxSum(arr, 0, arr.length - 1));
  System.out.println("Max sum using kadane's algo :"
    + findMaxSubArraySum(arr));
  System.out.println("Alternate kadane's :"+findMaxSumKadane(arr));
  
 }

 //Method 1: divide and conquer  
 public int findMaxSum(int arr[], int low, int high) {

  if (low == high) {
   return arr[low];
  }

  int mid = (low + high) / 2;
  return maxOfThree(findMaxSum(arr, low, mid),
    findMaxSum(arr, mid + 1, high),
    maxCrossSum(arr, low, mid, high));

 } 


//case 3: check whether max sum exist including crossing point.
 public int maxCrossSum(int arr[], int low, int mid, int high) {

  int leftSum = Integer.MIN_VALUE;
  int rightSum = Integer.MIN_VALUE;
  int sum = 0;

  for (int i = mid; i >= low; i--) {
   sum = sum + arr[i];
   if (sum > leftSum) {
    leftSum = sum;
   }
  }

  sum = 0;

  for (int j = mid + 1; j <= high; j++) {
   sum += arr[j];
   if (sum > rightSum) {
    rightSum = sum;
   }
  }

  return leftSum + rightSum;
 }

 /** 
 * Method 2: Using Kadane's algorithm
 * will return negative if all elements are negative
 * Time complexity : O(n)
 **/


 public int findMaxSubArraySum(int arr[]) {

  int max_ending_here = arr[0];
  int max_so_far = arr[0];

  int begin = 0;
  int end = 0;
  int temp = 0;

  for (int i = 1; i < arr.length; i++) {

   if (max_ending_here < arr[i]) {
    max_ending_here = arr[i];
    temp = i;
   } else {
    max_ending_here += arr[i];
   }

   if (max_ending_here >= max_so_far) {
    max_so_far = max_ending_here;
    begin = temp;
    end = i;
   }

  }

  System.out.println("Largest subarry start index :" + begin
    + " end index : " + end);
  return max_so_far;
 }

 //Another approach using Kadane's algorithm
 public int findMaxSumKadane(int arr[]){
  
  int length=arr.length;
  
  if(length==0){
   return Integer.MIN_VALUE;
  }
  
  //This will help with negative numbers.
  int  max_ending_here =arr[0], max_so_far = arr[0];
  
  for(int j=1; j<length; j++){
   max_ending_here=maxOfTwo(max_ending_here+arr[j],arr[j]);
   max_so_far= maxOfTwo(max_so_far, max_ending_here);
  }
  
  return max_so_far;
 }
 
 
 
 // Helper functions
 public int maxOfTwo(int a, int b) {
  return a > b ? a : b;
 }

 public int maxOfThree(int a, int b, int c) {
  return maxOfTwo(maxOfTwo(a, b), c);
 }
}

Complexity Analysis: 
For method 1(divide and conquer): it resembles to Master theorem case 2 hence time taken will be T(n)=2T(n/2)+O(n) = O(n logn)
For method 2: Kadane's algorithm makes only a single pass of the whole array hence time complexity will be O(n) which is linear and significant improvement than divide and conquer approach.

Reverse a stack

Given a stack, following program recursively reverses it:

/**
 * @author vikky.agrawal
 * Stack reversal
 */

public class StackImpl {

 Node top =null; 
 
 public static void main(String[] arg){ 
  
  StackImpl stack=new StackImpl();
  stack.stackOperations();
 }
 
 
 public void stackOperations(){
  

  for (int i = 1; i < 10; i++) {
   push((int) (Math.random() * 100));
  }
  
  printStack();
  
  top=this.reverseStack(top);
  System.out.println("Stack after reverse");
  printStack();
  
  
 }
 
 
 
 public Node reverseStack(Node tos){
  
  
  ///base case
  if(tos==null || tos.getLink()==null){
   return tos;
  }  
  
  //point temp to last node and then set link recursively.
  Node temp=reverseStack(tos.getLink());
  
  tos.getLink().setLink(tos);  //a->b->c->null,set b's backward link a<-b<-c;  
                                             // and set b's forward link as null
  tos.setLink(null);
  
  return temp; //always last node, hence top of reversed Stack
 }

 
 /**
  * Helper functions for stack operations
  */
 
 public void push(int data){
  if(top==null){
   top=new Node(data);
  }else{
   Node temp=new Node(data);
   temp.setLink(top);
   top=temp;
  }
 }
 
 public int pop(){
  if(top==null){
   return -1;
  }else{
   Node temp=top;
   top=top.getLink();
   return temp.getData();
  }
 }
 
 public int peek(){
  if(top!=null){
   return top.getData();
  }else{
   return -1;
  }
 }
 
 
 public boolean isEmpty(){
  if(top==null)
   return true;
  return false;
 }
 
 
 public int size(){
  int size=0;
  Node temp=top;
  
  while(temp!=null){
   size++;
   temp=temp.getLink();
  }
  return size;
 }
 
 public void printStack(){
  Node temp=top;
  System.out.print("Top->\n");
  while(temp!=null){
   System.out.println(temp.getData()+"\n|");
   temp=temp.getLink();
  }
  System.out.println("/null");
 }
 
 /**
  * static inner class to be used for Stack Data Structure
  */
  static class Node{
   private int data;
   private Node link;    
      
      Node(){
            
      }
      
      Node(int data){
       //mergedList=new Node();
          this.setData(data);
          this.setLink(null);       
      }
      
      public int getData(){
          return this.data;
      }
        
      public Node getLink(){
          return this.link;
      }
      
      public void setData(int data){
          this.data=data;
      }       
      
      public void setLink(Node link){
          this.link=link;
      }  
 }
 
}