Print all possible paths from top left to bottom right of a mXn matrix

Question : 

The problem is to print all the possible paths from top left to bottom right of a mXn matrix with the constraints that from each cell you can either move only to right or down.(GeeksForGeeks)

Idea :

The algorithm is a simple recursive algorithm, from each cell first print all paths by going down and then print all paths by going right. Do this recursively for each cell encountered.

Solution :

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 30/1/14
 * Time: 4:39 PM
 * To change this template use File | Settings | File Templates.
 */
public class AllPathsPrinter {

    int [][] array;
    int rowCount;
    int colCount;


    public AllPathsPrinter(int [][]array){

        this.array = array;
        rowCount = array.length;
        colCount = array[0].length;

    }


    public void printAllPaths(int currX, int currY, String path){

        if(currX == rowCount-1){
            for(int j=currY;j<=colCount-1;j++){
                path = path + array[currX][j];
            }
            System.out.println("Path : " + path);
            return;
        }

        if(currY == colCount-1){
            for(int i=currX;i<=rowCount-1;i++){
                path = path + array[i][currY];
            }
            System.out.println("Path : " + path);
            return;
        }
        path = path + array[currX][currY];
        printAllPaths(currX+1, currY, path);
        printAllPaths(currX, currY+1, path);

    }

    public static void main(String args[]){

        int [][] ar = new int[][]{{1, 2, 3}, {4, 5, 6}};
        AllPathsPrinter allPathsPrinter = new AllPathsPrinter(ar);
        allPathsPrinter.printAllPaths(0,0,"");


    }


}

Output :

Path : 1456
Path : 1256
Path : 1236

Convert a given Binary Tree to Doubly Linked List

Question:

Given a Binary Tree (Bt), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in BT) must be head node of the DLL.(Taken from GeeksForGeeks)

The idea behind its solution is quite simple and straight.

1.  If left subtree exists, process the left subtree
1. Recursively convert the left subtree to DLL.
2. Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).
3. Make inorder predecessor as previous of root and root as next of inorder predecessor.
2. If right subtree exists, process the right subtree (Below 3 steps are similar to left subtree).
1. Recursively convert the right subtree to DLL.
2. Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).
3. Make inorder successor as next of root and root as previous of inorder successor.
3. Find the leftmost node and return it (the leftmost node is always head of converted DLL).

 Solution :

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 29/1/14
 * Time: 5:43 PM
 */
public class BTreeToList {

    private static TreeNode btreeToListUtil(TreeNode root){

        if( root == null) {
            return null;
        }

        if(root.getLeftNode() != null){

            TreeNode leftTreeNode = btreeToListUtil(root.getLeftNode());

            while(leftTreeNode.getRightNode() != null){
                leftTreeNode = leftTreeNode.getRightNode();
            }

            leftTreeNode.setRightNode(root);
            root.setLeftNode(leftTreeNode);

        }


        if(root.getRightNode() != null){

            TreeNode rightTreeNode = btreeToListUtil(root.getRightNode());

            while(rightTreeNode.getLeftNode() != null){
                rightTreeNode = rightTreeNode.getLeftNode();
            }

            rightTreeNode.setLeftNode(root);
            root.setRightNode(rightTreeNode);
        }

        return root;

    }

    public static TreeNode btreeToList(TreeNode root){
         TreeNode head = btreeToListUtil(root);
        while(head.getLeftNode() != null){
            head = head.getLeftNode();
        }

        return head;
    }

    public static void printLL(TreeNode root){

        while(root != null){
            System.out.println("Data : " + root.getData());
            root = root.getRightNode();
        }


    }



    public static void main(String args[]){

        TreeNode root = new TreeNode(10);

        TreeNode l = new TreeNode(12);
        TreeNode r = new TreeNode(15);

        TreeNode ll = new TreeNode(25);
        TreeNode lr = new TreeNode(30);

        TreeNode rl = new TreeNode(36);

        root.setLeftNode(l);
        root.setRightNode(r);

        l.setLeftNode(ll);
        l.setRightNode(lr);

        r.setLeftNode(rl);

        printLL(btreeToList(root));

    }

}

Output :

Data : 25
Data : 12
Data : 30
Data : 10
Data : 36
Data : 15

Program to rotate a matrix by 90 degree clockwise.

Question :

You have to rotate the matrix by 90 degrees.

For example if you have

[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]

output must be

[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4] 

Solution : 

 package Matrices;

import java.util.Arrays;

/**
 * Created by Aniket on 1/26/14.
 */
public class NinetyDegRotator {

    public static int [][] rotate(int [][] matrix){
        int rows = matrix.length;
        int cols = matrix[0].length;
        int [][] rotatedMatrix = new int[rows][cols];
        for(int i =0; i<rows;i++){
            for(int j=0;j<cols;j++){
                rotatedMatrix[i][j] = matrix[cols-j-1][i];
            }
        }
        return rotatedMatrix;
    }

    public static void twoDArrayPrinter(int [][] matrix){

        for(int []array : matrix){
            System.out.println(Arrays.toString(array));
        }

    }

    public static void main(String args[]){

        int [][] matrix = new int[][]{
                {1,2,3,4},
                {5,6,7,8},
                {9,0,1,2},
                {3,4,5,6}
        };

        System.out.println("Original Array : ");
        NinetyDegRotator.twoDArrayPrinter(matrix);
        int [][] rotatedMatrix = ninetyDegRotator.rotate(matrix);
        System.out.println("Rotated Array : ");
        NinetyDegRotator.twoDArrayPrinter(rotatedMatrix);
    }

}

