Monday, 6 October 2014

Java Enum and its different uses

Enums :-

  • are set of constants.
  • special type of class that extends java.lang.Enum
  • implements Comparable and Serializable, and singleton by default. Hence, we can compare  enum with == operator.
  • enforce compile time error check.

Simple implementation of enum

public enum Status {
ACT,
PEN,
ARC,
DAC
}

Here ACT, PEN, ARC, DAC all are constant for enum Status.


Enum with values 

We can provide value to enum at the time their creation, for this we need a private constructor and a private member variable.

public enum Status {
ACT("ACTIVE"),
PEN("PENDING"),
ARC("ARCHIVE"),
DAC("DEACTIVE");

private String value;
private Status(String value){
this.value = value;
}
public String getValue() {
return value;
}
}

usage:- Status.ACT.getValue();

Enum with abstract method

public enum Status {
ACT{
public String getDescription()
{
return "ACTIVE";
}
},
PEN{
public String getDescription()
{
return "PENDING";
}
},
ARC{
public String getDescription(){
return "ARCHIVE";
}
},
DAC{
public String getDescription(){
return "DEACTIVE";
}
};
public abstract String getDescription();
}

usage:- Status.ACT.getDescription();


Printing entire Enum 

for(Status s : Status.values()){
System.out.println((s.name()));
}


Handling IllegalArgumentException with Enum

Enum can throw illegalArguementException when we try to get value of anything which is not a part of enum set using valueOf().
This feature can be used to determine whether a particular value is a part of  enum set or not.
See below implementation.

public enum Status {
ACT,
PEN,
ARC,
DAC
}

public class ValidateStatus{

static String checkValidStatus(String status){
try{
Status.valueOf(status);
}
catch(IllegalArgumentException e){
return "Not a valid status";
}
return "valid status";
}
public static void main(String[] args) {

System.out.println(checkValidStatus("ACT"));
System.out.println(checkValidStatus("DEC"));
}

}

output:-
valid status
Not a valid status



Sunday, 5 October 2014

Different ways of iterating Map and their performance

There are 4 ways using which we can iterate through a map. These 4 ways are based on entrySet() and keySet().
Any collection can be iterated using for each loop and iterator. For map also, iteration is done using these two techniques.

Method 1: keySet() with for each loop.
Method 2: keySet() with iterator().
Method 3: entrySet() with for each loop.
Method 4: entrySet() with iterator().

Let us see each method one by one and their cost of performance :

Create a map for 100000 objects.

Map<Integer,String> map = new HashMap<Integer,String>();
for(int i = 0; i<100000;i++)
{
     map.put(i,"object"+i);
}

Now we have created a map for 100000 objects, let iterate this map using each method one by one.

Method 1 : keySet() with for each loop

   long start = System.currentTimeMillis();
Set<Integer> keySet = map.keySet();
for(Integer key : keySet)
  {
String value = map.get(key);
}
long end = System.currentTimeMillis();
System.out.println("Method 1 takes "+(end-start)+" milliseconds");


Method 2: keySet() with iterator()

long start = System.currentTimeMillis();
Set<Integer> keySet = map.keySet();
Iterator<Integer> iterator = keySet.iterator();
while(iterator.hasNext())
{
Integer key = iterator.next();
String value = map.get(key);
}
long end = System.currentTimeMillis();

System.out.println("Method 2 takes "+(end-start)+" milliseconds");


Method 3: entrySet() with for each loop

long start = System.currentTimeMillis();
Set<Map.Entry<Integer, String>> entrySet = map.entrySet();
for(Map.Entry entry : entrySet)
{
Integer key = entry.getKey();
String value = entry.getValue();
}
long end = System.currentTimeMillis();

System.out.println("Method 3 takes "+(end-start)+" milliseconds");


Method 4: entrySet() with iterator()

long start = System.currentTimeMillis();
Set<Map.Entry<Integer, String>> entrySet = map.entrySet();
Iterator<Map.Entry<Integer, String>> iterator = entrySet.iterator();
while(iterator.hasNext())
{
Map.Entry entry = iterator.next();
Integer key = entry.getKey();
String value = entry.getValue();
}
long end = System.currentTimeMillis();

