Sunday, December 20, 2015

Snake and Ladder using graph in Java

Hello guys, today I want to talk about the well known game of all times. Snake and ladders.

Let us think of creating the game in Java using Graph.

Before starting I have to clear some of the points.

  1. I didn't entertained edge cases to the maximum. 
  2. Also I have created 2 different graph. one for ladders addresses and one for snakes addresses.
  3. There are different approaches of solving this problem as well but I have used graph in order to do so.
  4. Now lets see the program.
Full code is available here

Example code

package com.av.demosnakeladder;

import java.util.ArrayList;
import java.util.List;

import org.jgrapht.DirectedGraph;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;

public class DemoSnakeLadder {

 public static void main(String[] args) {
  
  Integer board[] = new Integer[101];
  
  for(int i=1; i<100; i++){
   board[i] = new Integer(i);
  }
  
  List<GroupInfo> laddersInfo = new ArrayList<GroupInfo>();
   laddersInfo.add(new GroupInfo(board[2], board[32]));
   laddersInfo.add(new GroupInfo(board[14], board[57]));
   laddersInfo.add(new GroupInfo(board[27], board[78]));
   laddersInfo.add(new GroupInfo(board[34], board[44]));
   laddersInfo.add(new GroupInfo(board[7], board[98]));
  //Ladder Configuration
  DirectedGraph<Integer, DefaultEdge> ladders = new DefaultDirectedGraph<Integer, DefaultEdge>(DefaultEdge.class);
  /*
   * Ladders are at 
   * 2 -> 32
   * 14 -> 57
   * 27 -> 78
   * 34 -> 44
   * 7 -> 98
   */
  for(GroupInfo gi : laddersInfo){
   ladders.addVertex(gi.getStartIndex());
   ladders.addVertex(gi.getEndIndex());
   ladders.addEdge(gi.getStartIndex(), gi.getEndIndex());
  }
  
  
  List<GroupInfo> snakesInfo = new ArrayList<GroupInfo>();
   snakesInfo.add(new GroupInfo(board[99], board[10]));
   snakesInfo.add(new GroupInfo(board[77], board[22]));
   snakesInfo.add(new GroupInfo(board[62], board[13]));
   snakesInfo.add(new GroupInfo(board[54], board[8]));
   snakesInfo.add(new GroupInfo(board[42], board[3]));
  
  //Snake Configuration
  DirectedGraph<Integer, DefaultEdge> snakes = new DefaultDirectedGraph<Integer, DefaultEdge>(DefaultEdge.class);
  /*
   * Snakes are at
   * 99 -> 10
   * 77 -> 22
   * 62 -> 13
   * 54 -> 8
   * 42 -> 3
   */
  for(GroupInfo gi : snakesInfo){
   snakes.addVertex(gi.getStartIndex());
   snakes.addVertex(gi.getEndIndex());
   snakes.addEdge(gi.getStartIndex(), gi.getEndIndex());
  }
  
  /*
   * These are the current positions of the player, I am considering 1 players
   */
  int player1 = 1;
  
  //The game goes till he reaches 100
  while(player1  != 100){
   //get the value of dice and 
   int nextValue = getNextDiceValue();
   System.out.println("Player is in " + player1 + " and got " + nextValue + " so next position is " + (player1 + nextValue));
   
   if((player1 + nextValue) <= 100){
    
    if((player1 + nextValue) == 100){
     System.out.println("!!!Congratulations you won!!! ");
     System.out.println("Bye, have a nice day");
     break;
    }
    
    //Now this is the current position of the player
    player1 += nextValue;
    
    Integer boardCurrentValue = board[player1];
    
    if(ladders.containsVertex(boardCurrentValue)){
     boardCurrentValue = ladders.getEdgeTarget(ladders.edgesOf(boardCurrentValue).iterator().next());
     System.out.println("Congratulations, you got ladder to " + boardCurrentValue);
     player1 = boardCurrentValue;
    }else if(ladders.containsVertex(boardCurrentValue)){
     boardCurrentValue = snakes.getEdgeTarget(snakes.edgesOf(boardCurrentValue).iterator().next());
     System.out.println("Oops, you get stung by snake and now you came to " + boardCurrentValue);
     player1 = boardCurrentValue;
    }
   }
  }
 }
 
 private static int getNextDiceValue(){
  //here randomize the dice for value between 1 & 6 and return the value that comes back
  int result = 0;
  
  while(result == 0){
   result = (int)(Math.random() * 10);
   
   if(result > 6){
    result -= 6;
   }
  }
  return result;
 }
}

class GroupInfo{
 private Integer startIndex;
 private Integer endIndex;

 public GroupInfo(Integer startIndex, Integer endIndex) {
  super();
  this.startIndex = startIndex;
  this.endIndex = endIndex;
 }

 public Integer getStartIndex() {
  return startIndex;
 }

 public void setStartIndex(Integer startIndex) {
  this.startIndex = startIndex;
 }

 public Integer getEndIndex() {
  return endIndex;
 }

 public void setEndIndex(Integer endIndex) {
  this.endIndex = endIndex;
 }
}


Tuesday, December 15, 2015

Graph in Java

Hello all, today let's see something about the Graphs.

So technically speaking Graph is "A graph in this context is made up of vertices or nodes or points and edges or arcs or lines that connect them. A graph may be un-directed, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another. "- Wiki

So now we can say that we understand what a graph is. Right?

Ok let me try to rephrase the things in a different way. Graph is a data structure with Vertices and Edges. Now vertices are the nodes and edges are the connectors between these nodes. A graph can be directed or non directed with weights on edges.

Why is graph theory so important?
    In real world, the graph theory is important in neural network, shortest path between 2 destinations and many more applications of graph are there.

Now coming to the Java, there are number of libraries available to use, but I have used JGraphT and found it pretty descent. The api is available here. You can incorporate it in your project via Maven or including it in the classpath after downloading the jar.

Let us take an example of Graph using JGraphT library.