Output :

Original Array :
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 0, 1, 2]
[3, 4, 5, 6]
Rotated Array :
[3, 9, 5, 1]
[4, 0, 6, 2]
[5, 1, 7, 3]
[6, 2, 8, 4]

Note : Above algorithm takes O(N^2) time complexity.

 To make the transformation in place it has to be a square matrix(n*n)

Code :

package Matrices;

/**
 * Created by Aniket on 1/26/14.
 */
public class TransposeCreator {
    public static void inPlaceTranspose(int [][] matrix){

        int rows = matrix.length;
        int cols = matrix[0].length;

        for(int i=0;i<rows;i++){
            for(int j=i+1;j<cols;j++){
                matrix[i][j] = matrix[i][j] + matrix[j][i];
                matrix[j][i] = matrix[i][j] - matrix[j][i];
                matrix[i][j] = matrix[i][j] - matrix[j][i];
            }
        }
    }

    public static int[][] transpose(int[][] matrix){

        int rows = matrix.length;
        int cols = matrix[0].length;

        int[][] transposedMatrix = new int[cols][rows];

        for(int i=0;i<cols;i++){
            for(int j=0;j<rows;j++){
                transposedMatrix[i][j] = matrix[j][i];
            }
        }

        return transposedMatrix;

    }

    public static void inPlaceRowsSwapper(int [][] matrix){
        int rows = matrix.length;
        int cols = matrix[0].length;

        for(int i=0;i<rows;i++){
            for(int j=0;j<cols/2;j++){
                matrix[i][j] = matrix[i][j] + matrix[i][cols-j-1];
                matrix[i][cols-j-1] = matrix[i][j] - matrix[i][cols-j-1];
                matrix[i][j] = matrix[i][j] - matrix[i][cols-j-1];
            }
        }

    }


    public static void main(String args[]){

        int [][] matrix = new int[][]{
                {1,2,3,4},
                {5,6,7,8},
                {9,0,1,2},
                {3,4,5,6}
        };

        System.out.println("Original Array : ");
        NinetyDegRotator.twoDArrayPrinter(matrix);
        System.out.println("Transposed Matrix");
        NinetyDegRotator.twoDArrayPrinter(TransposeCreator.transpose(matrix));
        TransposeCreator.inPlaceTranspose(matrix);
        System.out.println("InPlace Transposed matrix");
        NinetyDegRotator.twoDArrayPrinter(matrix);
        System.out.println("90deg rotation matrix");
        TransposeCreator.inPlaceRowsSwapper(matrix);
        NinetyDegRotator.twoDArrayPrinter(matrix);

    }
}

Output :

Original Array :
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 0, 1, 2]
[3, 4, 5, 6]
Transposed Matrix
[1, 5, 9, 3]
[2, 6, 0, 4]
[3, 7, 1, 5]
[4, 8, 2, 6]
InPlace Transposed matrix
[1, 5, 9, 3]
[2, 6, 0, 4]
[3, 7, 1, 5]
[4, 8, 2, 6]
90deg rotation matrix
[3, 9, 5, 1]
[4, 0, 6, 2]
[5, 1, 7, 3]
[6, 2, 8, 4]

Sum of all the numbers that are formed from root to leaf paths.

Question :

Given a binary tree, where every node value is a Digit from 1-9 .Find the sum of all the numbers which are formed from root to leaf paths.
For example consider the following Binary Tree.

 Solution :

The idea is to do a preorder traversal of the tree. In the preorder traversal, keep track of the value calculated till the current node, let this value be val. For every node, we update the val as val*10 plus node’s data.

Answer is : 632 + 6357 + 6354 + 654 = 13997

 Code :

package Tree;

/**
 * Created by Aniket on 1/24/14.
 */
public class TreePathSummer {

    public static int treePathSum(TreeNode root, int val){

        if(root == null){
            return 0;
        }

        val = val * 10 + root.getData();

        if(root.getLeftNode() == null && root.getRightNode() == null){
            return val;
        }

        return treePathSum(root.getLeftNode(),val) + treePathSum(root.getRightNode(),val);

    }

    public static void main(String args[]){
        TreeNode rooTreeNode = new TreeNode(6);

        TreeNode l = new TreeNode(3);
        TreeNode r = new TreeNode(5);

        TreeNode ll = new TreeNode(2);
        TreeNode lr = new TreeNode(5);

        TreeNode lrl = new TreeNode(7);
        TreeNode lrr = new TreeNode(4);

        TreeNode rr = new TreeNode(4);

        rooTreeNode.setLeftNode(l);
        rooTreeNode.setRightNode(r);

        l.setLeftNode(ll);
        l.setRightNode(lr);

        lr.setLeftNode(lrl);
        lr.setRightNode(lrr);

        r.setRightNode(rr);

        System.out.println("Answer is = " + TreePathSummer.treePathSum(rooTreeNode,0));
    }
}

And the output is as expected

Answer is = 13997

For the java code corresponding to TreeNode data structure refer to the earlier post.

Converting Array to a balanced BST(Binary Search Tree)

Question : 

Given an array you need to convert it into an balanced BST(Binary Search Tree).

Example :

Solution :

Given an array first step would be to sort it. You can probably use quick sort which will take average time O(NlogN) complexity. Once you have sorted you can apply following algorithm to convert it into a balance BST.

