How to convert DateTime to different Timezone's

How to convert DateTime to different Timezone's

TimeZone  

Convert the given date, time to a different timezone along with 12-hour clock format. Lets see simple java example to convert the given string to Date and with local/Default(IST) time to 2 different timezone along with 12-hour clock format (AM/PM).

import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Calendar;
import java.util.Date;
import java.util.TimeZone;

public class DateTime {

 public static void main(String[] args) {
  
  String sDate1="25-03-2018 13:34:56";  
  SimpleDateFormat sdf = new SimpleDateFormat("dd-MM-yyyy hh:mm:ss");
  
  // Converting string to Date() with specified date format.
  Date date = null;
  try {
   date = sdf.parse(sDate1);
  } catch (ParseException e) { 
   e.printStackTrace();
   // If any format error pick current datetime
   date = new Date();
  } 
  sdf = new SimpleDateFormat("dd-MMM-yyyy hh:mm:ss a");
  Calendar calendar = Calendar.getInstance();
  calendar.setTime(date);
  
  System.out.println("Default IST Time      : "+sdf.format(calendar.getTime()));    
  
  
  // Changing TimeZone to America/New_York
  sdf.setTimeZone(TimeZone.getTimeZone("America/New_York"));
  System.out.println("America/New_York Time : "+sdf.format(calendar.getTime()));    

  
  // Changing TimeZone to Australia/Sydney
  sdf.setTimeZone(TimeZone.getTimeZone("Australia/Sydney"));
  System.out.println("Australia/Sydney Time : "+sdf.format(calendar.getTime()));
  
 }
}

OUTPUT:

Default IST Time      : 25-Mar-2018 01:34:56 PM
America/New_York Time : 25-Mar-2018 04:04:56 AM
Australia/Sydney Time : 25-Mar-2018 07:04:56 PM

Know How to find all leaf nodes in binary tree

Know How to find all leaf nodes in binary tree

Print all leaf nodes of a Binary Tree from left to right  

Create a Binary Tree with from the given array of values and then find all the leaf nodes from left to right. Leaf nodes are nothing but bottom/last nodes with both left and right subtree's are null.
For the below given Binary tree the list of leaf nodes will be 1, 6, 9

Lets see simple java code to create a binary with the given array of integers and to find the leaf nodes.

public class BinaryTreeLeafNode {

 public static void main(String[] args) {

  int val[] = new int[] { 4, 5, 8, 100, 3, 2, 9, 1, 7, 6 };
  
  BinaryTree obj = new BinaryTree();

  BST root = obj.createBinaryTree(val);

  obj.getAllLeafNodes(root);
 }

 public BST createBinaryTree(int[] val) {
  BST root = new BST(val[0]); // Initialize root with 1ft element
  BST tmpRoot = root; // Temporary root node

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

   BST lastNode = getLastNode(tmpRoot, val[i]);
   if (val[i] > lastNode.data) {
    BST tmp = new BST(val[i]);
    lastNode.right = tmp;
   } else {
    BST tmp = new BST(val[i]);
    lastNode.left = tmp;
   }
  }
  return root;
 }

 public void getAllLeafNodes(BST root) {
  if (root.left != null) {
   getAllLeafNodes(root.left);
  }
  if (root.right != null) {
   getAllLeafNodes(root.right);
  }
  /*
   * If both left and right are null then its leaf node
   */
  if(root.left == null && root.right == null) {
   System.out.print(root.data + ", ");
  }
 }

 public BST getLastNode(BST root, int val) {

  if (val > root.data) {
   if (root.right == null) {
    return root;
   } else
    return getLastNode(root.right, val);
  } else {
   if (root.left == null) {
    return root;
   } else
    return getLastNode(root.left, val);
  }
 }
}

OUTPUT:

1, 6, 9, 

Interesting, How to find next greater number with same digits

Interesting, How to find next greater number with same digits

next greater number  