Code can be found here.

Code snippet
import java.net.MalformedURLException;
import java.net.URL;

import org.jgrapht.DirectedGraph;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleGraph;

public class DemoGraph {

 public static void main(String[] args) {

  UndirectedGraph<String, DefaultEdge> stringGraph = createStringGraph();

  // note undirected edges are printed as: {<v1>,<v2>}
  System.out.println(stringGraph.toString());

  // create a graph based on URL objects
  DirectedGraph<URL, DefaultEdge> hrefGraph = createHrefGraph();
  
  DirectedGraph<Integer, DefaultEdge> ladder = new DefaultDirectedGraph<Integer, DefaultEdge>(DefaultEdge.class);

  Integer two = new Integer(2);
  Integer twentyOne = new Integer(21);
  
  ladder.addVertex(two);
  ladder.addVertex(twentyOne);
  
  ladder.addEdge(two, twentyOne);
  
  System.out.println(ladder.getEdgeTarget(ladder.edgesOf(two).iterator().next()));
  
  // note directed edges are printed as: (<v1>,<v2>)
  System.out.println(hrefGraph.toString());
 }

 /**
  * Creates a toy directed graph based on URL objects that represents link
  * structure.
  *
  * @return a graph based on URL objects.
  */
 private static DirectedGraph<URL, DefaultEdge> createHrefGraph() {
  DirectedGraph<URL, DefaultEdge> g = new DefaultDirectedGraph<URL, DefaultEdge>(DefaultEdge.class);

  try {
   URL amazon = new URL("http://www.amazon.com");
   URL yahoo = new URL("http://www.yahoo.com");
   URL ebay = new URL("http://www.ebay.com");

   // add the vertices
   g.addVertex(amazon);
   g.addVertex(yahoo);
   g.addVertex(ebay);

   // add edges to create linking structure
   g.addEdge(yahoo, amazon);
   g.addEdge(yahoo, ebay);
  } catch (MalformedURLException e) {
   e.printStackTrace();
  }

  return g;
 }

 /**
  * Create a toy graph based on String objects.
  *
  * @return a graph based on String objects.
  */
 private static UndirectedGraph<String, DefaultEdge> createStringGraph() {
  UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>(
    DefaultEdge.class);

  String v1 = "v1";
  String v2 = "v2";
  String v3 = "v3";
  String v4 = "v4";

  // add the vertices
  g.addVertex(v1);
  g.addVertex(v2);
  g.addVertex(v3);
  g.addVertex(v4);

  // add edges to create a circuit
  g.addEdge(v1, v2);
  g.addEdge(v2, v3);
  g.addEdge(v3, v4);
  g.addEdge(v4, v1);

  return g;
 }

}

Wednesday, December 9, 2015

Annotation in Java

Hello guys, today we will try to learn something about the Annotations.

Annotation:
    "An annotation is a metadata (e.g. a comment, explanation, presentational markup) attached to text, image, or other data.Often, annotations make reference to a specific part of the original data." - Wiki

In other words, it is a kind of code that gives the user a way to pass some data from its code to the developer of the annotation who have given annotations to use in the code so that he knows that the user wants to do what.

Oh my God, what have I read there? :O

Well let us take an example like we have to get the data from the database. So for that we :
  1. Have to create a connection 
  2. Open a connection
  3. Get the data considering the exceptions and all
  4. After getting the data, close the connection
  5. Release the memory
Now these 5 steps are going to be happened all the times whenever we have to get the data from the database.

These type of codes which are to be executed number of times are termed as boiler plate codes. And in order to get rid of boiler plate codes Java have introduced the concept of Annotation.

Now the annotation is a very useful feature. If you have used the Spring, Hibernate or any framework you would have gone through it.

Lets take an example of reading and making the annotation in Java.

You can get  the project from here.

Its basically a simple project that works in the following way:
  1. We first create an annotation that have the properties which would be available (TestAnnotation.java).
  2. Then I have created the Java class where I used the annotation created in step no: 1(TestClassWithAnnotationUsed.java).
  3. And lastly I have coded the class that will read all the functions that used our annotation(ClassThatReadsAnnotation.java)
TestAnnotation.java
import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;

@Retention(RetentionPolicy.RUNTIME)
@Target(ElementType.METHOD)
public @interface TestAnnotation {
 public String name() default "";
}

ClassThatReadsAnnotation.java
import java.lang.annotation.Annotation;
import java.lang.reflect.Method;

import com.av.demo.annotation.TestAnnotation;

public class ClassThatReadsAnnotation {

 
 public static void main(String[] args) {
  System.out.println("Lets first create a normal object of the TestClassWithAnnotationUsed class");
  TestClassWithAnnotationUsed obj = new TestClassWithAnnotationUsed();
  System.out.println("Now call the method and see whether it works or not");
  obj.functionWithAnnotationApplied_1();
  System.out.println("Now we read the annotation and try to get the value that is passed in for the string. "
    + "\nThis is usually done by reading the annotation in the runtime. "
    + "\nAnd this is done by the concept called Reflection of Java. "
    + "\nBy the we can actually manipulate the classes and objects in runtime, "
    + "\nwhich is internally by the apis like spring and hibernate. ");
  
  //Getting the reference of the class Object
  Class<Testclasswithannotationused> testClassWithAnnotationUsedClass = TestClassWithAnnotationUsed.class;
  
  for (Method method : testClassWithAnnotationUsedClass.getDeclaredMethods()) {
   //Checking for the presence of the Annotation we have made
   if(method.isAnnotationPresent(TestAnnotation.class)){
    Annotation annotation = method.getAnnotation(TestAnnotation.class);
    TestAnnotation test = (TestAnnotation) annotation;
    System.out.println(test.name());
   }
  }
  
 }
 
}

TestClassWithAnnotationUsed.java
import com.av.demo.annotation.TestAnnotation;

public class TestClassWithAnnotationUsed {
 
