Tuesday, March 15, 2016

Array of HashMaps in Java

HashMap in Java is one of the common data structures used to store key-value pairs. HashMap can also be used as items of an ordinary array.
package util;

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

public class ArrayUtility {


    @SuppressWarnings("unchecked")
    public static HashMap<String,Object>[] createAndFillHashMapArray( final int size )
    {
        HashMap<String, Object>[] hashMapArray = (HashMap<String, Object>[])new HashMap[size];
        int i = 0;
        for (HashMap<String, Object> hashMap : hashMapArray) {
             hashMap = new HashMap<String, Object>();
             hashMap.put("key"+i, "value"); 
             hashMapArray[i] = hashMap;
             i++;
        }
        return hashMapArray;
    }
 
    public static void displayHashMapArrayContent( HashMap<String, Object>[] hashMapArray )
    {
        if( hashMapArray != null && hashMapArray.length > 0 )
        {
           for (HashMap<String, Object> hashMap : hashMapArray) {
              for (Map.Entry<String, Object> entry : hashMap.entrySet()) {
                  String key = entry.getKey();
                  Object value = entry.getValue();
                  System.out.println(key+" - "+value);
               }
           }
         }
    }
 
    public static void main(String[] args) {
  
         HashMap<String, Object>[] hashMapArray = createAndFillHashMapArray(5);
         displayHashMapArrayContent(hashMapArray);
    }
}


createAndFillHashMapArray method takes the size of the array and fills it with HashMaps.
displayHashMapArrayContent method takes the hashMap array and displays its content as follows :

key0 - value
key1 - value
key2 - value
key3 - value
key4 - value

Thursday, November 12, 2015

Maximum Contiguous Subsequence Sum in Linearithmic Time Recursively in Java

There are different solutions to maximum subsequence sum problem with varying complexities such as linear, quadratic and cubic.

There is also a linearithmic solution for the maximum subsequence sum problem implemented in Java.

This linearithmic solution is achieved by applying a divide-and-conquer algorithm design strategy.

Algorithm divides the input array into two different parts from the middle and then searches the max sum
1-) in the first half
2-) in the second half
3-) in the sub array that crosses the mid point of the array

1st and 2nd cases are achieved with recursive calls.

3rd case is achieved by as described at :

"by finding the largest sum in the first half that includes the last element in the first half, and the largest sum in the second half that includes the first element in the second half."



package basics;

public class MaxSubSumLinearithmic {

 public static int maxSubSum(int[] inArr) {
  return maxSubSum( inArr, 0, inArr.length-1 );
 }

 public static int maxSubSum(int[] inArr, int left, int right) {

  if (left == right)
   if (inArr[left] > 0)
    return inArr[left];
   else
    return 0;

  int mid = (left + right) / 2;
  int maxLSum = maxSubSum( inArr, left, mid);
  int maxRSum = maxSubSum( inArr, mid+1, right);

  int maxLBorderSum = 0, leftBorderSum = 0;
  for (int i = mid; i >= left; i--) {
   leftBorderSum += inArr[i];
   if ( leftBorderSum > maxLBorderSum )
    maxLBorderSum = leftBorderSum;
  }

  int maxRBorderSum = 0, rightBorderSum = 0;
  for (int i = mid + 1; i <= right; i++) {
   rightBorderSum += inArr[i];
   if ( rightBorderSum > maxRBorderSum )
    maxRBorderSum = rightBorderSum;
  }

  return getMax3( maxLSum, maxRSum, maxLBorderSum+maxRBorderSum );
 }
 
 private static int getMax3( int a, int b, int c )
 {
      return a > b ? a > c ? a : c : b > c ? b : c;
 }

 public static void main(String[] args) {

  int input[] = { -2, -3, 4, -1, -2, 1, 5, -3 };

  System.out.println("Max Sub Array Sum Result = " + maxSubSum(input));

  input = new int[] { -2, 3, -16, 100, -4, 5 };

  System.out.println("Max Sub Array Sum Result = " + maxSubSum(input));

  input = new int[] { -2, 11, -4, 13, -5, 2 };

  System.out.println("Max Sub Array Sum Result = " + maxSubSum(input));

  input = new int[] { -15, -23, -476, -3, -292 };

  System.out.println("Max Sub Array Sum Result = " + maxSubSum(input));
 }
}



Create a MaxSubSumLinearithmic.java file in your workspace.

When the main method inside the MaxSubSumLinearithmic class executed it is going to print :

Max Sub Array Sum Result = 7
Max Sub Array Sum Result = 101
Max Sub Array Sum Result = 20
Max Sub Array Sum Result = 0


References :



Divide and Conquer Solution to Max Sub Sum

Finding-maximum-contiguous-subsequence-sum-using-divide-and-conquer-approach

Max Sub Array Problem Definition from Wikipedia

Finding Maximum of Three Integers in Java

Finding maximum of three integers problem helps to understand if-else branching and conditionals topic in a better way.

Following is the implementation of the find maximum of three integers in Java.



package basics;

public class ThreeComparator {

 public static int max3( int a, int b, int c )
 {
  if( a>b )
  {
   if( a > c )
       return a;
   else
       return c;
  }
  else if( b>c )
  {
                 return b;
  }
  else
  {
   return c;
  }
  
 }
 
 public static void main(String[] args) {
  
  int a = 4;
  int b = 3;
  int c = 5;
  
  System.out.println("Maximum of "+a+" , "+b+" and "+c+" is = "+max3( a,b,c ));
  System.out.println("Maximum of "+a+" , "+c+" and "+b+" is = "+max3( a,c,b ));
  System.out.println("Maximum of "+b+" , "+a+" and "+c+" is = "+max3( b,a,c ));
  System.out.println("Maximum of "+b+" , "+c+" and "+a+" is = "+max3( b,c,a ));
  System.out.println("Maximum of "+c+" , "+a+" and "+b+" is = "+max3( c,a,b ));
  System.out.println("Maximum of "+c+" , "+b+" and "+a+" is = "+max3( c,b,a ));
  
  System.out.println("Maximum of 4 , 5 and 4 is = "+max3( 4,5,4 ));
  System.out.println("Maximum of 41 , 41 and 41 is = "+max3( 41,41,41 ));
  System.out.println("Maximum of 11 , 21 and 31 is = "+max3( 11,21,31 ));  
 }
}



Create a ThreeComparator.java file in your workspace.

When the main method inside the ThreeComparator class executed it is going to print :

Maximum of 4 , 3 and 5 is = 5
Maximum of 4 , 5 and 3 is = 5
Maximum of 3 , 4 and 5 is = 5
Maximum of 3 , 5 and 4 is = 5
Maximum of 5 , 4 and 3 is = 5
Maximum of 5 , 3 and 4 is = 5
Maximum of 4 , 5 and 4 is = 5
Maximum of 41 , 41 and 41 is = 41
Maximum of 11 , 21 and 31 is = 31