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