 @TestAnnotation(name="ACCEPTED_VALUE")
 public void functionWithAnnotationApplied_1(){
  System.out.println("I have applied the annotation TestAnnotation with value ACCEPTED_VALUE");
 }
 
 
 @TestAnnotation(name="NON_ACCEPTED_VALUE")
 public void functionWithAnnotationApplied_2(){
  System.out.println("I have applied the annotation TestAnnotation with value NON_ACCEPTED_VALUE");
 }
}

Wednesday, December 2, 2015

Breadth First Traversal in Binary Trees

Hey guys, lets see the way of traversing the tree in a breadth first fashion.

So when the question comes for traversing the tree there are broadly two categories:

  1. Depth First Approach
    1. InOrder
    2. PreOrder
    3. PostOrder
  2. Breadth First Approach
In the first approach the style of traversing the tree is in a depth first fashion which means, that we keep on traversing the tree in a manner that goes vertically rather than horizontally.

In case of the breadth first approach we go layer by layer or in other words we go level by level. 

So if I have a tree like:
then in this tree, we will say that the :
  • 1 is at Level 0
  • 2,3 is at level 1
  • 4,5,6,7 is at level 2
  • 10,11,8,9 is at level 3
  • 12,13 is at level 4
So going forward with this approach we want to traverse the the tree in a level wise manner, and at the end the traversal would be : 1,2,3,4,5,6,7,10,11,8,9,12,13

Now coming to the code of this, it is very easy, if we uses queue in the code. We start by root and we keep pushing the children of the traversed node in to queue and keep on traversing the node taking from the queue.

Code here

import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

class BFS {

 public static void main(String[] args) {
  Node n1 = new Node(1);
  Node n2 = new Node(2);
  Node n3 = new Node(3);
  Node n4 = new Node(4);
  Node n5 = new Node(5);
  Node n6 = new Node(6);
  Node n7 = new Node(7);
  Node n8 = new Node(8);
  Node n9 = new Node(9);
  Node n10 = new Node(10);
  Node n11 = new Node(11);
  Node n12 = new Node(12);
  Node n13 = new Node(13);
  
  n1.left = n2;
  n1.right = n3;
  
  n2.left = n4;
  n2.right = n5;
  
  n3.left = n6;
  n3.right = n7;
  
  n4.left = n4.right = null;
  
  n5.left = n10;
  n5.right = n11;
  
  n6.left = n6.right = null;
  
  n7.left = n8;
  n7.right = n9;
  
  n10.left = n12;
  n10.right = n13;
 
  n11.left = n11.right = null;
  
  n8.left = n8.right = null;
  n9.left = n9.right = null;
  
  Node root = n1; 
  Queue<Node> queue = new LinkedBlockingQueue<Node>();
  queue.add(root);
  
  while(!queue.isEmpty()){
   Node n = queue.poll();
   if(n.left !=null){
    queue.add(n.left);
   }
   if(n.right!=null){
    queue.add(n.right);
   }
   
   System.out.print(n.info + ", ");
  }
 }
 
}

 class Node{
 public Node left;
 public Node right;
 public int info;
 
 public Node(int info){
  this.info = info;
  this.left = null;
  this.left = null;
 }
 
 public String toString(){
  return "" + this.info;
 }
}

Tuesday, December 1, 2015

Lowest Common Ancestor of a Tree

Hello guys, during one of my interview, the interviewer asked me something about the Lowest Common Ancestor. At first point it was a bit unusual thing as I never heard of it before, but when he explained me the stuff that what is a Lowest Common Ancestor, I found that it is quite good.

So here it goes lets suppose you have a tree like this:

The example is pretty clear. If you look closely you will find out that the lowest common ancestor is the common root for both the nodes. So:

  • If  you take the case of the 4, 5 the first common root (or more preferably ancestor/parent) is 2
  • If  you take the case of the 4, 6 the first common root (or more preferably ancestor/parent) is 1
Now the question arises how do we get to this using the program. So let me try to explain the simple solution what we can do for this to work:

First of all let us try to understand the basic traversing algos of the Trees (binary). These are as follows:
  1. In-Order(Left-Node-Right)
  2. Post-Order(Left-Right-Node)
  3. Pre-Order(Node-Left-Right)


So considering the above example, let us try to take out the In-Order and Pre-Order:
  • In-Order will be 4, 2, 12, 10, 13, 5, 11, 1, 6, 3, 8, 7, 9
  • Post-Order will be 4, 12, 13, 10, 11, 5, 2, 6, 8, 9, 7, 3, 1
Now after this we can say some of the key points, those are:
  1. The left subtree of any node is available in Inorder
  2. Now take all the subnodes of two nodes for which we have to find the LCA
  3. Now if you select the node at the maximum index in Post-order among all the nodes of step (2) list you will find the LCA.
Explanation:
The reason is very clear the Inorder gives you all the possible in between nodes of the 2 nodes for which you want to find the LCA. Now out of these nodes the root of these in between nodes, i.e LCA in other terms would be at last in Post order because by definition of Post order we always have the Node at the last. So considering this, if we want to get the LCA for Node 6 and Node 9 then the answer would be 3.

Note:
  • I have considered the above example for my reference and have created the code according to the above scenario, so please update it according to your needs.
  • The overall example and logic will remain the same only the creation of the tree will change. So the left and right might change in a tree.
  • I have just coded the basic one, didn't covered the edge cases and all the checks.
Working code here:

Java Code
package com.test.tree;

import java.util.ArrayList;
import java.util.List;

public class TreeTraversal {
 
 public static final List<Node> inOrderList = new ArrayList<>(); 
 public static final List<Node> preOrderList = new ArrayList<>();
 public static final List<Node> postOrderList = new ArrayList<>(); 