1. Get the Middle of the array and make it root.
2. Recursively do same for left half and right half.
   
   1. Get the middle of left half and make it left child of the root created in step 1.
   2. Get the middle of right half and make it right child of the root created in step 1.

TreeNode data structure

package Tree;

/**
 * Created by Aniket on 1/22/14.
 */
public class TreeNode {

    int data;
    TreeNode leftNode;
    TreeNode rightNode;

    public TreeNode(int data){
        this.data = data;
    }

    public TreeNode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }

    public TreeNode getRightNode() {
        return rightNode;
    }

    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }
}

 Code to transform a sorted array into balance BST.

package Tree;

import java.util.Arrays;

/**
 * Created by Aniket on 1/22/14.
 */
public class ArrayToBST {

    public static TreeNode convert(int[] ar, int start, int end){

        if(start > end)
            return null;

        int mid = start + ((end - start)/2);
        TreeNode root = new TreeNode(ar[mid]);
        root.setLeftNode(convert(ar,start,mid-1));
        root.setRightNode(convert(ar,mid+1,end));

        return root;

    }

    public static void main(String args[]){

        int array[] = new int[]{1,2,3,4,5,6,7};
        System.out.println("Array is : " + Arrays.toString(array));


        System.out.println("BST in pre order : ");
        PrintTree.printPreOrderTraversal(ArrayToBST.convert(array,0,array.length-1));

    }

}

and the output is

Array is : [1, 2, 3, 4, 5, 6, 7]
BST in pre order :
Data : 4
Data : 2
Data : 1
Data : 3
Data : 6
Data : 5
Data : 7


Pre-order traversal is a type of tree traversals. You can take a look at the types and code for each in the previous post on Tree traversal.

Building Java projects with Maven.

In last post we saw what is maven and how do we install it. Now lets create a java project and use maven to build and then  test by running it.

What you will need?

1. Maven installed
2. JDK(6 or higher)
3. IDE(Eclipse/Intellij IDEA) or a text editor(gedit/vim)

Setting up the project

Projects that are to be built by maven must follow a particular directory pattern. For detailed directory structure you can visit their documentation on directory structure.

For our example we are going to create a HelloWorld sample inside a package called hello.

So our directory structure will be something like

So go ahead and create such structure. You can use following command

mkdir -p src/main/java/hello

Now inside hello directory create two java files - HelloWorld.java  and Greeter.java.

Code for them is provided below. For src/main/java/hello/HelloWorld.java

package hello;

public class HelloWorld {
    public static void main(String[] args) {
        Greeter greeter = new Greeter();
        System.out.println(greeter.sayHello());
    }
}

and for src/main/java/hello/Greeter.java

package hello;

public class Greeter {
    public String sayHello() {
        return "Hello world!";
    }
}

Now that Maven is installed, you need to create a Maven project definition. Maven projects are defined with an XML file named pom.xml. Among other things, this file gives the project’s name, version, and dependencies that it has on external libraries.

Note :  This file must be in the project root directory which means in the folder which has src folder.

Create a file named pom.xml at the root of the project and give it the following contents:

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
    <modelVersion>4.0.0</modelVersion>
    <groupId>HelloWorld</groupId>
    <artifactId>gs-maven-initial</artifactId>
    <version>0.1.0</version>
    <packaging>jar</packaging>
</project>

Now you can build your java project using 

mvn compile

This will download your dependencies and compile you java files. Corresponding .class files will be created in a target folder in the projects root folder.

To make the jar file of your project you can use

mvn package

This will create a jar file in the target folder. Now you can run your code with

java -jar PathToYourJarFile

Maven Build lifecycle

compile and package were some of the initial phases of Maven build lifecycle. All of them are listed in the following diagram

For more details on the maven build life cycle phases you can visit their official site.

I am getting Can't execute jar- file: “no main manifest attribute”. What should i do?

That is because you have not told maven while packaging how do you built the project. You need to provide build information withing <build> and </build> tags in the build file. You can add following tag between <project> and </project>.

    <build>
        <plugins>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-shade-plugin</artifactId>
                <version>2.1</version>
                <executions>
                    <execution>
                        <phase>package</phase>
                        <goals>
                            <goal>shade</goal>
                        </goals>
                        <configuration>
                            <transformers>
                                <transformer
                                    implementation="org.apache.maven.plugins.shade.resource.ManifestResourceTransformer">
                                    <mainClass>hello.HelloWorld</mainClass>
                                </transformer>
                            </transformers>
                        </configuration>
                    </execution>
                </executions>
            </plugin>
        </plugins>
    </build>

and you are done. By this you essentially say what is your main class so that while executing java knows the entry point from that jar file.

I want to use IDE instead of text editor. How do I import maven projects to my IDE?

Even this is very simple. You can run the following commands in the projects root directory -

• mvn eclipse:eclipse  (For Eclispe IDE)
• mvn idea:idea  (For intellij IDEA IDE)

For example idea command will generate all the required files like .ipr(project file), .iws(workspace file) etc. You can open the file by simply opening this .ipr file in IDEA.

Note : As per Mavens official site mvn idea:idea is obsolete. You can directly do File -> Import project and select pom.xml file.

I am getting "Package name does not correspond to the file path" error after importing project in my IDE.

This is because dash(-) is not allowed in package name and your -DgroupId contained  dash(-) which was used as package name. You can refactor and replace dash(-) with underscores(_) which is legal in a package name.

 Useful Links

• Can't execute jar- file: “no main manifest attribute”
• Building Java Projects with Maven
• Maven + Spring hello world example
• Package name does not correspond to the file path