System.out.println("Method 4 takes "+(end-start)+" milliseconds");

Output:-
Method 1 takes 109 milliseconds
Method 2 takes 168 milliseconds
Method 3 takes 63 milliseconds
Method 4 takes 68 milliseconds

From this observation, it is clear that entrySet() is faster than keySet(). So Method 1 and Method 2 are ruled out from the race.

Now to decide which to be used between Method 3 and method 4, we need to see our requirements.
If we want to modify the content of map during its iteration, then go for iterator(), because any attempt made to modify the content of map during its iteration using for each loop, will result in java.util.ConcurrentModificationException.

Set<Map.Entry<Integer, String>> entrySet = map.entrySet();
for(Map.Entry entry : entrySet)
{
map.remove(entry.getKey());  // throws run time exception here.
String value = entry.getValue();
}
long end = System.currentTimeMillis();



Using iterator(), one can modify the content of map during its iteration.

Set<Map.Entry<Integer, String>> entrySet = map.entrySet();
Iterator<Map.Entry<Integer, String>> iterator = entrySet.iterator();
while(iterator.hasNext())
{
Map.Entry entry = iterator.next();
iterator.remove();    //valid here
}

Monday, 16 December 2013

Gold Mine Problem :

Rectangular grid of gold mine is given with R rows and C columns. Grid has R x C cells in it.
Each Cell is denoted by an integer , which is the count of gold content in that cell.

Sub rectangle is defined by four integers x1,y1,x2,y2 ,
where 1<=x1<=x2<=R and 1<=y1<=y2<=C.

Aim is to find the total gold in that given sub rectangle.

For Example:

Input Matrix is      
                             2 3 4 5
                             1 7 3 1
                             8 9 4 6
                             7 3 5 6

and  x1=1 , y1=1 , x2= 2 , y2 = 4  (yellow shaded region is the sub rectangle formed by these points).

Then , output should be sum of 2+3+4+5+1+7+3+1 = 26.

Algorithm:-

1. Input : array and two co-ordinates of rectangle say x1,y1 and x2,y2.
2. for i from x1-1 to x2-1 do
3. for j from y1-1 to y2-1 do
4. sum = sum+array[i][j]


Complexity:- O(n2)


Java implementation of algorithm

package problem.goldmine;

import java.util.Scanner;

public class GoldMine {

    public static void main(String[] args) {
       
        System.out.println("Enter row (M): ");  //Input rows
        Scanner scan = new Scanner(System.in);
        int row = Integer.parseInt(scan.nextLine());
       
        System.out.println("Enter column (N): ");  //Input columns
        Scanner scan1 = new Scanner(System.in);
        int column = Integer.parseInt(scan1.nextLine());
       
        int array[][] = new int[row][column];
       
        for(int r=0;r<row;r++){                       // Input binary matrix
            System.out.println("Enter row "+(r+1));
            for(int c=0;c<column;c++){
                Scanner scan2 = new Scanner(System.in);
                array[r][c]=Integer.parseInt(scan2.nextLine());
            }
        }
       
        System.out.println("Enter x1 : "); 
        Scanner scanx1 = new Scanner(System.in);
        int x1 = Integer.parseInt(scanx1.nextLine());
       
        System.out.println("Enter y1 : "); 
        Scanner scany1 = new Scanner(System.in);
        int y1 = Integer.parseInt(scany1.nextLine());
       
        System.out.println("Enter x2 : "); 
        Scanner scanx2 = new Scanner(System.in);
        int x2 = Integer.parseInt(scanx2.nextLine());
       
        System.out.println("Enter y2 : "); 
        Scanner scany2 = new Scanner(System.in);
        int y2 = Integer.parseInt(scany2.nextLine());
       
        System.out.println();
        display(array,row,column);
        System.out.println();
       
        int sum = 0;
        long startTime = System.currentTimeMillis();
        for(int i=x1-1;i<x2;i++){
            for(int j=y1-1;j<y2;j++){
                sum = sum + array[i][j];
            }
        }
        System.out.println("sum of gold mine in rectangle  formed by ("+x1+","+y1+") and ("+x2+","+y2+") ="+sum);
       
        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println("Time Taken= "+(double)elapsedTime/1000+" sec");
       
       

    }
   