Given a number N, find the smallest number that has same set of digits as N and is greater than N. If theres no number greater than N by same same set of digits then print -1.
For example if N = 354 then all possible cobinations of the N digits will be 345, 435, 453, 534, 543. So the output will be 435 is the next smallest of all combinations and greater than N.

Few examples:

N = 354
Output: 435

N = 218765
Output: 251678

N = 1234
Output: 1243

N = 4321
Output: -1

N = 534976
Output: 536479

Below code a simple permutation and combination of all digits from given N and get the next number from given number. If don't find any number then return -1.

For permutation and combination we use recursive algorithm and stores the combination in the TreeSet. 

import java.util.TreeSet;

public class HighestNumber {

 private TreeSet<Integer> combination = new TreeSet<Integer>();

 public static void main(String[] args) {

  Integer n = 354;
  HighestNumber obj = new HighestNumber();
  int nxtNumber = obj.findNextHighest(n);
  System.out.println(nxtNumber);
 }

 private int findNextHighest(int n) {
  permutation("", Integer.toString(n));
  return getNextHighestNumber(n);
 }

 /*
  * Recursive method to get all combination of digits
  */
 private void permutation(String prefix, String str) {
  int len = str.length();
  if (len == 0) {
   combination.add(Integer.valueOf(prefix));
  } else {
   for (int i = 0; i < len; i++) {

    String p = prefix + str.charAt(i);
    String s = str.substring(0, i) + str.substring(i + 1, len);
    permutation(p, s);
   }
  }
 }

 /*
  * Get the next number from combination collection TreeSet
  */
 private int getNextHighestNumber(int n) {
  boolean flag = false;
  int nxtNumber = -1;
  for (Integer num : combination) {
   if (num == n)
    flag = true;
   else if (flag) {
    nxtNumber = num;
    break;
   }
  }
  return nxtNumber;
 }
}

OUTPUT:

435

Sorting HashMap by Values including duplicate in Java

Sorting HashMap by Values including duplicate in Java

Sorting HashMap by Values including duplicate in Java  

We have seen sorting HashMap based on custom objects by implementing Comparator and Comparable interfaces. Now lets see how to sort HashMap using values which has duplicate. Can be sorted with multiple ways like using Comparator interface, using Stream from Java 8 etc.,

Sorting HashMap based on custom objects

Now lets see simple example to sort HashMap based on value which has dupilcate using Comparator interface.

import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class SortingHashMap {

 public static void main(String[] args) {

  Map<String, Integer> map = new HashMap<String, Integer>();
  map.put("java", 100);
  map.put(".net", 80);
  map.put("python", 99);
  map.put("C++", 65);
  map.put("C", 70);
  map.put("Orale", 65);
  
  System.out.println("Before Sorting : "+map);
  
  map = new SortingHashMap().sortMapByValue(map);
  
  System.out.println("After Sorting  : "+map);
 }

 private Map<String, Integer> sortMapByValue(Map<String, Integer> map) {

  List<Entry<String, Integer>> list = new LinkedList<Entry<String, Integer>>(map.entrySet());
  /*
   * Sorting map values by using Comparator
   */
  Collections.sort(list, new Comparator<Entry<String, Integer>>() {
   public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
    return o1.getValue().compareTo(o2.getValue());
   }
  });

  // LinkedMap to maintain the sorted value order 
  Map<String, Integer> sortedMap = new LinkedHashMap<String, Integer>();
  for (Entry<String, Integer> entry : list) {
   sortedMap.put(entry.getKey(), entry.getValue());
  }

  return sortedMap;
 }
}

OUTPUT:

Before Sorting : {python=99, C++=65, java=100, C=70, .net=80, Orale=65}
After Sorting  : {C++=65, Orale=65, C=70, .net=80, python=99, java=100}

Next we will see how to sort HashMap based on value using stream from Java 8

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.stream.Collectors;

public class SortingHashMap {

 public static void main(String[] args) {

  Map<String, Integer> map = new HashMap<String, Integer>();
  map.put("java", 100);
  map.put(".net", 80);
  map.put("python", 99);
  map.put("C++", 65);
  map.put("C", 70);
  map.put("Orale", 65);
  
  System.out.println("Before Sorting : "+map);
  
  map = new SortingHashMap().sortMapByValue(map);
  
  System.out.println("After Sorting  : "+map);
 }