 public static void main(String[] args) {
  
  Node n1 = new Node(1);
  Node n2 = new Node(2);
  Node n3 = new Node(3);
  Node n4 = new Node(4);
  Node n5 = new Node(5);
  Node n6 = new Node(6);
  Node n7 = new Node(7);
  Node n8 = new Node(8);
  Node n9 = new Node(9);
  Node n10 = new Node(10);
  Node n11 = new Node(11);
  Node n12 = new Node(12);
  Node n13 = new Node(13);
  
  n1.left = n2;
  n1.right = n3;
  
  n2.left = n4;
  n2.right = n5;
  
  n3.left = n6;
  n3.right = n7;
  
  n4.left = n4.right = null;
  
  n5.left = n10;
  n5.right = n11;
  
  n6.left = n6.right = null;
  
  n7.left = n8;
  n7.right = n9;
  
  n10.left = n12;
  n10.right = n13;
 
  n11.left = n11.right = null;
  
  n8.left = n8.right = null;
  n9.left = n9.right = null;
  
  
  inOrder(n1);
  System.out.println("Inorder traversal is " + inOrderList);
  postOrder(n1);
  System.out.println("Postorder traversal is " + postOrderList);
  
  /*
   * 1. we take the list of nodes that are in between them
   * 2. then we take the address of each node of the above found list 
   * 3. the node that is in the farthest position, will be the LCA 
   */
  Node fn = n6;
  Node sn = n9;
  System.out.println("We are gonna find the LCA between " + fn + " & " + sn);
  List<Node> inBetweenList = inBetween(inOrderList, fn, sn);
  System.out.println("The nodes in between " + fn + " and " + sn + " are as follows " + inBetweenList);
  System.out.println("LCA of " + fn + " & " + sn + " is " + lca(inBetweenList, postOrderList));
 }
 
 public static List inBetween(List<node> inOrder, Node fn, Node sn){
  int i1 = inOrder.indexOf(fn);
  int i2 = inOrder.indexOf(sn);
  List<Node> result = i1 > i2 ? inOrder.subList(i2, i1 + 1) :  inOrder.subList(i1, i2 + 1);
  return result;
 }
 
 public static Node lca(List<node> inBetweenList, List<node> postOrderList){
  Node result = null;
  int maxIndex = 0;
  for(Node node : inBetweenList){
   maxIndex = postOrderList.indexOf(node) > maxIndex ? postOrderList.indexOf(node) : maxIndex;
  }
  
  result = postOrderList.get(maxIndex);
  return result;
 }
 
 public static void inOrder(Node root){
  if(root == null){
   return;
  }
  inOrder(root.left);
  inOrderList.add(root);
  inOrder(root.right);
 }
 
 public static void preOrder(Node root){
  if(root == null){
   return;
  }
  preOrderList.add(root);
  preOrder(root.left);
  preOrder(root.right);
  
 }
 
 public static void postOrder(Node root){
  if(root == null){
   return;
  }
  postOrder(root.left);
  postOrder(root.right);
  postOrderList.add(root);
 }
 
}


class Node{
 public Node left;
 public Node right;
 public int info;
 
 public Node(int info){
  this.info = info;
  this.left = null;
  this.left = null;
 }
 
 public String toString(){
  return "" + this.info;
 }
}

Monday, November 30, 2015

Getting the Prime numbers using the Sieve of Eratosthenes method

Hello Guys, today we are going to look the method by which the large number of prime numbers can be calculated.

The definition of the Sieve of Eratosthenes method goes this way:
"Mark the first presence of the number as prime and mark all its multiples as non primes." - Wiki


Looking at the diagram its pretty clear to understand that the first presence of number is considered to be prime and all the multiples of it (increasing order) is marked non prime also, we will check for the prime only if the number is not marked as non prime before, like in case of 6, the number would be marked as non prime before while we run the thing for the number 2 so it is skipped in case of 3.

Now lets see the program as well, running link here

Here is the code:

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public static void main(String[] args) {
  int MAX = 1000000;
  int T = 0;
  boolean isPrime[] = new boolean[MAX];
  for(int i=2; i<isPrime.length; i++)
   isPrime[i] = true;
  
  int primes[] = new int[MAX];
  int p = 0;
  for(int i=2;i<MAX;i++){
   if(isPrime[i]){
    primes[p++] = i;
    for(int j=2*i; j<MAX; j+=i)
     isPrime[j] = false;
   }
  }
  System.out.println("All your prime numbers are calculated, just for example I am taking out the 10101th prime number");
  T = 10101;
  System.out.println(primes[T]);
    }
}

Friday, November 20, 2015

Anagram String and its solutions

Hello Friends, today I want to discuss something about the anagram strings.

Now What is an Anagram String?
   "An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once; for example, the word anagram can be rearranged into nag-a-ram." - Wiki

Now if I understood correctly then in one way or the other we have to use the same letters that are there in first word for exactly the same number of times they appeared in it, for the second word in any order.

Now coming to the solution part. There are many ways of checking the anagram strings.
  1. Using the sorting solution
  2. Using the prime number solution
Using the Sorting Algorithm:
    This is pretty simple way of checking the Anagram Strings. In this we sort both the Strings that we get for being checked as Anagram and then checks that both the results should be identical.

  For example: 
    If I pass 2 strings, say Anagram and Nagaram, then the algo goes like this:
  • Checks whether the length of both the strings are same, if not there is no profit in going forward
  • Then change strings to lower case/Upper case, to make sure there should not be any difference because of the cases.
  • Sorts both the strings in their natural way either increasing or decreasing order
  • Then checks whether both the sorted results are identical
  Program:

public class AnagramCheck_Sort{
 public static boolean isAnagram(String s1, String s2){
  // Early termination check, if strings are of unequal lengths,
  // then they cannot be anagrams
  if (s1==null || s2==null || s1.length() != s2.length() ) {
   return false;
  }

  char[] c1 = s1.toLowerCase().toCharArray();
  char[] c2 = s2.toLowerCase().toCharArray();
  Arrays.sort(c1);
  Arrays.sort(c2);
  String sc1 = new String(c1);
  String sc2 = new String(c2);
  return sc1.equals(sc2);
 }
 public static void main(String[] args){
  System.out.println(isAnagram("Anagram","nagaram"));
 }
}