    static void display(int[][] array,int row,int column) {         //function to display matrix
        for(int r=0;r<row;r++){
            System.out.println();
            for(int c=0;c<column;c++){
                System.out.print(array[r][c]);
            }
        }
       
    }

}


Output:-

Enter row (M):
4
Enter column (N):
4
Enter row 1
2
8
9
7
Enter row 2
5
8
1
7
Enter row 3
5
7
3
5
Enter row 4
4
8
7
4
Enter x1 :
1
Enter y1 :
4
Enter x2 :
2
Enter y2 :
4


2897
5817
5735
4874
sum of gold mine in rectangle  formed by (1,4) and (2,4) =14
Time Taken= 0.0 sec




Sunday, 15 December 2013

Matrix Game : Flip The World

Composition and Dimension of Matrix

There is an binary matrix of dimension M x N.
Binary Matrix : Matrix with entries from the Boolean domain B = {0, 1}

Make a move

1. Select any two integer , say x and y such that 1<=x<=M and 1<=y<=N .
2. All the elements in the rectangle or square formed by (1,1) and (x,y) are to be toggled ,i.e. 0 is made 1 and
    1 is made 0.
                                 (1,1) . . . . . . . . . . . . . .
                                    .                .
                                    .                .
                                    .                .
                                    .............(x,y)

 Note : (1,1) is always taken as one of the two co-ordinates.

For Example : Given a  matrix 4 x 4 (M=4, N=4)

                          1 0 1 0
                          1 1 0 0
                          1 0 0 1
                          1 1 1 0

If we choose x=2 and y=3, then new matrix after toggle will be :

                          0 1 0 0
                          0 0 1 0
                          1 0 0 1
                          1 1 1 0


Aim of the Game

Sole aim of the game is to change all elements of the matrix to 1.
This requires some number of moves to be made in order to get the all-ones matrix out of binary matrix.

Calculating number of steps required

Algorithm:-

1.  Input : row , column and array element .
2.  for i from row-1 to 0 do
3.  for j from column-1 to 0 do
4.  if  array[row][column]==0 then
5.  Toggle the matrix
6.  increment the counter
7. Output : all-ones matrix  and number of moves


Complexity : O(n2)


Java Implementation of the algorithm



import java.util.Scanner;

public class FlipTheWorld {


    public static void main(String[] args) {
       
        System.out.println("Enter row (M): ");  //Input rows
        Scanner scan = new Scanner(System.in);
        int row = Integer.parseInt(scan.nextLine());
       
        System.out.println("Enter column (N): ");  //Input columns
        Scanner scan1 = new Scanner(System.in);
        int column = Integer.parseInt(scan1.nextLine());
       
        int array[][] = new int[row][column];
        int count = 0;
        for(int r=0;r<row;r++){                       // Input binary matrix
            System.out.println("Enter row "+(r+1));
            for(int c=0;c<column;c++){
                Scanner scan2 = new Scanner(System.in);
                array[r][c]=Integer.parseInt(scan2.nextLine());
            }
        }
        System.out.println("Original : ");
        display(array,row,column);
        for(int r=row-1;r>=0;r--){                                
            for(int c=column-1;c>=0;c--){
                if(array[r][c]==0){
                    toggle(array,r,c);
                    count = count+1;
                    System.out.println();
                    System.out.println("Matrix after toggle "+count);
                    display(array,row,column);
                }
                   
            }
        }
        int sum = 0;                                        
        for(int i=0;i<row;i++){                            //Checking if resultant matrix is all-ones or not
            for(int j=0;j<column;j++){                     //for this to check , compare the sum of elements
                                                           // of resultant matrix with the product of row and column.
        sum = sum + array[i][j];
            }
        }
        if(sum==row*column){
        System.out.println();
        System.out.println();
        System.out.println("Final : ");
        display(array,row,column);
        System.out.println();
        System.out.println("Number of steps : "+count);
            }
        else{
            System.out.println("Failure of algo");
        }

    }
   