 private Map<String, Integer> sortMapByValue(Map<String, Integer> map) {

  Map<String, Integer> sortedMap = 
        map.entrySet().stream()
       .sorted(Entry.comparingByValue())
       .collect(Collectors.toMap(Entry::getKey, Entry::getValue,
                           (o1, o2) -> o1, LinkedHashMap::new));
  
  return sortedMap;
 }
}

OUTPUT:

Before Sorting : {python=99, C++=65, java=100, C=70, .net=80, Orale=65}
After Sorting  : {C++=65, Orale=65, C=70, .net=80, python=99, java=100}

Longest Common Subsequence (LCS) algorithm using Dynamic Programming in java

Longest Common Subsequence (LCS) algorithm using Dynamic Programming in java

Longest Common Subsequence (LCS) algorithm using Dynamic Programming in java  

The Longest Common Subsequence (LCS) problem is given with two strings like "ABAZDC" and "BACBAD". LCS is to find their longest common subsequence that appear left-to-right but not necessarily in a contiguous block in both the strings. Here we will see how to achieve Longest Common Subsequence (LCS) algorithm using Dynamic Programming using Java.

Example:
Str1 = "ABAZDC"
Str2 = "BACBAD"

Here the Longest Common Subsequence (LCS) size will be 4 and the Longest Common Subsequence (LCS) will "ABAD".

How to find Longest Common Subsequence (LCS)?

First we need to construct matrix of size str1 and str2 like matrix[str1.length][str2.matrix] as shown below

Whenever any character matches with both the array then we need to increment the value by 1 and carry on with same comparison for all rows and columns.
Same comparison will be done using recursion and by storing the value to achieve dynamic programming.  

public class LCS {

 public static void main(String[] args) {

  String str1 = "ABAZDC";
  String str2 = "BACBAD";

  LCS obj = new LCS();
  String out = obj.getLCS(str1, str2);

  System.out.println("LCS Length : " + out.length());
  System.out.println("LCS String : " + out);
 }

 public String getLCS(String str1, String str2) {

  /* Array will be updated with the character change order */
  int arr[][] = new int[str1.length()][str2.length()];
  
  /* Calling actual LCS recursive method */
  getLCS(str1, str1.length() - 1, str2, str2.length() - 1, arr);

  return constructLCSString(arr, str1, str2);
 }
 
 /*
  * Constructing the LCS string the generated array arr[]
  */
 public String constructLCSString(int[][] arr, String str1, String str2) {
  
  String lcsString = "";
  
  /* Iterating through arr[] to get the actual LCS string 
   * iterating from bottom to up.
   */
  for (int i = arr.length - 1, j = arr[0].length - 1; (i >= 0 && j >= 0);) {

   if (i == 0) {
    lcsString = str1.charAt(i) + lcsString;
    break;
   } else if (j == 0) {
    lcsString = str2.charAt(j) + lcsString;
    break;
   }

   if (arr[i][j] != arr[i - 1][j] && arr[i][j] != arr[i][j - 1]) {
    lcsString = str1.charAt(i) + lcsString;
    i--;j--;
   } else if (arr[i][j] == arr[i - 1][j]) {
    i--;
   } else if (arr[i][j] == arr[i][j - 1]) {
    j--;
   }
  }
  return lcsString;
 }
 
 
 public int getLCS(String str1, int n, String str2, int m, int arr[][]) {
  if (n == -1 || m == -1)
   return 0;
  
  /*
   * Checking in array for same n, m index and if present returning 
   * the value from array and its Dynamic programming
   */
  if (arr[n][m] != 0)
   return arr[n][m];

  int output = 0;
  if (str1.charAt(n) == str2.charAt(m)) {
   output = 1 + getLCS(str1, n - 1, str2, m - 1, arr);
  } else {
   int tmp1 = getLCS(str1, n - 1, str2, m, arr);
   int tmp2 = getLCS(str1, n, str2, m - 1, arr);
   output = tmp1 > tmp2 ? tmp1 : tmp2;
  }
  /* Memorize the output on array to use for similar recursive call */
  arr[n][m] = output;
  return output;
 }
}