Using the prime number solution:
    This method is like the brute force. Here goes ihe algo:

  • Checks whether the length of both the strings are same if not there is no profit in going forward.
  • Then makes a map of character and assign 1 unique prime number to it.For instance assign character 'a' the prime number 2, and character 'b' the prime number 3 and so on for all 26 letters.
  • then runs the loop and keep on multiplying by the number that each character posses and keep it in a different variable as a product
  • At last because all the number were prime in nature and also the product of two unique primes are always unique we end up getting two products which tells us whether the strings are prime or not. If the two products are same then the strings are prime otherwise not
  • One point to note that because we are multiplying the numbers the variable should be of big datatype.
Program:
Here is running version : link

class AnagramCheck_Sort{
 public static boolean isAnagram(String s1, String s2){
  // Early termination check, if strings are of unequal lengths,
  // then they cannot be anagrams
  if (s1==null || s2==null || s1.length() != s2.length() ) {
   return false;
  }
  s1=s1.toLowerCase();s2=s2.toLowerCase();
  Integer p1 = 1; Integer p2 = 1;
  for(int i=0, len=s1.length(); i!=len; i++){
   char c1 = s1.charAt(i);char c2 = s2.charAt(i);
   p1 = p1 * primesMap.get(c1);p2 = p2 * primesMap.get(c2);
  }

  return p1.equals(p2);
 }
 public static void main(String[] args){
  primesMap.put('a',2);primesMap.put('b',3);primesMap.put('c',5);primesMap.put('d',7);primesMap.put('e',11);primesMap.put('f',13);
  primesMap.put('g',17);primesMap.put('h',19);primesMap.put('i',23);primesMap.put('j',29);primesMap.put('k',31);primesMap.put('l',37);
  primesMap.put('m',41);primesMap.put('n',43);primesMap.put('o',47);primesMap.put('p',53);primesMap.put('q',59);primesMap.put('r',61);
  primesMap.put('s',67);primesMap.put('t',71);primesMap.put('u',73);primesMap.put('v',79);primesMap.put('w',83);primesMap.put('x',89);
  primesMap.put('y',97);primesMap.put('z',101);
 
  System.out.println(isAnagram("Anagram","nagaram"));
 }
 
 private static Map<character ,Integer> primesMap = new HashMap<>();
}

Wednesday, September 16, 2015

Storm Apache, how it works

Hello Friends, today we are going to look on to very emerging technology of Apache which is being created by Twitter and later took by Apache that gives us the way of real time processing in a step wise manner.

You might be thinking, step wise manner? What the hell is this step wise manner?

Now let me give you a very basic example of hotel or restaurant. If you go in to a hotel, you will find that one person just opens the door, one person just takes the order, one person cooks it and one person serves it. And when everything is over you go to another person to pay the bill.

Now this is a very simple and basic example where you can see that the overall system, that is a restaurant, has multiple actors (gate boy, waiter, cook, receptionist etc), and these multiple actors are doing there work in a sync being the part of one system.

In the same way storm gives us the functionality of processing the data with the help of multiple actors(running in same/different machines, under a common roof, tell you after sometime).

In storm world we have different terms to describe the functionality of the part of the system.
  • Spout
    • Spout is a starting point of the ecosystem. In our example you being a customer is a Spout. This is b'coz unless and until you enters the restaurant, the process don't starts, which means all the actors becomes active only when you enters the restaurant.
  • Bolt
    • Blot is a part of the Storm ecosystem who do the things, or in other words the doers, actors or executors.
  • Topology
    • The overall ecosystem is bound by Topology. It is the one who tell Storm, how to react and communicate to which actor after which actor in which manner. Or I can say that it is the head of all the connection of the actors.
Storm needs Zookeeper to interact with other actors of its team, in Production Mode. In simple words if you have created a full fledged system where you have n number of Actors then you can run this in different machines so that your full function can be finished by the power of n processors simultaneously or sequentially then you need a Zookeeper to manage these machines(actors).

Storm runs in 2 modes:
  1. Development Mode
  2. Production Mode
Development Mode:
          In this mode, the code you do with Storm API don't need any other machine or Zookeeper to test. It can be executed in the same machine and thus don't need Zookeeper for its functionality.

Production Mode:
          In this mode we have to install a full fledged Zookeeper in multiple machines and starts the Storm server by giving these Zookeeper nodes in the config so that Storm server can interact with all the bolts of the topology[I know its a bit technical but now you know what is what, :-) ]

Now lets jump to the basic example of Storm, you can find this example here.

I am going to post the code here and then will explain each line of the code one by one.

Before starting the basic example of the Storm let me explain you the parts of the example:
  1. Spout: This is a class that acts as the creator of the messages. For this example I am just picking a random sentence from a List of predefined sentences and emitting it
  2. Bolt This is the class that is attached to the spout and will read the sentence that is being projected by the spout(SentenceSpout) 
  3. Topology: This class contains the main method that is having the overall handshake of classes.
  4. pom.xml: This file contains the dependencies to be used in development of the code.
You can find the code here