How to install maven on Ubuntu?

What is Maven?

Maven is essentially a build automation tool similar to apache ant but provides much more features that just building. It addresses two important aspects -  

1. how your software will be built and 
2. your software dependency resolution

For complete details you can visit the following sites

1.  Wiki
2. Apache Maven Homepage

Lets get started then.

How to install Maven?

 You can search for the maven package using the following command

apt-cache search maven

You may see a lot of packages but what we are interested is -

maven - Java software project management and comprehension tool

So lets go ahead and install it. Use the following command to install the package

sudo apt-get install maven

I am using Ubuntu so I have apt-get. You can use yum  if you have Fedora/CentOS.

To verify the installation you can simply execute the following command

 mvn -v

v here stands for version. You can also type complete word i.e  mvn -version.

 You will see some details about the installed maven package.

This indicated maven is successfully installed.

Install latest versions

Using apt-get you may not get the latest version of maven. For latest version download the binary from maven site and install it.

Use the following commands - 

1. cd ~/Downloads
2. wget http://apache.mirrors.timporter.net/maven/maven-3/3.1.1/binaries/apache-maven-3.1.1-bin.tar.gz
3. sudo mkdir -p /usr/local/apache-maven
4. sudo mv apache-maven-3.1.1-bin.tar.gz /usr/local/apache-maven
5. cd /usr/local/apache-maven
6. sudo tar -xzvf apache-maven-3.1.1-bin.tar.gz
7. Edit ~/.profile with gedit ~/.profile and add these four lines:
1. export M2_HOME=/usr/local/apache-maven/apache-maven-3.1.1
2. export M2=$M2_HOME/bin
3. export MAVEN_OPTS="-Xms256m -Xmx512m"
4. export PATH=$M2:$PATH

Next immediate question that may come to anyone’s mind - 

Where is maven installed?

Maven by default gets installed in the following directory

/usr/share/maven

and maven configuration files go to the following directory

/etc/maven

settings.xml has default configurations like path to local repository. yes maven downloads dependencies and stores it in a local repository so that there is no need to download same dependency twice.

Path to maven(mvn) executable is not added to $PATH variable then how is the command recognized?

If you print your path variable by using

echo $PATH

You will notice one of the paths in the variable is

/usr/bin

Now if you see the contents of /usr/bin you will notice that it has mvn executable. It is actually soft link to the actual executable. This approach is a common approach. We cannot keep adding all installed packages folder to $PATH. Instead create a soft link to executable and keep it in  /usr/bin and add this to the $PATH.

This was just how do we install maven on ubuntu. In the next post we will see how to compile and run Java code using maven.

Related Links

• How to install Maven on Windows

Race Condition, Synchronization, atomic operations and Volatile keyword.

In this times where multi-threading is an essential feature of almost all systems it is very important for the programmers to handle race conditions. All the concepts mentioned in the title of this post - Race Condition, Synchronization, atomic operations and Volatile keyword are very much related to each other and understanding them together will give you a better and bigger picture of Concurrency.

Race Condition

Consider a very simple increment(++) operation. There is a common misconception that incrementing is an atomic operation. If you are wondering what atomic operations are then be patient. We will discuss it in a more detail later. For now you can understand atomic operation as an operation that takes only one CPU cycle.

But is is not. Incrementing is not an atomic operation. If you think a bit deeper you can imagine increment operation as sequence of following operations.

1. Read the value from the memory.
2. add one to it.
3. Write the changed value back to the memory.

Individual operations may or may or may not be atomic in nature(Will cover this in volatile section). But for our current discussion lets say the counter is of type int  and read/writes for it are atomic. That means as far as our discussion on race condition using increment is considered each subdivided operations mentions above happen in a single CPU cycle.

Now lets see where the problem arises.Lets say we have a single counter instance and it's value is 17. Lets say you have two thread T1 and T2. Both perform increment operation on the same counter instance so that the result we expect at the end is 19. Lets say T1 reads the value of the counter which is 17 and then context switch happens. Then T2 reads the value which is again 17. Now lets say T2 will increment the value to 18 and store it back in the memory. Now the T1 thread again increments the value it has(17) so that the result is 18 and stores it back in the memory which overwrites the T2 threads value. So at the end your value is 18 when you expected it to be 19.  This problem is called race condition. You can visualize the problem with following diagram -

So yes this a problem that every programmer faces while programming in multi-threaded environment. So what is the way out? One could say make an machine level increment operation that happens in a single CPU cycle(or in other words make the increment operation atomic). But we cannot make those machine level changes can we? There are other alternatives or work a rounds that will help us solve the problem. And the first one of it is called - Synchronization.

Synchronization

To avoid race conditions we can use synchronization. By synchronizing a part of code we ensure that only one thread can process that part of the code. In java either you can have synchronized methods or blocks.

Now even these methods or blocks can be further categorized into - 

1. instance methods/blocks
2. static/class methods/blocks

To understand the difference between above two it is essential to understand how synchronization mechanism works internally. Java is an Object oriented programming language and everything in it is essentially an Object. Each Object is associated with a monitor. Synchronization involves e thread getting a lock over this monitor. If one thread has a lock over the monitor other thread cannot acquire the lock and consequently cannot access the area governed by that monitor.

Now for instance methods lock is acquired for monitors of the instance itself. So for example if you have a getData()  method of the Employee class then the lock obtained is on the individual Employee instance.