OUTPUT:

LCS Length : 4
LCS String : ABAD

Printing ODD/EVEN using 2 threads in java - (By ReentrantLock and Condition)

Printing ODD/EVEN using 2 threads in java - (By ReentrantLock and Condition)

ReentrantLock and Condition  

Already in our earlier post we have have seen how to print ODD EVEN numbers using 2 thread using wait() and notify() and using semaphore in java. Below are the links if have not seen it.

Printing ODD/EVEN using wait() and Notify() in java

Printing ODD/EVEN using Semaphore in java

Now lets see how to achieve same logic by 2 threads using ReentrantLock along with Condition. First lets see what is ReentrantLock and Condition?

ReentrantLock Lock?

The ReentrantLock class implements the Lock interface and provides synchronization to the methods while accessing shared resources. The code which manipulates the shared resource is surrounded by calls to lock and unlock method. This gives a lock to the current working thread and blocks all other threads which are trying to take a lock on the shared resource.

Condition?

Conditions (also known as condition queues or condition variables) provide a means for one thread to suspend execution (to "wait") until notified by another thread that some state condition may now be true. Because access to this shared state information occurs in different threads, it must be protected, so a lock of some form is associated with the condition. The key property that waiting for a condition provides is that it atomically releases the associated lock and suspends the current thread, just like Object.wait.

A Condition instance is intrinsically bound to a lock. To obtain a Condition instance for a particular Lock instance use its newCondition() method. Hence here we are going to use 2 conditions like 1 for ODD and another for EVEN

 //Reentrant Lock
 private final Lock aLock = new ReentrantLock(); 
 
 // Condition for ODD block
 private final Condition oddCondition = aLock.newCondition(); 
 
 // Condition for EVEN block
 private final Condition evenCondition = aLock.newCondition();

Simple example to print ODD and EVEN numbers using 2 threads upto 10 using above ReentrantLock and Condition. 

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/*
 * Printing odd numbers using Odd thread and Even
 * numbers using Even thread but in sequential order
 */
public class OddEvenUsingLockAndCondition {

 public static void main(String[] args) {
  
  OddEvenImpl obj = new OddEvenImpl();
  
  Odd odd = new Odd(obj);
  Even even = new Even(obj);
  odd.start();

  /* *
   * Just starting 2nd thread after
   * a half second
   */
  try {
   Thread.sleep(500);
  } catch (InterruptedException e) {
   e.printStackTrace();
  }
  even.start();
 }
 
}

class OddEvenImpl {
 
 //Reentrant Lock
 private final Lock aLock = new ReentrantLock(); 
 
 // Condition for ODD block
 private final Condition oddCondition = aLock.newCondition(); 
 
 // Condition for EVEN block
 private final Condition evenCondition = aLock.newCondition();
 
 // Variable to print ODD/ EVEN numbers
 private int counter = 1;
 
 /*
  * ODD Block
  */
 public void printOdd() throws InterruptedException {
  while(counter <= 10) {
   try {
    // Getting lock for ODD block
    aLock.lock();
    System.out.println("ODD : "+ counter++);
    // signaling to EVEN condition 
    evenCondition.signal();
    /*
     * Just stopping await once reach counter to 10.
     * Not to odd thread to await indefinitely  
     */
    if(counter < 10) { 
     oddCondition.await();
    }
   }finally {
    aLock.unlock();
   }
  }
 }
 
 /*
  * EVEN Block
  */
 public void printEven() throws InterruptedException {
  while(counter <= 10) {
   try {
    // Getting lock for EVEN block
    aLock.lock();
    System.out.println("EVEN : "+ counter++);
    // signaling to ODD condition 
    oddCondition.signal();
    /*
     * Just stopping await once reach counter to 10.
     * Not to even thread to await indefinitely  
     */
    if(counter < 10) {
     evenCondition.await();
    }
   }finally {
    aLock.unlock();
   }
  }
 }
}