Explanation:
  1. LearningStormSpout.java: This class is doing the job of publishing the data in a stream whose name is "site". If you see the function declareOutputFields, you will see that we have declared the output field named "site". This is pretty straight forward since the data is emitting from the nextTuple(), where we are just picking a random sentence and emitting it. This sentence is going to be emitted on a stream whose name will be site.
  2. LearningStormBolt.java: This is the class whose job is to read the data coming on a specific stream. If you see the code under execute(), you will find that I am reading the stream whose name is site (line #15). This is because our data generator is pushing the data under stream named site. 
  3. LearningStormTopology.java: This class is the structure of your overall ecosystem of multiprocessing environment. If you see (line #17), we are actually creating a topology with the spout as LearningStormSpout, the first bolt of this as LearningStormBolt and kept the grouping to be shuffle grouping on the id which is same as the spout ID. 
  4. At last we have started the topology in a development mode and submitted it in a local cluster so that we can test it and see whether or not we are getting the correct results or not.
There is another way of starting the topology in a distributed environment which I will cover in other tutorial. For your information, in the distributed environment we have to install zookeeper in a cluster environment and install Storm server over these zookeepers and then have to install the jar of our topology on this Storm server.

Sunday, August 9, 2015

Detecting the loops in a linked list

Hello Friends today I want to take one of the question that one of my friend asked me which he faced in an interview.

How would you detect whether the linked list has the loop or not?

Let us take a basic example, so assume you have the linked list like that looks like this:

A -> B -> C -> D ->B

Now if you look at the list you find out that the last node is pointing towards B. So now the question is how would you find whether the list has a loop or not.

For this problem there are some solutions, one of them is Floyd's cycle-finding algorithm, also known as tortoise and hare algorithm.

The algorithm's idea is that, maintains 2 pointers and move with them with different speeds, one fast and one slow, if there is a loop, one time they will definitely meet.

Going forward with this idea in mind, let us see the program.


boolean hasLoop(Node first) {
    if (first == null) // list does not exist..so no loop either.
        return false;
    Node slow, fast; // create two references.
    slow = fast = first; // make both refer to the start of the list.
    while (true) {
        slow = slow.next;          // 1 hop.
        if (fast.next != null)
            fast = fast.next.next; // 2 hops.
        else
            return false;          // next node null => no loop.

        if (slow == null || fast == null) // if either hits null..no loop.
            return false;
        if (slow == fast) // if the two ever meet...we must have a loop.
            return true;
    }
}

Now the other problem is to know the start of the loop. For that we follow:

Step1: Proceed in the usual way u'll use to find the loop. ie. Have two pointers, increment one in single step and other in two steps, If they both meet in sometime, there is a loop.

Step2: Freeze one pointer where it was and increment the other pointer in one step counting the steps u make and when they both meet again, the count will give u the length of the loop.(This is same as counting the number of elements in a circular link list.)

Step3: Reset both pointers to the start of the link list, increment one pointer to the length of loop times and then start the second pointer. increment both pointers in one step and when they meet again, it'll be the start of the loop. (This is same as finding the nth element from the end of the link list.)

Working code here

public class LoopInLinkedList {

    static class Node {
        public String info;
        public Node next;
        @Override
        public String toString() {
            return "Node [info=" + info + ", next=" + next.hashCode() + "]";
        }
    }
    public static void main(String[] args) throws Exception {

        Node n1 = new Node();
        n1.info = "A";
        Node n2 = new Node();
        n2.info = "B";
        Node n3 = new Node();
        n3.info = "C";
        Node n4 = new Node();
        n4.info = "D";
        Node n5 = new Node();
        n5.info = "E";
        Node n6 = new Node();
        n6.info = "F";
        Node n7 = new Node();
        n7.info = "G";
        Node n8 = new Node();
        n8.info = "H";

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        n7.next = n8;
        n8.next = n2;

        detectLoop(n1);
    }
    public static boolean detectLoop(Node start) throws Exception {
        Node slow = start;
        Node fast = start;
        while (slow !=null && fast != null) {
            slow=slow.next;
            fast=fast.next.next;
            if (fast == slow) {
                int k = getLengthOfLoop(fast);
                Node startOfLoopNode = detectLoopStart(start, k);
                System.out.println("Length of the loop is " + k);
                System.out.println("Start of the loop is " + startOfLoopNode);
                return true;
            }
        }
        return false;
    }
    private static int getLengthOfLoop(Node loopNode) throws Exception {
        Node ptr = loopNode;
        int k=0;
        while ((ptr=ptr.next)!=loopNode) {
            k++;
        }
        return k+1;
    }
    private static Node detectLoopStart(Node start, int k) throws Exception {
        Node ptr1 = start;
        Node ptr2 = start;
        while (k-->0 && (ptr1 = ptr1.next)!=null);
        while ((ptr1=ptr1.next)!=null && (ptr2=ptr2.next)!=null && ptr1 != ptr2);
        return ptr1;
    }
}

Getting the sum of all multiples of 3 and 5 before a number n

Hello all, today we are going to look on to a problem that says the total of all the multiples of 3 and 5 before a number n.

Note: Before n

So  if I say take the sum of all numbers before 10 which are the multiples of 3 and 5 then the answer would be: 3,5,6,9 and the answer would be 23 (3+5+6+9).

Before going to the implementation lets go back and make some points:
  1. The multiples of 3 and to make a sum of them would be:
    • 3 + 6 + 9 + 12 + 15 ...... which cuts down to : 3 * (1 + 2 + 3 + 4 + 5 ......). Now if you look at this series it is an Arithmetic Progression or you can say that it is the sum of n natural numbers, multiplied by 3.
    • Now the second part which is quite important to notice is that if I say that you have to add all the multiples of  3 before 10 (excluding 10) then then total numbers to be added is 3 * (1 + 2 + 3), which means that the n-1(since we don't have to include n)(for us ,10-1, 9) is divided by 3 and then we consider it to be the part where we can say that apply the formula of addition of first n natural numbers multiplied by 3.
    • So in total the formula would be 3 * (sum of first (n-1)/3 natural numbers), this part is a bit tricky so please give more attention to it.
  2. Same will be the case of numbers divisible by 5 as well.
  3. One more important thing is that if the n is 16 and we have to add all the multiples of 3 and 5 together then the answer would be:
    (3 + 6 + 9 + 12 +15) + (5 + 10 + 15)
    if you notice the expression the digit 15 is added twice since, 3 & 5 both are the multiples of 15 and so added twice.
  4. Now in order to do correct solution we have to remove the digits those are the multiple of 15(i.e 3*5)
  5. So the case would be like this:
        3 * (sum of first (n-1)/3 natural numbers)
    5 * (sum of first (n-1)/5 natural numbers)
    15 * (sum of first (n-1)/15 natural numbers)
Now lets prepare the code :

public class Solution {
    public static Scanner ins = new Scanner(System.in);
    public static sumOfNNaturalNumbers(int n) {
        return (n*(n+1)/2);
    }
    public static int readInt() {
        int result = ins.nextInt();
        ins.nextLine();
        return result;
    }
    public static int readString() {
        return ins.readLine();
    }
    public static void main(String[] args) {
        int n = readInt();
        int answer = 3 * (n-1)/3 + 5 * (n-1)/5 - 15 * (n-1)/15;
        System.out.println(answer);
    }
}

Friday, July 24, 2015

Getting different objects from Jackson

Hello All, today I want to explain you a special case when we want to get different objects from Jackson Library.

What is Jackson API and how it works?
     It is a standard JSON library for Java (or JVM platform in general), or, as the "best JSON parser for Java". Or simply as "JSON for Java". It is very useful and flexiblt in nature. It takes JSON string in to consideration and changes it to Java object or vice versa.

What is a JSON string?
    JSON is a special format of representing the data in a string format, you can think it as a refined version of XML.

Eg:
    In XML:
        <user>
            <author>Ankur</author>
            <name>Codepool</name>
         </user>
    In JSON:
        user:{
                "author" : "Ankur",
                "name" : "Codepool",
        }
     

Now before going further lets us take a basic example of how Jackson works to and forth?

User.java
public class User {
    private String name;
    private String author;

    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public String getAuthor() {
        return author;
    }
    public void setAuthor(String author) {
        this.author = author;
    }
    @Override
    public String toString() {
        return "User [name=" + name + ", author=" + author + "]";
    }
}

ExampleJackson.java
public class ExampleJackson {
    public static void main(String[] args) throws Exception {
        User user = new User();
            user.setName("Ankur");
            user.setAuthor("Codepool");

        //Writing a Java object as a Json String
        ObjectMapper objectMapper = new ObjectMapper();
        System.out.println(objectMapper.writeValueAsString(user));
        //Output: {"name":"Ankur","author":"Codepool"}

        //Now reading from Json string to Java object
        String jsonString = "{\"name\":\"NewAnkur\", \"author\":\"NewAuthor\" }";
        User newUser = objectMapper.readValue(jsonString, User.class);
        System.out.println(newUser);
        //Output: User [name=NewAnkur, author=NewAuthor]
    }
}

Now let us take a case, where we want to get the object on the basis of data inside the JSON string, that means if the name value is Ankur, I want AnkurUser object and if name value is John, we want the JohnUser object.

For this type of functionality we have the annotations defined in Jackson library, those are :
  • @JsonTypeInfo
  • @JsonSubTypes
  • @JsonSubTypes.Type
Now lets edit the User class in a way like this:

User.java
@JsonTypeInfo(
    use = JsonTypeInfo.Id.NAME,
    include = JsonTypeInfo.As.PROPERTY,
    property = "name", // (A)
    visible = true  // (B)
)
@JsonSubTypes( {
    @JsonSubTypes.Type(name = "ankur", value = AnkurUser.class), //(C)
    @JsonSubTypes.Type(name = "john", value = JohnUser.class)  //(D)
})
abstract class User {
    private String name;
    private String author;
    protected abstract void show();

    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public String getAuthor() {
        return author;
    }
    public void setAuthor(String author) {
        this.author = author;
    }
    @Override
    public String toString() {
        return "User [name=" + name + ", author=" + author + "]";
    }
}

AnkurUser.java
class AnkurUser extends User{

 public AnkurUser(){
   System.out.println("Ankur Created");
  }
  @Override
 protected void show() {
  System.out.println("This is ankur user");
 }

 @Override
  public String toString() {
   return "AnkurUser [name=" + super.getName() + ", author=" + super.getAuthor() + "]";
  }
}

JohnUser.java
class JohnUser extends User {
    public AnkurUser() {
        System.out.println("Ankur Created");
    }
    @Override protected void show() {
        System.out.println("This is john user");
    }
    @Override
    public String toString() {
        return "JohnUser [name=" + super.getName() + ", author=" + super.getAuthor() + "]";
    }
}
Now lets see the usage and output:

ExampleJackson .java
public class ExampleJackson {
    public static void main(String[] args) throws Exception {
        ObjectMapper objectMapper = new ObjectMapper();

        //Now reading from Json string to Java object
        String jsonString = "{\"name\":\"ankur\", \"author\":\"NewAuthor\" }";
        User newUser = objectMapper.readValue(jsonString, User.class);
        newUser.show();
        /*
        * Output: (E)
        *  Ankur Created
        *  This is ankur user
        */
    }
}

If you notice the equation (C) tells you that the object that is created, is of AnkurUser class and returns you the same, this transition is because of the annotation configuration that we did at the creation of the User class, which says check for the property named name (equation (A)), and if its value is Ankur  create the AnkurUser object and so on, at equation (C) and (D). The equation (B) states that the field is also going to be visible for further calls  normally the field that is used as a deciding factor of the object, is never visible for further manipulations.

Thanks

Wednesday, July 15, 2015

Singleton pattern exposed

Today we are going to look in to one of the most common pattern used in Software Development. That is Singleton Pattern.

Before moving forward let me give you a brief description of what is a Design Pattern and how it is useful in one or more ways?

What is a design pattern?
          In software engineering, a design pattern is a general reusable solution to a commonly occurring problem within a given context in software design.- Wiki

Now the statement is quite clear that it is not a rocket science and it is just the way of solving a problem which is common in the market.

Ok, now when we understand the basic idea of the design patterns let us take a look on to its types or in other words categories.

Categories:
          There are 4 categories under which the design patterns are divided. These are as follows:
  1. Creational Patterns
  2. Structural Patterns
  3. Behavioral Patterns
  4. Concurrency Patterns
I will not go in the inside of these because it would be a totally new and big topic to discuss but just want to give you an idea that Singleton Pattern is one of these patterns and comes under Creational Pattern.

Now we got the info regarding the patterns and their categories. Let us now take the info regarding the Singleton pattern as a particular.

Singleton Pattern:
          In software engineering, the singleton pattern is a design pattern that restricts the instantiation of a class to one object. This is useful when exactly one object is needed to coordinate actions across the system.

Ok, so if you need an object to be instantiated once, per JVM per Application  we use singleton pattern to achieve this.


The above diagram shows a basic idea of how singleton works.

Now there are many ways of creating singleton objects. 
  1. Eager Initialization, without static block and so no exceptional handling.
  2. Eager Initialization, with static block and so with/without exception handling.
  3. Lazy initialization
  4. Thread safe initialization
Some of the points that we have to take care about are:
  1. Reflection can break the nature of Singleton object.
At last we will look in to the Enum style of creating the singleton.
  1. Enum Singleton
Lets see  each one of the above style 1 by 1.
  1. Eager Initialization, without static block and so no exceptional handling.
             
    It is pretty basic and easy to use.

    Example:
    public class  SingletonClass{
    public static final String singleton = "I am singleton";
    }

  2. This is very easy to use and also easy to understand but as you can see it is eager in nature which means we have to create the object beforehand that means the object is in memory even if we don't want to use it.

  3. Eager Initialization, with static block and so with/without exception handling.
             
    This way is same as the previous one as in this also we create the object beforehand but the only difference is that the object is created in a static block which gives us the opportunity to use exceptional handling if we want to.

    Example:
    public class  SingletonClass{
    public static String singleton;
    static{
    try{singleton = "I am singleton";}
    catch(Exception ex){System.out.println("You can handle exception here");}
    }
    }

    This is great when we know the creating the object beforehand not make any big impact on the system but in real world scenario mostly the database connection template(in case of Spring) and hibernate template are used in a singleton manner which are very heavy objects in nature and so creating them beforehand is not a good way.

  4. Lazy initialization.
             
    This is useful to make sure that the object is created only when it is needed by any class in a JVM per application

    Example:
    public class SingletonClass {
    private static SingletonClass instance;
    private SingletonClass(){} // (3.A)
    public static SingletonClass getInstance(){
    if(instance == null){ // (3.B)
    instance = new SingletonClass();
    }
    return instance;
        }
    }

    If you look on to this example at equation (3.A) you find that we have made the constructor private in nature thus restricting the creation of the object for the class, also in equation (3.B) we have checked for nullness of the object which makes sure that only one object is created for this class.

  5. Thread safe initialization.
             
    Thread safe initialization is very important for a singleton pattern to work correctly. If you look on to equation (3.B) you will find out that this is the place that will make the things messy as it may be the chance that 2 threads of  the application enters this code and tries to create to different objects of the instance which in turn breaks the overall meaning of the pattern. Now in order to achieve thread safe initialization we have 2 modes:
    • Either go for synchronization block
    • Either go for double check

      Synchronization Block:
                
      public class SingletonClass {
      private static SingletonClass instance;
      private SingletonClass(){} // (4.A)
      public static synchronized SingletonClass getInstance(){//(4.B)
      if(instance == null){ // (4.C)
      instance = new SingletonClass();
      }
      return instance;
          }
      }

      If you look at equation 4.B, the synchronized keyword makes sure that only 1 thread has the access to this function and will create only 1 instance of the instance but the problem here is the efficiency, as if you see the overall speed of the check will be affected greatly since only 1 thread has the access to the function.

      Double Check:     
      public static Singleton getInstance(){//(4.D)
          if(instance == null){
              synchronized (Singleton.class) {//(4.E)
                  if(instance == null){
                      instance = new Singleton();
                  }
              }
          }
          return instance;
      }

      In this example equation 4.D makes sure that multiple threads can access the function and thus not affecting the efficiency and equation 4.E will place the lock on the block and recheck of the condition, this is good to achieve the thread safe creation of  the object but it is still the overhead.
Using reflection to break singleton pattern from above styles.
          The reflection is an API provided by Java that gives you the functionality to manipulate the objects in the run time. Reflection is commonly used by programs which require the ability to examine or modify the run time behavior of applications running in the Java virtual machine.

Here I am presenting the code example that can break the functionality of the Singleton pattern and thus ruins everything of singleton pattern.

Example

class Singleton {
public static final Singleton INSTANCE = new Singleton();
}
public class EnumSingletonTest{
public static void main(String[] args) {
Singleton ins1 = Singleton.INSTANCE;
Singleton ins2 = null;
try{
Constructor[] constructors = Singleton.class.getDeclaredConstructors();
for (Constructor constructor : constructors) {
                                //Below code will destroy the singleton pattern
                                constructor.setAccessible(true);
                                ins2 = (Singleton) constructor.newInstance();
                                break;
                        }
        System.out.println(ins1.hashCode());
        System.out.println(ins2.hashCode());
}catch(Exception ex){
System.out.println("Hello");
}
}
}
Output:
360637413
1034148457

The output clearly showing that both the objects are different and unique and not the same which is the promise of the singleton pattern.

Now lets look on to the Enum style of creating the singleton objects:
  1. Enum Singleton.
              
    This is something that I have created the page. This is the best way of creating the singleton object and also not worrying about the  thread safe creation and eager creation. The enum singleton pattern is by default thread safe in nature and is also easy to use.


    Example:
    enum EnumSingleton {
    INSTANCE;
    private final String var1;
    private EnumSingleton(){
    var1 = "I am initialised now you can use me";
    System.out.println("I am private constructor");
    }
    public String getVar1() {
    return var1;
    }
    }
    public class EnumSingletonTest{
    public static void main(String[] args) {
    System.out.println(EnumSingleton.INSTANCE.getVar1());
    }
    }

    One more point to be noted that Enum singleton also restricts creation of new object by the use of Reflections. If we tries to use it, the program throws an Exception.java.lang.IllegalArgumentException: Cannot reflectively create enum objects