On the other hand for static methods lock obtained is over Class instance of the Employee instance. You can get this Class object by using ClassName.class or classInstance.getClass() method. And this Class instance is same for all the individual Employee instances.

Refer : Interview Question #13 synchronization on static function/method.

So for above counter problem we can synchronize the increment operation with a synchronized function or a block. Eg.

    public synchronized void incrementCounter(){
        counter++;
    }

This involves obtaining lock on the instance or this and then increment. So as long as one thread is carrying out an increment operation no other thread can enter this function. Analogous synchronized block would be

    public void incrementCounter(){
        synchronized (this) {
            counter++;
        }
    }

That is all about the basics of synchronization. We may go into more detailed discussion in another post. But the basic concept of what is synchronization and why is it used should be clear by now.

Note :

Java synchronized keyword is re-entrant in nature it means if a java synchronized method calls another synchronized method which requires same lock then current thread which is holding lock can enter into that method without acquiring lock.(More on Synchronization)

Synchronization is an alternative for operations that are not atomic. So now lets see what atomic operations are.

Atomic operations

As mentioned previously each higher level language operation may require one or more CPU cycles to be completed. It is very much possible that before all the cycles needed for a particular operation are completed there may be context switch and some other process or thread might take control of the CPU resulting in race condition we discussed above. Though we cannot actually manipulate processor instructions there are work a rounds to make an operation atomic.

If you have encountered this context before you must have read -

"The Java language specification guarantees that reading or writing a variable is an atomic operation(unless the variable is of type long or double). Operations variables of type long or double are only atomic if they declared with the volatile keyword."

Even if not lets see what it means. It means read and writes of primitive variables are atomic in nature. Exception to this is long and double.

So why the exception?
Answer : It's not atomic because it's a multiple-step operation at the machine code level. That is, longs and doubles are longer than the processor's word length. So on a machine where processor's word length is greater than the long/double size it is possible for the corresponding read write operations to be atomic.

Note :   Also note it says only read and write. So do not confuse it with any other operation like incrementing, As mentioned above increment operation itself is composed of 3 sub operations listed above.

As per JLS

For the purposes of the Java programming language memory model, a single write to a non-volatile long or double value is treated as two separate writes: one to each 32-bit half. This can result in a situation where a thread sees the first 32 bits of a 64-bit value from one write, and the second 32 bits from another write.

Writes and reads of volatile long and double values are always atomic.

Writes to and reads of references are always atomic, regardless of whether they are implemented as 32-bit or 64-bit values. 

So another way to make read/write for long/double is to declare them volatile. I have just mentioned it here since it comes under atomic title but will discuss it more in next topic - Volatile variables.

Java specially provides atomic classes for purposes like this. For eg we have AtomicInteger or AtomicLong that provides methods like getAndDecrement(), getAndIncrement() and getAndSet() which are atomic.

The AtomicInteger class uses CAS (compare-and-swap) low-level CPU operations (no synchronization needed!) They allow you to modify particular variable only if the present value is equal to something else (and return it it succeed). So when you execute getAndIncrement() it actually runs in a loop (simplified real implementation):

int current;
do {
  current = get();
} while(!compareAndSet(current, current + 1)

Volatile keyword

Synchronization solves the problem faced due to race conditions but there is one another problem that we have missed and that is -  visibility.

Consider following code

public synchronized Singleton getInstance(){
if(_instance == null){   //race condition if two threads sees _instance= null
_instance = new Singleton();
}
}

 Here synchronization makes sure that only one thread enters the function and no other thread is allowed to access it until the thread which has the lock over it's monitor completes it's execution. But what about the variable visibility?

Thread T1 lets say identifies that  _instance is null. It acquires lock and creates new object but before the it comes out of the function lets say there is a context switch. Though new variable is created some other thread in some other function will still see _instance as null . This is because each thread caches the value of a variable and the synchronization among threads happen only when the synchronized method or block is completely executed. To overcome this problem we use volatile keyword.

Volatile keyword in Java guarantees that value of volatile variable will always be read from main memory and not from Thread's local cache thus solving the visibility issue.

Now lets come to the Long and Double issue and how making it volatile make it's read and write atomic. So there is this another concept  - happens before relationship that volatile keyword follows which means if there is a write operation with subsequent reads then reads will be processed only after write is successful.

Useful Links

This post is meant to clear the basic concepts of concurrency in Java and give you a bigger picture of how above topics are correlated. Maybe we will have individual posts to learn them individually. But you can refer to following links. They provide quite useful information.

•  How ConcurrentHashMap Works Internally in Java (OSFG)
• What is the difference of Atomic / Volatile / synchronize?
• Atomic Operations and multithreading
• How Volatile in Java works ? Example of volatile keyword in Java
• What is Race Condition in multithreading
• 20 Things on Synchronization, Synchroinzed Block, Method, locking and Threadsafety in Java

I would recommend read following book for a good exposure on Java concurrency -

• Java concurrency in practice - Book by Brian Goetz

JVM Shutdown Hook

Today I was going through articles on gracefully shutting down your Java process and came across the concept of Shutdown hooks in Java. You can register a shutdown hook which is a in-fact a thread and it will run before your JVM is shutdown and your program is terminated.

You can register a shutdown hook thread to your java process with just one line

Runtime.getRuntime().addShutdownHook(yourThreadInstance));

Let us see a demo example

public class ShutdownHookDemo {
    
    public static void main(String args[]){
        Runtime.getRuntime().addShutdownHook(new Thread(new ShutDownHook()));
        System.out.println("Shutdown hook registered");
        System.out.println("Before calling exit");
        System.exit(0);
        System.out.println("After exit");        
    }
    

}