    static void display(int[][] array,int row,int column) {         //function to display matrix
        for(int r=0;r<row;r++){
            System.out.println();
            for(int c=0;c<column;c++){
                System.out.print(array[r][c]);
            }
        }
       
    }

    static void toggle(int array[][],int row,int column){          //function to toggle the matrix
        for(int r=0;r<=row;r++){
            for(int c=0;c<=column;c++){
                if(array[r][c]==1)
                    array[r][c]=0;
                else
                    array[r][c]=1;
            }
        }
    }

}









Output :

Original :

1010
1100
1001
1110
Matrix after toggle 1

0101
0011
0110
0001

Matrix after toggle 2

1011
1101
1000
1111

Matrix after toggle 3

0100
0010
0111
1111

Matrix after toggle 4

1100
1010
1111
1111

Matrix after toggle 5

0011
0101
1111
1111

Matrix after toggle 6

1101
1011
1111
1111

Matrix after toggle 7

0001
0111
1111
1111

Matrix after toggle 8

1001
1111
1111
1111

Matrix after toggle 9

0111
1111
1111
1111

Matrix after toggle 10

1111
1111
1111
1111

Final :

1111
1111
1111
1111

Number of steps : 10
Time Taken= 0.011 sec
Palindrome Count  : All possible substring palindromes inside a string

A string is said to be palindrome, if the reverse of the string is same as itself.
A sub string is any continuous sequence of characters in the string.

Given a string S, finding all non empty sub strings that are palindromes.

For Example:

For Input string , S =abcba

Output should be all possible substring palindromes :

Palindrome 1 : a
Palindrome 2 : abcba
Palindrome 3 : b
Palindrome 4: bcb
Palindrome 5 : c
Palindrome 6 : b
Palindrome 7 : a



Algorithm:

1.  Input : a string str.
2.  for i from 0 to str.length-1  do
3.  for j from i+1 to str.length  do
4.  result = str.substring(i,j)
5. check if result is palindrome  then
6. increment counter


Complexity:  O(n3)


Java implementation of the algorithm:


import java.util.Scanner;

public class PalindromeCount {


    public static void main(String[] args) {
   
        System.out.println("Enter the string : ");
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        long startTime = System.currentTimeMillis();   
        int count = substr(str);
        System.out.println("Number of palindromes = "+count);
            long stopTime = System.currentTimeMillis();
            long elapsedTime = stopTime - startTime;
            System.out.println("Time Taken= "+(double)elapsedTime/1000+" sec");
    }
   
   

    private static int substr(String str) {
        int len = str.length();
        int count = 0;
        String result = "";
        for(int i = 0;i<len;i++){
            for(int j = i+1;j<=len;j++){
            result = str.substring(i,j);
            if(isPalindrome(result)){
                count = count + 1;
                System.out.println("Palindrome("+i+","+j+") "+(count)+" : "+result);
               
            }
            }
        }
        return count;
    }



    static boolean isPalindrome(String str){
        int len = str.length();
        boolean flag = false;
        String reverse = "";
        for(int i=len-1;i>=0;i--){
            reverse = reverse+str.charAt(i);
        }
        if(str.equals(reverse))
        flag = true;
        return flag;
    }
}


Output:

Enter the string : abcba
Palindrome(0,1) 1 : a
Palindrome(0,5) 2 : abcba
Palindrome(1,2) 3 : b
Palindrome(1,4) 4 : bcb
Palindrome(2,3) 5 : c
Palindrome(3,4) 6 : b
Palindrome(4,5) 7 : a
Number of palindromes = 7
Time Taken= 0.002 sec