class Odd extends Thread {
 OddEvenImpl pc;
 public Odd(OddEvenImpl pc) {
  this.pc = pc;
 }
 @Override
    public void run() {
        try {
            pc.printOdd();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

class Even extends Thread {
 OddEvenImpl pc;
 public Even(OddEvenImpl pc) {
  this.pc = pc;
 }
 @Override
    public void run() {
        try {
            pc.printEven();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

OUTPUT:

ODD : 1
EVEN : 2
ODD : 3
EVEN : 4
ODD : 5
EVEN : 6
ODD : 7
EVEN : 8
ODD : 9
ODD : 10

Dynamic Programming - Find nth Fibonacci number

Dynamic Programming - Find nth Fibonacci number

recursion  

Dynamic Programming (DP) is an algorithmic that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again for another subproblems. Just make use of the previously computed result by storing and by this complexity will be reduced. Usually we used to write a recursive call for getting list of Fibonacci series or to get the nth element in Fibonacci series. Here we will see simple recursive method for getting nth Fibonacci number with and without dynamic programming and latter will compare the benefits of using DP.

Find nth Fibonacci number using recursive:

public class Fibonacci {
 
 static int i = 0;
 
 public static void main(String[] args) {
  int n = 10;
  int val = fibo(n);
  System.out.println("No. of recursive calls : "+i);
  System.out.println(n +"th Fibonacci number : "+val);
  
 }
 
 public static int fibo(int n) {
  System.out.println("CALL ::: "+ (++i) + " - n: "+n);
  if(n<=2) {
   return 1;
  }
  else {
   int f = fibo(n-1) + fibo(n-2);
   return f;
  }
 }
}

OUTPUT:

CALL ::: 1 - n: 10
CALL ::: 2 - n: 9
CALL ::: 3 - n: 8
CALL ::: 4 - n: 7
CALL ::: 5 - n: 6
CALL ::: 6 - n: 5
CALL ::: 7 - n: 4
CALL ::: 8 - n: 3
CALL ::: 9 - n: 2
CALL ::: 10 - n: 1
CALL ::: 11 - n: 2
CALL ::: 12 - n: 3
CALL ::: 13 - n: 2
CALL ::: 14 - n: 1
CALL ::: 15 - n: 4
CALL ::: 16 - n: 3
CALL ::: 17 - n: 2
CALL ::: 18 - n: 1
CALL ::: 19 - n: 2
CALL ::: 20 - n: 5
CALL ::: 21 - n: 4
CALL ::: 22 - n: 3
CALL ::: 23 - n: 2
CALL ::: 24 - n: 1
CALL ::: 25 - n: 2
CALL ::: 26 - n: 3
CALL ::: 27 - n: 2
CALL ::: 28 - n: 1
CALL ::: 29 - n: 6
CALL ::: 30 - n: 5
CALL ::: 31 - n: 4
CALL ::: 32 - n: 3
CALL ::: 33 - n: 2
CALL ::: 34 - n: 1
CALL ::: 35 - n: 2
CALL ::: 36 - n: 3
CALL ::: 37 - n: 2
CALL ::: 38 - n: 1
CALL ::: 39 - n: 4
CALL ::: 40 - n: 3
CALL ::: 41 - n: 2
CALL ::: 42 - n: 1
CALL ::: 43 - n: 2
CALL ::: 44 - n: 7
CALL ::: 45 - n: 6
CALL ::: 46 - n: 5
CALL ::: 47 - n: 4
CALL ::: 48 - n: 3
CALL ::: 49 - n: 2
CALL ::: 50 - n: 1
CALL ::: 51 - n: 2
CALL ::: 52 - n: 3
CALL ::: 53 - n: 2
CALL ::: 54 - n: 1
CALL ::: 55 - n: 4
CALL ::: 56 - n: 3
CALL ::: 57 - n: 2
CALL ::: 58 - n: 1
CALL ::: 59 - n: 2
CALL ::: 60 - n: 5
CALL ::: 61 - n: 4
CALL ::: 62 - n: 3
CALL ::: 63 - n: 2
CALL ::: 64 - n: 1
CALL ::: 65 - n: 2
CALL ::: 66 - n: 3
CALL ::: 67 - n: 2
CALL ::: 68 - n: 1
CALL ::: 69 - n: 8
CALL ::: 70 - n: 7
CALL ::: 71 - n: 6
CALL ::: 72 - n: 5
CALL ::: 73 - n: 4
CALL ::: 74 - n: 3
CALL ::: 75 - n: 2
CALL ::: 76 - n: 1
CALL ::: 77 - n: 2
CALL ::: 78 - n: 3
CALL ::: 79 - n: 2
CALL ::: 80 - n: 1
CALL ::: 81 - n: 4
CALL ::: 82 - n: 3
CALL ::: 83 - n: 2
CALL ::: 84 - n: 1
CALL ::: 85 - n: 2
CALL ::: 86 - n: 5
CALL ::: 87 - n: 4
CALL ::: 88 - n: 3
CALL ::: 89 - n: 2
CALL ::: 90 - n: 1
CALL ::: 91 - n: 2
CALL ::: 92 - n: 3
CALL ::: 93 - n: 2
CALL ::: 94 - n: 1
CALL ::: 95 - n: 6
CALL ::: 96 - n: 5
CALL ::: 97 - n: 4
CALL ::: 98 - n: 3
CALL ::: 99 - n: 2
CALL ::: 100 - n: 1
CALL ::: 101 - n: 2
CALL ::: 102 - n: 3
CALL ::: 103 - n: 2
CALL ::: 104 - n: 1
CALL ::: 105 - n: 4
CALL ::: 106 - n: 3
CALL ::: 107 - n: 2
CALL ::: 108 - n: 1
CALL ::: 109 - n: 2
No. of recursive calls : 109
10th Fibonacci number : 55

If we seen above output we can get to know that just for 10th Fibonacci number total 109 recursive calls made. Also in many cases like Fibo(4), Fibo(5), Fino(3) etc., are multiple times computed for same value. So here we need to use the power of Dynamic Programming to store the computed value and need to reuse the result if same value occurs again. By this we can avoid lot of iterations/recursive call's.

Lets see converting above program to Dynamic Programming by storing the computed value and reusing it again when its need. By this lets find out how many recursive calls made for getting 10th Fibonacci number.

Find nth Fibonacci number using Dynamic Programming:

import java.util.HashMap;

public class Fibonacci {
 
 static int i = 0;
 static HashMap<Integer, Integer> map = new HashMap<>();
 
 public static void main(String[] args) {
  int n = 10;
  int val = fibo(n);
  System.out.println("No. of recursive calls : "+i);
  System.out.println(n +"th Fibonacci number : "+val);
  
 }
 
 public static int fibo(int n) {
  
  if(map.containsKey(n)) 
   return map.get(n);
  
  System.out.println("CALL ::: "+ (++i) + " - n: "+n);
  if(n<=2) {
   map.put(n, 1);
   return 1;
  }
  else {
   int f = fibo(n-1) + fibo(n-2);
   map.put(n, f);
   return f;
  }
 }
}

OUTPUT:

CALL ::: 1 - n: 10
CALL ::: 2 - n: 9
CALL ::: 3 - n: 8
CALL ::: 4 - n: 7
CALL ::: 5 - n: 6
CALL ::: 6 - n: 5
CALL ::: 7 - n: 4
CALL ::: 8 - n: 3
CALL ::: 9 - n: 2
CALL ::: 10 - n: 1
No. of recursive calls : 10
10th Fibonacci number : 55

Now we can compare the no. of recursive calls made my 1st program and 2nd program exactly to get the same output of 10th Fibonacci number. If we see 1st program taken 109 recursive calls and 2nd dynamic program taken only 10 recursive calls for same problem and output.