class ShutDownHook implements Runnable{

    public void run() {
        System.out.println("Inside Shutdown hook");
        System.out.println("Shutdown hook thread sleeping for 2 seconds");
        try {
            Thread.sleep(2000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("Shutdown hook thread waking up");
        System.out.println("Shutdown hook thread terminating");
    }
    
}

and the output is

Shutdown hook registered
Before calling exit
Inside Shutdown hook
Shutdown hook thread sleeping for 2 seconds
Shutdown hook thread waking up
Shutdown hook thread terminating

When will Shutdown hook not be initiated

• you cannot register a shutdown hook after shutdown has been initiated. That means you cannot register a shutdown hook from a thread that is itself registered as a shutdown hook.
• Shutdown hook will not be called if Runtime.getRuntime().halt(status); is called. It abruptly shuts down the JVM.

Why above example did not print the statement after System.exit() call?

Code below System.exit() is not reachable though compiler doesn't really know it. Either an exception will be thrown or the JVM will be shutdown.  The call never really "returns". So nothing after the exit() call is executed.

Note :  You can register multiple shutdown hook threads with the java process. All of them will get executed in parallel once JVM shutdown is initiated.

To summarize

Useful Links

• JVM Shutdown Hook
• When should we call System.exit in Java
• Queries regarding Shutdown hook

How join() and yield() methods of Thread class work?

Background

A very general interview question on Threads in java. If you have 3 threads t1, t2 and t3 how would you structure your program such that t1 completes it execution before t2 and t2 before t3. To answer this question we need to know how join() method of Thread class works.

About join() method

The join method allows one thread to wait for the completion of another. If t is a Thread object whose thread is currently executing,

t.join();

causes the current thread to pause execution until t's thread terminates. 

Note : Like sleep(), join() responds to an interrupt by exiting with an InterruptedException.

Java7 documentation

Let us now understand the method behavior with an example. Run the following code

package in.blogspot.iquestions;

public class ThreadDemo implements Runnable {

    public void run() {
        try {
            System.out.println("Thread has started running. Waiting for 2 seconds");
            Thread.sleep(2000);
            System.out.println("Back from waiting.Terminating ThreadDemo now");
        } catch (InterruptedException e) {
            System.out.println("Thread was interrupted");
            e.printStackTrace();
        }
    }
    
    public static void main(String args[]) throws InterruptedException{
        System.out.println("Main thread started");
        Thread demoThread = new Thread(new ThreadDemo());
        System.out.println("Starting ThreadDemo thread");
        demoThread.start();
        demoThread.join(); //comment this line in 1st run
        System.out.println("Terminating main thread");
    }

}

What we are doing in above code is that we are running a thread ThreadDemo from our main thread. Now in 1st run comment out the demoThread.join(); line and execute the program.

Output on running without calling join()

Main thread started
Starting ThreadDemo thread
Terminating main thread
Thread has started running. Witing for 2 seconds
Back from waiting.Terminating ThreadDemo now

This shows that main thread exited before ThreadDemo thread. What we want in next run is for the main thread to wait until ThreadDemothread is executed. So in 2nd run use the join() call.

Output on running with join()

Main thread started
Starting ThreadDemo thread
Thread has started running. Waiting for 2 seconds
Back from waiting.Terminating ThreadDemo now
Terminating main thread

Here you will notice main thread will wait for ThreadDemo thread to complete it's execution. Only then the main thread continues with it's execution and terminates.

Summary of join() method of Thread class

Currently executing thread(whichever that is) will stop it's execution until the thread on which join is called has completed it's execution.

Understanding yield() method in java

 Before we go to yield() lets understand the difference between sleep() and wait() -

Main difference between wait and sleep is that wait() method release the acquired monitor when thread is waiting while Thread.sleep() method keeps the lock or monitor even if thread is waiting. Also, wait for method in Java should be called from synchronized method or block while there is no such requirement for sleep() method. 

Coming back to yield(), it's little different than wait() and sleep(), it just releases the CPU hold by Thread to give another thread an opportunity to run though it's not guaranteed who will get the CPU. It totally depends upon thread scheduler and it's even possible that the thread which calls the yield() method gets the CPU again.

I have copied yield() and diagram part from the link mentioned in the related links section below. However note that Object.notify() or Object.notifyAll() does not wake up sleeping thread. That part is not correct is diagram above.

Related Links

•  Difference between Wait and Sleep, Yield in Java

Serialization in Java

What is Serialization?

Serialization is the process of converting an object into a series of bytes, so that the object can be easily saved to persistent storage or streamed across a communication link. The byte stream can then be deserialised - converted into a replica of the original object.

What is java.io.Serializable?

Serializable is a marker interface just like  Cloneable interface. It does not have any methods to be implemented. Implementing this interface will allow an object to be serialized.

Example

package in.blogspot.iquestions;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;

public class SerializationExample {
    
    public static void main(String args[]) throws ClassNotFoundException{
        
        Employee employee = new Employee("Sam",18);
        
        try {
            ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(new File("C:\\Users\\Aniket\\Desktop\\test.txt")));
            ObjectInputStream ois = new ObjectInputStream(new FileInputStream(new File("C:\\Users\\Aniket\\Desktop\\test.txt")));
            System.out.println("Object before serialization : " + employee);
            oos.writeObject(employee);
            Employee employeeCopy = (Employee)ois.readObject();
            System.out.println("Object after deserialzation : " + employeeCopy);
            
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

class Employee implements Serializable{
    
    private static final long serialVersionUID = 8414822319246756172L;
    String name;
    int age;
    
    public Employee(String name, int age){
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Name is " + name + " and Age is " + age;
    }
    
}

Output :
Object before serialization : Name is Sam and Age is 18
Object after deserialzation : Name is Sam and Age is 18

What is use of serialVersionUID?

When you try your class to implement Serializable interface compiler will issue an warning.

Which clearly indicated you need something called serialVersionUID in your class. I use Eclipse and it gave me 3 quick fixes shown above.

1. Add default serial version ID : Selecting this option will assign some default value hard coded in the IDE.
2. Add generated serial version ID : This will generate a hash value depending on your variables/methods and use it in your class.
3. The 3rd option is just a suppress warning to tell compiler you can ignore this warning.

This variable is private static final long . Default value option gives

private static final long serialVersionUID = 1L;

where as  generated one was as follows

private static final long serialVersionUID = 8414822319246756172L;

If you do not assign it then java compiler will generate it and normally it’s equal to hashCode of object.

This is about the variable but the main question still remains - Whats the need for it?

Well it is used to match the versions of the class. I will bring up this point again later but serialVersionUID is the only variable that is static and is serialized(state is stored) because static variables are not serialized. Just note this at the moment we will discuss it later. If these value on deserialization does not match exception InvalidClassException in thrown.

Are there any other ways to serialize an object other than Java serialization?

Answer to that would be Yes!

1. For object serialization, instead of implementing the Serializable interface, a developer can implement the Externalizable interface, which extends Serializable. By implementing Externalizable, a developer is responsible for implementing the writeExternal() and readExternal() methods. As a result, a developer has sole control over reading and writing the serialized objects.
2. XML serialization is an often-used approach for data interchange. This approach lags runtime performance when compared with Java serialization, both in terms of the size of the object and the processing time. With a speedier XML parser, the performance gap with respect to the processing time narrows. Nonetheless, XML serialization provides a more malleable solution when faced with changes in the serializable object.

What happens if the object to be serialized includes the references to other serializable objects?

If the object to be serialized includes the references to other objects whose class implements serializable then all those object’s state also will be saved as the part of the serialized state of the object in question. The whole object graph of the object to be serialized will be saved during serialization automatically provided all the objects included in the object’s graph are serializable.

 What happens if an object is serializable but it includes a reference to a non-serializable object?

If you try to serialize an object of a class which implements serializable, but the object includes a reference to an non-serializable class then a ‘NotSerializableException’ will be thrown at runtime.

Are the static variables saved as the part of serialization?

This is the question I was referring to earlier. Let us discuss this now. Recollect the purpose of Serialization. It is used to convert Object(with a state) to series if bytes and deserialization gives us back the exact same copy. The main purpose is to save the Object state and static variables do not form part of object state(rather they are part of Class state). So the answer is No! Static variables belong to the class and not to an object they are not the part of the state of the object so they are not saved as the part of serialized object. 

What is a transient variable?

 It has a very simple definition. Variables which you do not wish to save on serialization or which should not be a part of object state is to be defined as transient. These variables are not included in the process of serialization and are not the part of the object’s serialized state.

What will be the value of transient variable after de-serialization?

Transient variables will get default values[More details] on deserialization.  

Does the order in which the value of the transient variables and the state of the object using the defaultWriteObject() method are saved during serialization matter?

 Yes! As while restoring the object’s state the transient variables and the serializable variables that are stored must be restored in the same order in which they were saved. 

If a class is serializable but its superclass in not , what will be the state of the instance variables inherited  from super class after deserialization?

The values of the instance variables inherited from superclass will be reset to the values they were given during the original construction of the object as the non-serializable super-class constructor will run.

To serialize an array or a collection all the members of it must be serializable. True /False?

Arrays are Objects in Java and can be serialized like any other Object. Point to note here is that for an array to be serializable all of it's members must be serializable.

Suppose super class of a new class implement Serializable interface, how can you avoid new class to being serialized?

One of the tricky interview question in Serialization in Java. If Super Class of a Class already implements Serializable interface in Java then its already Serializable in Java, since you can not unimplemented an interface its not really possible to make it Non Serializable class but yes there is a way to avoid serialization of new class. To avoid java serialization you need to implement writeObject() and readObject() method in your Class and need to throw NotSerializableException from those method.

Note : Serialization doesn't write out the object a second time. It sees you're writing out an object that is already written out, and only writes out a reference to the object that previously was serialized.

For example see the code below -

public static void main(String args[]) throws FileNotFoundException, IOException, ClassNotFoundException
{
    ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(new File("data.txt")));
    Human human = new Human();
    human.setAge(21);
    human.setName("Test");
    System.out.println("Human : " + human);
    oos.writeObject(human);
    human.setName("Test123");
    oos.writeObject(human);
    ObjectInputStream ois = new ObjectInputStream(new FileInputStream(new File("data.txt")));
    Human newHuman1  = (Human)ois.readObject();
    System.out.println("newHuman1 :" + newHuman1);
    Human newHuman2  = (Human)ois.readObject();
    System.out.println("newHuman2 :" + newHuman2);
}

and it prints -

Human : Human [age=21, name=Test]
newHuman1 :Human [age=21, name=Test]
newHuman2 :Human [age=21, name=Test]

NOTE :  All classes get a serialVersionUID - one is generated by the serialization runtime if you haven't declared one. By declaring a serialVersionUID you're telling the serialization runtime, don't generate one because you know the serialized form of the classes is compatible with one built earlier.

 The serialization runtime associates with each serializable class a version number, called a serialVersionUID, which is used during deserialization to verify that the sender and receiver of a serialized object have loaded classes for that object that are compatible with respect to serialization. If the receiver has loaded a class for the object that has a different serialVersionUID than that of the corresponding sender's class, then deserialization will result in an InvalidClassException. A serializable class can declare its own serialVersionUID explicitly by declaring a field named "serialVersionUID" that must be static, final, and of type long:


    ANY-ACCESS-MODIFIER static final long serialVersionUID = 42L;


    If a serializable class does not explicitly declare a serialVersionUID, then the serialization runtime will calculate a default serialVersionUID value for that class based on various aspects of the class, as described in the Java(TM) Object Serialization Specification. However, it is strongly recommended that all serializable classes explicitly declare serialVersionUID values, since the default serialVersionUID computation is highly sensitive to class details that may vary depending on compiler implementations, and can thus result in unexpected InvalidClassExceptions during deserialization. Therefore, to guarantee a consistent serialVersionUID value across different java compiler implementations, a serializable class must declare an explicit serialVersionUID value. It is also strongly advised that explicit serialVersionUID declarations use the private modifier where possible, since such declarations apply only to the immediately declaring class--serialVersionUID fields are not useful as inherited members.

Related  Links

•  What is object serialization?
•  Java Serialization
• Top 10 Java Serialization Interview Questions and Answers 
• What is a serialVersionUID and why should I use it? 
• Changing instance state does not get reflected in serialized object

Difference between data encapsulation and data abstraction in java.

Four important concepts or principles in Java are

1. Data encapsulation
2. Data abstraction
3. Inheritance
4. Polymorphism

In this post, we will look at first two principles - Encapsulation and Abstraction.

General View

            Data Encapsulation simply means wrapping relevant data together whereas Data abstraction means abstracting out the underneath logic and expose only the relevant part to the user. This is a very generic statement. We will get back to the what it actually means in Java language.

Data Encapsulation in Java

        Java is an Object oriented programming language, That means everything in java is an object and these objects interact with each other to form an executing program. Classes are nothing but blueprints of Objects and these classes form the very basis of Data encapsulation.

Data encapsulation in its simple form means wrapping the relevant data in a class and controlling its access. This is also sometimes associated with another keyword - Data Hiding. When we design the class we essentially write encapsulation rules.Lets us go a little deeper to understand this concept - 

• We achieve data encapsulation in java by using access modifiers - Public,Protected,default,Private. 

We define functions or variables with some access modifier to control the extent of scope that can be used or accessed by the user. Common examples are declaring a variable private and giving its access using getter and setter methods or declaring a method private if it's only use is withing the class.

This is also why it is referred to as data hiding. We hide the data and provide only desired access to it.

Note: Keywords encapsulation and data hiding are used synonymously everywhere. It should not be misunderstood that encapsulation is all about data hiding only. When we say encapsulation, emphasis should be on grouping or packaging or bundling related data and behavior together. 

A very basic encapsulation example

public class Animal {
    
    private String type;

    public String getType() {
        return type;
    }

    public void setType(String type) {
        this.type = type;
    }
        
}

Data Abstraction in Java

Data abstraction simply means generalizing something to hide the complex logic that goes underneath. Consider a very simple example of computer science - subtraction. If we have two variables  "a" and "b" we simply say their subtraction is (a-b). But what is really happening behind the scenes? These variables are stored in main memory in binary format. The processor processes the subtract information which really takes place using two's complement method. Again in the processor, we have gates that actually carry out the procession. Even inside gates, there are pins and 1 and 0 simple means high and low signals. 

Even though the process is so complex underneath a normal software developer developing some financial application need not know every small detail. This is because the concept has been abstracted out. This is what abstraction means in a general terminology.

• We achieve data abstraction in Java primarily by using Interfaces and abstract classes.

 We only expose the method signature to the user. All user needs to know is what input or parameters he must supply to the function and what is the desired output or return value.

Lets us take an example to understand this function -

Let's say we have an interface Animal and it has a function makeSound(). There are two concrete classes Dog and Cat that implement this interface. These concrete classes have separate implementations of makeSound() function. Now let's say we have an animal(We get this from some external module). All user knows is that the object that it is receiving is some Animal and it is the user's responsibility to print the animal sound. One brute force way is to check the object received to identify it's type, then typecast it to that Animal type and then call makeSound() on it. But a neater way is to abstracts thing out. Use Animal as a polymorphic reference and call makeSound() on it. At runtime depending on what the real Object type is proper function will be invoked.    

I would like to end this post by saying Data encapsulation(Data hiding) is wrapping and controlling access of logically related data in a class. One of the aspects of this is by using suitable access modifiers. Data abstraction, on the other hand, is generalizing the concept so that the underlying complex logic is hidden from the user. In java, this is achieved by using interfaces and abstract classes.

Encapsulation is combining related logic data (variables and methods) whereas Abstraction is hiding internal implementation details and expose only relevant details to the user. In a way you can Abstraction is achieved by Encapsulation.

 A generic diagram to understand the difference is provided below. Note complex logic is on the circuit board which is encapsulated in a touchpad and a nice interface(buttons) is provided to abstract it out.

Useful Links

• difference between abstraction and encapsulation?
• Java Encapsulation
• Java Abstraction