Revision Day 3: Spring Entity Manager and HTML

Implemented the Entity Manager functionality for the yesterday's springMvcApplication

Revision Day 2: SPRING MVC

Completed the simple mvc application.

Link:- https://github.com/vikramsvk/Spring-Hibernate

Changed it from spring jdbctemplate to hibernate for Dao implementation.

Web.xml:-

<?xml version="1.0" encoding="UTF-8"?>

<web-app xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"

       xmlns="http://java.sun.com/xml/ns/javaee"

       xsi:schemaLocation="http://java.sun.com/xml/ns/javaee http://java.sun.com/xml/ns/javaee/web-app_3_0.xsd"

       version="3.0">

       <display-name>Archetype Created Web Application</display-name>

       <welcome-file-list>

             <welcome-file>home.jsp</welcome-file>

       </welcome-file-list>

       <servlet>

             <servlet-name>spring-mvc</servlet-name>

             <servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class>

             <load-on-startup>1</load-on-startup>

       </servlet>

       <servlet-mapping>

             <servlet-name>spring-mvc</servlet-name>

             <url-pattern>/</url-pattern>

       </servlet-mapping>

<!-- <context-param>

             <param-name>contextConfigLocation</param-name>

             <param-value>/WEB-INF/spring-mvc-servlet.xml</param-value>

       </context-param>

       <listener>

             <listener-class>org.springframework.web.context.ContextLoaderListener</listener-class>

       </listener> -->

</web-app>

Wasted lot of time in understanding how this “spring-mvc-servlet.xml” getting loaded i.e. how spring is getting initiated when I am not specifying which file to fetch nor the file path??

After so much of investigation I came to know that

<servlet-name>spring-mvc</servlet-name>

             <url-pattern>/</url-pattern>

Here server will take servlet-name as the standard file name and appends -servlet at the end like this:-

Loading XML bean definitions from ServletContext resource [/WEB-INF/spring-mvc-servlet.xml

When you want to put your Servlet file in your custom location or with custom name, rather than the default naming convention [servletname]-servlet.xml and path under Web-INF/ ,then you can use ContextLoaderListener.

I ran simple java main class to test the application functionality by placing the spring-mvc-servlet.xml in resources folder.

import org.springframework.context.ApplicationContext;

import org.springframework.context.support.ClassPathXmlApplicationContext;

import jbr.springmvc.model.Login;

import jbr.springmvc.model.User;

import jbr.springmvc.service.UserService;

public class App {

  public static void main(String[] args) {

    ApplicationContext context = new ClassPathXmlApplicationContext("spring-mvc-servlet.xml");

    UserService obj = (UserService) context.getBean("userService");

    Login login = new Login();

    login.setUsername("admin");

    login.setPassword("admin123");

    User user = obj.validateUser(login);

    System.out.println(user.toString());

  }

}

Embed jetty in the application so need to to run in the external server while testing

<build>

             <finalName>SpringMvcUser</finalName>

             <plugins>

                    <plugin>

                           <groupId>org.mortbay.jetty</groupId>

                           <artifactId>jetty-maven-plugin</artifactId>

                           <version>8.1.16.v20140903</version>

                           <configuration>

                                 <scanIntervalSeconds>10</scanIntervalSeconds>

                           </configuration>

                    </plugin>

             </plugins>

       </build>

Use mvn jetty:run

SPRING:-

Spring framework provides flexibility to configure beans in multiple ways such as XML, Annotations, and JavaConfig.

What is dependency injection and its types?

A technique where the instance is not directly passed but its specified how to create the instance, this helps in loose coupling and testing.

Types:-

1.              Setter injection
2.              Constructor injection

We prefer setter injection over constructor injection because it helps in resolving cyclic dependency.

Scenario:- If A is dependent on B and vice-versa, then we can neither create instance of A nor B because A requires instance of B passed in the constructor and B requires instance of A be passed in the constructor, This can be resolved by setter injection where the instance A is created first then we can set the B’s instance.

Revision Day 1

• Revised all the algorithms That i worked on in the past couple of months while working on Princeton's algorithms course.
• Read about Hoare’s Partition Scheme and Lomuto partition scheme on quicksort,Dijkistra's algorithm etc.
• I am not going to spend more time on this again.
• updated my algorithms summary article.so that i can just go through it for quick reference.

Java Notes

Java Technology

HelloWorld.java -> Java Code
HelloWorld.class -> Java ByteCode

Bytecode

Object : -An  real-world object with state and behaviour

Class:- It’s a blueprint from which objects can be created

Class can be public or default.it cannot be declared as private or protected.

Class Name consists of:- alphabets, Numbers, $,_

Inheritance

Extends

Interface – A Contract between a class and the outside world.

Implements

Package

Variables
Instance Variables (Non-Static Fields)
Class Variables (Static Fields)
Local Variables
Parameters


Literals :- Java Literals are syntactic representations of variables.

Using Underscore Characters in Numeric Literals
long creditCardNumber = 1234_5678_9012_3456L; which is equal to 1234567890123456

Array
Java.util.Arrays
Arrays.binarySearch(array,key)
Arrays.fill(array,value)
Arrays.Equals(array1,array2) 1 dimension
Arrays.deepequals(array1,array2) 2 dimension

Operators


Type Comparison Operator instanceof

Bitwise and Bit Shift Operators

<<,<<<,&,|,^

If another class cannot call a Class constructor, it cannot directly create Class objects.

Variable Argument (Varargs)

            private static int add(int... i) {
                        int sum = 0;
                        for (int k = 0; k < i.length; k++) {
                                    sum += i[k];
                        }
                        return sum;
            }

Object Creation of  a class by name myClass:-

new()
myClass.class.newInstance()
Class obj = Class.forName("myClass”);
myClass myclass = obj.getInstance();
Serialization
Clone()


compile-time constant
A constant variable of primitive type or type String that is declared final and initialized with a compile-time constant expression.

Important Nested Classes

Nested classes that are declared static are called static nested classes.
Non-static nested classes are called inner classes.
There are two special kinds of inner classes: local classes and anonymous classes.
a local class can access local variables and parameters of the enclosing block that are final or
effectively final
Shadowing
Local classes are similar to inner classes because they cannot define or declare any static members
Final and Effectively Final:-
A variable or parameter whose value is never changed after it is initialized is effectively final.

Serializable

serialize an object means to convert its state to a byte stream so that the byte stream can be
 reverted back into a copy of the object.
A Java object is serializable if its class or any of its superclasses implements either the
 java.io.Serializable interface or its subinterface, java.io.Externalizable.

Enum

All enums implicitly extend java.lang.Enum.hence they cannot be extended further.
Note: The constructor for an enum type must be package-private or private access. It automatically
creates the constants that are defined at the beginning of the enum body. You cannot invoke an
enum constructor yourself


All interfaces are inherently static
Annotation

Interfaces
abstract methods, default methods, and static methods.
All constant values defined in an interface are implicitly public, static, and final, you can omit
these modifiers.

The Java programming language supports multiple inheritance of type

Using an Interface as a Type

Overriding and Hiding Methods

covariant return type

Instance methods are preferred over interface default methods.

Static methods in interfaces are never inherited.

virtual method invocation

hiding fields
hiding methods

Methods called from constructors should generally be declared final.

Abstract Class Implements an Interface

Abstract calss can have final methods.

static import

Generics

type inference

bounded type parameters

Given two concrete types A and B (for example, Number and Integer), MyClass<A> has no
 relationship to MyClass<B>, regardless of whether or not A and B are related. The common
parent of MyClass<A> and MyClass<B> is Object.

static import

exception

exception handling

call stack

Checked Exceptions
Errors and runtime exceptions are collectively known as unchecked exceptions

All exceptions inherit from Throwable class

If a catch block handles more than one exception type, then the catch parameter is implicitly final.

try-with-resources statement is a try statement that declares one or more resources.
Any object that implements java.lang.AutoCloseable, which includes all objects which implement
 java.io.Closeable, can be used as a resource.

suppressed exceptions

runtime exception  occurs when a method tries to access a member of an object through a null
reference

StackTraceElement

File IO

java.io vs java.nio

Io Streams

Array based memory

byte streams

InputStream and OutputStream are superclasses

FileInputStream and FileOutputStream are descendends of above two classes.Used for byte reading

FileReader and FileWriter same as above used for character’s reading.

BufferedReader and PrintWriter used in Line-Oriented I/O


Buffered Streams


There are four buffered stream classes used to wrap unbuffered streams: BufferedInputStream and
BufferedOutputStream create buffered byte streams, while BufferedReader and BufferedWriter
create buffered character streams.


flushing the buffer.

Datastreams

objectStreams


FileVisitor to walkthrough file tree

Type Erasure and Bridge Methods
       
Restrictions on generics

 ACID (Atomicity, Consistency, Isolation, Durability)

DFS and BFS

package vikram.HR;

// Java program to print DFS traversal from a given given graph

import java.util.*;
import java.util.LinkedList;

// This class represents a directed graph using adjacency list
// representation
public class DFSBFS {
    private int V;   // No. of vertices

    // Array  of lists for Adjacency List Representation
    private java.util.LinkedList<Integer> adj[];

    // Constructor
    public DFSBFS(int v) {
        V = v;
        adj = new java.util.LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new java.util.LinkedList();
    }

    //Function to add an edge into the graph
    void addEdge(int v, int w) {

        adj[v].add(w);  // Add w to v's list.
    }

    // A function used by DFS
    void DFSUtil(int v, boolean visited[]) {
        // Mark the current node as visited and print it
        visited[v] = true;
        System.out.print(v + " ");

        // Recur for all the vertices adjacent to this vertex
        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    // The function to do DFS traversal. It uses recursive DFSUtil()
    void DFS(int v) {
        // Mark all the vertices as not visited(set as
        // false by default in java)
        boolean visited[] = new boolean[V];

        // Call the recursive helper function to print DFS traversal
        DFSUtil(v, visited);
    }

    // prints BFS traversal from a given source s
    void BFS(int s) {
        // Mark all the vertices as not visited(By default
        // set as false)
        boolean visited[] = new boolean[V];

        // Create a queue for BFS
       java.util.LinkedList<Integer> queue = new LinkedList<Integer>();

        // Mark the current node as visited and enqueue it
        visited[s] = true;
        queue.add(s);

        while (queue.size() != 0) {
            // Dequeue a vertex from queue and print it
            s = queue.poll();
            System.out.print(s + " ");
            // Get all adjacent vertices of the dequeued vertex s
            // If a adjacent has not been visited, then mark it
            // visited and enqueue it
            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

    public static void main(String args[]) {
        DFSBFS g = new DFSBFS(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("Following is Depth First Traversal " +
                "(starting from vertex 2)");
        System.out.println("BFS:-");
        g.BFS(2);
        System.out.println("\nDFS:-");
        g.DFS(2);
    }
}
// This code is contributed by Aakash Hasija

Completed - CTCI 20 Days Challange

Completed the Challenge in 18 days(25th July-12th Aug).

Digest:-

• Most of the problems were easier than I thought.
• Learnt implementation of algorithms like tries,heaps,BFS and DFS.
• Gained lot of confidence on my algorithmic knowledge.
• Learnt discipline and working in time bound environment.
• On paper working helped me a lot,need to practice further on that.
• Few backlogs are left out,need to cover them ASAP.  note:- Completed all problems on 22/8/17
• Uploaded all the solutions on Github at link:-  Github link

CTCI Challange, DAY 20

Day 20

Problem Statement:-Bit Manipulation: Lonely Integer

Studied the Bit manipulation.
Solution:-

   public static int lonelyInteger(int[] a) {
        int value = 0;
        for (int i : a)
            value ^= i;
        return value;
    }

CTCI Challange, DAY 19

Day 19

Problem Statement:- DP: Coin Change

Spent time in understanding this problem,feeling difficult to understand.

TODO:-
Need to go through below links.

https://www.youtube.com/watch?v=jaNZ83Q3QGc

CTCI Challange, DAY 18

Day 18

Problem Statement:- Recursion: Davis' Staircase

Solution:-

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        for(int a0 = 0; a0 < s; a0++){
            int n = in.nextInt();
            System.out.println(NoOfWays(n));
        }
    }
 
        private static int NoOfWays(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;
        return NoOfWays(n - 1) + NoOfWays(n - 2) + NoOfWays(n - 3);
    }
}

Note:-
updated on 22/8/17
Completed the problem with small trick.
I passed the calculated the values till 5,there by reducing the calculation time.

public class Stairs {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        for (int a0 = 0; a0 < s; a0++) {
            int n = in.nextInt();
            System.out.println(recur(n));
        }
    }

    public static int recur(int n) {
        if (n == 1) 
            return 1;
        if (n == 2)
            return 2;
        if (n == 3)
            return 4;
        if (n==4)
            return 7;
        if (n==5)
            return 13;
        return recur(n - 1) + 
                recur(n - 2) + recur(n - 3);
    }
}

CTCI Challange, DAY 17

Day 17

Problem Statement:-Recursion: Fibonacci Numbers

 very simple recursive fibonacci no problem.

Solution:-

   public static int fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

CTCI Challange, DAY 16

Day 16:-

Problem Statement:-Time Complexity: Primality

Simple problem,If its even no then its definately not prime,if its odd no,then loop n/2 times and try to find the divisor if not found any then its prime.


Solution:-

import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int p = in.nextInt();
        for (int a0 = 0; a0 < p; a0++) {
            int n = in.nextInt();

            System.out.println(isPrime(n));
        }
    }

    private static String isPrime(int n) {
        if (n==1){
            return "Not prime";
        }
        if (n==2) return "Prime";
        if (n % 2 == 0) {
            return "Not prime";
        }
        for (int i = 3; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return "Not prime";
            }
        }
        return "Prime";
    }
}

CTCI Challange, DAY 15

Day 15

Problem Statement:- BFS: Shortest Reach in a Graph

Tried a lot,couldn't end up with successful solution,only few tests were passing.
Hence referred online for solution and practiced. Added to backlog to revisit again.

Solution:-

package vikram.CTCI;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.HashSet;
import java.util.ArrayDeque;

public class Shortest_Reach {
    private static final int EDGE_WEIGHT = 6;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int numQueries = scan.nextInt();

        for (int q = 0; q < numQueries; q++) {
            int numNodes = scan.nextInt();
            int numEdges = scan.nextInt();
            
            /* Create Nodes */
            Node[] node = new Node[numNodes + 1]; // node "i" will be at index "i"
            node[0] = null;
            for (int i = 1; i <= numNodes; i++) {
                node[i] = new Node(i);
            }
            
            /* Connect Nodes */
            for (int i = 0; i < numEdges; i++) {
                int n1 = scan.nextInt();
                int n2 = scan.nextInt();
                node[n1].addNeighbor(node[n2]);
            }
            
            /* Create MST */
            int start = scan.nextInt();
            findDistances(node[start]);

            /* Print results */
            for (int i = 1; i <= numNodes; i++) {
                if (i != start) {
                    System.out.print(node[i].distance + " ");
                }
            }
            System.out.println();
        }
        scan.close();
    }

    private static void findDistances(Node start) {
        if (start == null) {
            return;
        }
        Queue<Node> deque = new LinkedList<>(); // use deque as a queue
        start.distance = 0;
        deque.add(start);
        while (!deque.isEmpty()) {
            Node curr = deque.remove();
            for (Node neighbor : curr.neighbors) {
                if (neighbor.distance == -1) { // meaning it's unvisited
                    neighbor.distance = curr.distance + EDGE_WEIGHT;
                    deque.add(neighbor);
                }
            }
        }
    }

    /* Implementation of an UNDIRECTED graph */
    public static class Node {
        public final int id; // each Node will have a unique ID
        public int distance; // Also tells us if Node has been visited (-1 means unvisited)
        public HashSet<Node> neighbors;

        public Node(int id) {
            this.id = id;
            distance = -1;
            neighbors = new HashSet<>();
        }

        public void addNeighbor(Node neighbor) {
            neighbors.add(neighbor);
            neighbor.neighbors.add(this);
        }

        @Override
        public boolean equals(Object other) {
            if (other == this) {
                return true;
            } else if (other == null || !(other instanceof Node)) {
                return false;
            }
            Node otherNode = (Node) other;
            return this.id == otherNode.id;
        }

        @Override
        public int hashCode() {
            return id; // simple and effective
        }
    }
}

CTCI Challange, DAY 14

Day 14

Problem Statement:-DFS: Connected Cell in a Grid

I did't know about DFS and BFS, gone through the Princeton Video lectures and tries to solve the DFS and BF once before attempting to solve the problem,this helped a lot.


Solution:-

public class Graph {

    public static int getBiggestRegion(int[][] matrix) {
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        int bigRegion = 0;
        int size = 0;
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[0].length; col++) {
                if (!visited[row][col]) {
                    size = findRegion(matrix, visited, row, col);
                    bigRegion = Math.max(bigRegion, size);
                }
            }
        }
        return bigRegion;
    }

    private static int findRegion(int[][] matrix, boolean[][] visited, int row, int col) {
        if (row >= matrix.length || col >= matrix[0].length) return 0;
        if (row < 0 || col < 0) return 0;
        int count = 0;
        if (visited[row][col]) return 0;
        visited[row][col] = true;
        if (matrix[row][col] == 0) {
            return 0;
        }
        count = 1;
        count += findRegion(matrix, visited, row + 1, col);
        count += findRegion(matrix, visited, row, col + 1);
        count += findRegion(matrix, visited, row + 1, col + 1);
        count += findRegion(matrix, visited, row - 1, col);
        count += findRegion(matrix, visited, row, col - 1);
        count += findRegion(matrix, visited, row - 1, col - 1);
        count += findRegion(matrix, visited, row - 1, col + 1);
        count += findRegion(matrix, visited, row + 1, col - 1);
        return count;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int grid[][] = new int[n][m];
        for (int grid_i = 0; grid_i < n; grid_i++) {
            for (int grid_j = 0; grid_j < m; grid_j++) {
                grid[grid_i][grid_j] = in.nextInt();
            }
        }
        System.out.println(getBiggestRegion(grid));
    }
}

CTCI Challange, DAY 13

Day 13:-

Problam Statement:-Binary Search: Ice Cream Parlor


I didn't solve on paper as i practiced Binary Search algo on system before attemptng this problem.
Solution:-

import java.util.*;

class IceCream implements Comparable {
    int flavorCost;
    int index;

    public IceCream(int flavor, int index) {
        this.flavorCost = flavor;
        this.index = index;
    }

    @Override
    public int compareTo(Object o) {
        IceCream iceCream = (IceCream) o;
        return this.flavorCost - iceCream.flavorCost;
    }

    @Override
    public boolean equals(Object o) {
        IceCream iceCream = (IceCream) o;
        if (this.flavorCost == iceCream.flavorCost && this.index == iceCream.index) {
            return true;
        }
        return false;
    }

}

public class Solution1 {

    public static int binarySearch(int first, int last, IceCream[] arr, int search) {
        if (first > last) {
            return -1;
        }
        int mid = (first + last) / 2;
        if (arr[mid].flavorCost == search) {
            return arr[mid].index;
        }
        if (search > arr[mid].flavorCost) {
            return binarySearch(mid + 1, last, arr, search);
        }
        if (search < arr[mid].flavorCost) {
            return binarySearch(first, mid - 1, arr, search);
        }
        return -1;
    }

    public static void main(String[] args) {

        int t;
        int n, m;

        Scanner in = new Scanner(System.in);
        t = in.nextInt();
        for (int test = 0; test < t; test++) {

            m = in.nextInt();
            n = in.nextInt();
            IceCream[] arr = new IceCream[n];


            for (int i = 0; i < n; i++)
                arr[i] = new IceCream(in.nextInt(), i + 1);
            Arrays.sort(arr);
            int firstIndex = 100000, secondIndex = 100000;
            for (int i = 0; i < n - 1; i++) {
                int search = m - arr[i].flavorCost;
                if (search >= arr[i].flavorCost) {
                    int index = binarySearch(i + 1, n - 1, arr, search);
                    if (index != -1) {
                        System.out.println(Math.min(arr[i].index, index) + " " + Math.max(arr[i].index, index));
                        break;
                    }
                }
            }
        }
    }
}

CTCI Challange, DAY 12

Day 12:- 

Problem Statement:-Merge Sort: Counting Inversions

practiced the mergesort before going to solve the problem,It was very easy.

Solution:-

public class Inversions {

    static long countInversions(int[] arr) {
        MergeSort mr = new MergeSort();
        return mr.mergesort(arr);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int a0 = 0; a0 < t; a0++) {
            int n = in.nextInt();
            int[] arr = new int[n];
            for (int arr_i = 0; arr_i < n; arr_i++) {
                arr[arr_i] = in.nextInt();
            }
            long result = countInversions(arr);
            System.out.println(result);
        }
        in.close();
    }

    private static long merge(int[] a, int[] aux, int lo, int mid, int hi) {
        long inversions = 0;

        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }

        // merge back to a[]
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (aux[j] < aux[i]) {
                a[k] = aux[j++];
                inversions += (mid - i + 1);
            } else a[k] = aux[i++];
        }
        return inversions;
    }

}

class MergeSort {

    public long mergesort(int[] array) {
        int[] helper = new int[array.length];
        return mergesort(array, helper, 0, array.length - 1);
    }

    public long mergesort(int[] array, int[] helper, int low, int high) {
        long count = 0;
        if (low < high) {
            int middle = (low + high) / 2;
            count += mergesort(array, helper, low, middle); // Sort left half
            count += mergesort(array, helper, middle + 1, high); // Sort right half
            count += merge(array, helper, low, middle, high); // Merge them
        }
        return count;
    }

    /*public long merge(int[] array, int[] helper, int low, int middle, int high) {

*//* Copy both halves into a helper array *//*
        for (int i = low; i <= high; i++) {
            helper[i] = array[i];
        }

        int helperLeft = low;
        int helperRight = middle + 1;
        int current = low;

*//* Iterate through helper array. Compare the left and right
         * half, copying back the smaller element from the two halves
* into the original array. *//*
        while (helperLeft <= middle && helperRight <= high) {
            if (helper[helperLeft] <= helper[helperRight]) {
                array[current] = helper[helperLeft];
                helperLeft++;
            } else { // If right element is smaller than left element
                array[current] = helper[helperRight];
                helperRight++;
                count++;
            }
            current++;
        }

*//* Copy the rest of the left side of the array into the
         * target array *//*

        int remaining = middle - helperLeft;
        count += remaining;
        for (int i = 0; i <= remaining; i++) {
            array[current + i] = helper[helperLeft + i];
        }
        int remaining1 = high - helperRight;
        for (int i = 0; i <= remaining1; i++) {
            array[current + i] = helper[helperLeft + i];
        }
        return count;
    }*/

    private static long merge(int[] a, int[] aux, int lo, int mid, int hi) {
        long inversions = 0;
        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }

        // merge back to a[]
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (aux[j] < aux[i]) {
                a[k] = aux[j++];
                inversions += (mid - i + 1);
            } else a[k] = aux[i++];
        }
        return inversions;
    }
}

NOTE:- CTCI Challange

I wont be working on this weekend(5th and 6th august) as I will be busy in family function.

Note:-on 10th Aug,2 days gap extended to 7 days,Sorry.

CTCI Challange, DAY 11

Day 11

Problem Statement:- Sorting: Comparator

Today's problem was very easy,on comparators.
i have copied the int to Integer so as to use the compareTo() functionality.

On Paper:-

Solution:-

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class Player {
    String name;
    int score;

    Player(String name, int score) {
        this.name = name;
        this.score = score;
    }
}

class Checker implements Comparator<Player> {

    @Override    public int compare(Player o1, Player o2) {
        Integer i1 = o1.score;
        Integer i2 = o2.score;
        if (i2.compareTo(i1) == 0) {
            return o1.name.compareTo(o2.name);
        }
        return i2.compareTo(i1);
    }
}

class Solution {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        Player[] player = new Player[n];
        Checker checker = new Checker();

        for (int i = 0; i < n; i++) {
            player[i] = new Player(scan.next(), scan.nextInt());
        }
        scan.close();

        Arrays.sort(player, checker);
        for (int i = 0; i < player.length; i++) {
            System.out.printf("%s %s\n", player[i].name, player[i].score);
        }
    }
}

CTCI Challange, DAY 10

Day 10:-

Problem Statement:-Sorting: Bubble Sort

The problem is an implementation of bubble sort,it was very easy.
did very silly mistake,need to be concious.

import java.util.Scanner;

/**
 * @author vikram.shanbogar@gmail.com
 * on 8/3/2017.
 */
public class Bsort {
    static int swaps = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long a[] = new long[n];
        for (int a_i = 0; a_i < n; a_i++) {
            a[a_i] = in.nextInt();
        }
        sort(a);
        printOutputs(a);
    }

    private static void printOutputs(long[] a) {
        System.out.printf("Array is sorted in %d swaps.\n", swaps);
        if (a.length > 0) {
            System.out.printf("First Element: %d\n", a[0]);
            System.out.printf("Last Element: %d", a[a.length - 1]);
        }
    }

    private static void sort(long[] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length-1; j++) {
                if (a[j] > a[j+1]) {
                    exch(a, j, j+1);
                    swaps++;
                }
            }
        }
    }

    private static void exch(long[] pq, int i, int j) {
        long swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
    }
}

CTCI Challange, DAY 9

Day 9:- 
Problem statement:- Tries: Contacts

Note:-
Updated version below..
 
Tries is new concept,I gone through the Princeton algorithms lectures and got a picture of what this data structure is all about.

Implemented the logic using the existing algorithms given by Princeton.

import java.util.*;

/**
 * @author vikram.shanbogar@gmail.com
 * on 8/2/2017.
 */
public class Tries<Value> {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        TrieST<Integer> tries = new TrieST();
        List<Integer> list = new ArrayList<>();
        for (int a0 = 0; a0 < n; a0++) {
            String op = in.next();
            String contact = in.next();
            if (op.equals("add")) {
                tries.put(contact, a0);
            }
            if (op.equals("find")) {
                int count = 0;
                for (Object s : tries.keysWithPrefix(contact))
                    count++;
                System.out.println(count);
            }
        }
    }

    public static class TrieST<Value> {
        private static final int R = 256;        // extended ASCII


        private Node root;      // root of trie
        private int n;          // number of keys in trie

        // R-way trie node
        private static class Node {
            private Object val;
            private Node[] next = new Node[R];
        }

        /**
         * Initializes an empty string symbol table.
         */
        public TrieST() {
        }


        /**
         * Returns the value associated with the given key.
         *
         * @param key the key
         * @return the value associated with the given key if the key is in the symbol table
         * and {@code null} if the key is not in the symbol table
         * @throws IllegalArgumentException if {@code key} is {@code null}
         */
        public Value get(String key) {
            if (key == null) throw new IllegalArgumentException("argument to get() is null");
            Node x = get(root, key, 0);
            if (x == null) return null;
            return (Value) x.val;
        }

        /**
         * Does this symbol table contain the given key?
         *
         * @param key the key
         * @return {@code true} if this symbol table contains {@code key} and
         * {@code false} otherwise
         * @throws IllegalArgumentException if {@code key} is {@code null}
         */
        public boolean contains(String key) {
            if (key == null) throw new IllegalArgumentException("argument to contains() is null");
            return get(key) != null;
        }

        private Node get(Node x, String key, int d) {
            if (x == null) return null;
            if (d == key.length()) return x;
            char c = key.charAt(d);
            return get(x.next[c], key, d + 1);
        }

        /**
         * Inserts the key-value pair into the symbol table, overwriting the old value
         * with the new value if the key is already in the symbol table.
         * If the value is {@code null}, this effectively deletes the key from the symbol table.
         *
         * @param key the key
         * @param val the value
         * @throws IllegalArgumentException if {@code key} is {@code null}
         */
        public void put(String key, Value val) {
            if (key == null) throw new IllegalArgumentException("first argument to put() is null");
            if (val == null) delete(key);
            else root = put(root, key, val, 0);
        }

        private Node put(Node x, String key, Value val, int d) {
            if (x == null) x = new Node();
            if (d == key.length()) {
                if (x.val == null) n++;
                x.val = val;
                return x;
            }
            char c = key.charAt(d);
            x.next[c] = put(x.next[c], key, val, d + 1);
            return x;
        }

        /**
         * Returns the number of key-value pairs in this symbol table.
         *
         * @return the number of key-value pairs in this symbol table
         */
        public int size() {
            return n;
        }

        /**
         * Is this symbol table empty?
         *
         * @return {@code true} if this symbol table is empty and {@code false} otherwise
         */
        public boolean isEmpty() {
            return size() == 0;
        }

        /**
         * Returns all keys in the symbol table as an {@code Iterable}.
         * To iterate over all of the keys in the symbol table named {@code st},
         * use the foreach notation: {@code for (Key key : st.keys())}.
         *
         * @return all keys in the symbol table as an {@code Iterable}
         */
        public Iterable<String> keys() {
            return keysWithPrefix("");
        }

        /**
         * Returns all of the keys in the set that start with {@code prefix}.
         *
         * @param prefix the prefix
         * @return all of the keys in the set that start with {@code prefix},
         * as an iterable
         */
        public Iterable<String> keysWithPrefix(String prefix) {
            Queue<String> results = new PriorityQueue<>();
            Node x = get(root, prefix, 0);
            collect(x, new StringBuilder(prefix), results);
            return results;
        }

        private void collect(Node x, StringBuilder prefix, Queue<String> results) {
            if (x == null) return;
            if (x.val != null) results.offer(prefix.toString());
            for (char c = 0; c < R; c++) {
                prefix.append(c);
                collect(x.next[c], prefix, results);
                prefix.deleteCharAt(prefix.length() - 1);
            }
        }

        /**
         * Returns all of the keys in the symbol table that match {@code pattern},
         * where . symbol is treated as a wildcard character.
         *
         * @param pattern the pattern
         * @return all of the keys in the symbol table that match {@code pattern},
         * as an iterable, where . is treated as a wildcard character.
         */
        public Iterable<String> keysThatMatch(String pattern) {
            Queue<String> results = new PriorityQueue<>();
            collect(root, new StringBuilder(), pattern, results);
            return results;
        }

        private void collect(Node x, StringBuilder prefix, String pattern, Queue<String> results) {
            if (x == null) return;
            int d = prefix.length();
            if (d == pattern.length() && x.val != null)
                results.offer(prefix.toString());
            if (d == pattern.length())
                return;
            char c = pattern.charAt(d);
            if (c == '.') {
                for (char ch = 0; ch < R; ch++) {
                    prefix.append(ch);
                    collect(x.next[ch], prefix, pattern, results);
                    prefix.deleteCharAt(prefix.length() - 1);
                }
            } else {
                prefix.append(c);
                collect(x.next[c], prefix, pattern, results);
                prefix.deleteCharAt(prefix.length() - 1);
            }
        }

        /**
         * Returns the string in the symbol table that is the longest prefix of {@code query},
         * or {@code null}, if no such string.
         *
         * @param query the query string
         * @return the string in the symbol table that is the longest prefix of {@code query},
         * or {@code null} if no such string
         * @throws IllegalArgumentException if {@code query} is {@code null}
         */
        public String longestPrefixOf(String query) {
            if (query == null) throw new IllegalArgumentException("argument to longestPrefixOf() is null");
            int length = longestPrefixOf(root, query, 0, -1);
            if (length == -1) return null;
            else return query.substring(0, length);
        }

        // returns the length of the longest string key in the subtrie
        // rooted at x that is a prefix of the query string,
        // assuming the first d character match and we have already
        // found a prefix match of given length (-1 if no such match)
        private int longestPrefixOf(Node x, String query, int d, int length) {
            if (x == null) return length;
            if (x.val != null) length = d;
            if (d == query.length()) return length;
            char c = query.charAt(d);
            return longestPrefixOf(x.next[c], query, d + 1, length);
        }

        /**
         * Removes the key from the set if the key is present.
         *
         * @param key the key
         * @throws IllegalArgumentException if {@code key} is {@code null}
         */
        public void delete(String key) {
            if (key == null) throw new IllegalArgumentException("argument to delete() is null");
            root = delete(root, key, 0);
        }

        private Node delete(Node x, String key, int d) {
            if (x == null) return null;
            if (d == key.length()) {
                if (x.val != null) n--;
                x.val = null;
            } else {
                char c = key.charAt(d);
                x.next[c] = delete(x.next[c], key, d + 1);
            }

            // remove subtrie rooted at x if it is completely empty
            if (x.val != null) return x;
            for (int c = 0; c < R; c++)
                if (x.next[c] != null)
                    return x;
            return null;
        }
    }
}

Note:- updated on 22/8/17
Today got time to work on CTCI backlogs.Completed the tries problem.

package vikram.HR;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class TrieNode1 {
    char c;
    HashMap<Character, TrieNode1> children = 
            new HashMap<Character, TrieNode1>();
    boolean isLeaf;
    public int size;

    public TrieNode1() {
    }

    public TrieNode1(char c) {
        this.c = c;
    }
}

class Trie {
    private TrieNode1 root = new TrieNode1();

    public void insert(String word) {
        HashMap<Character, TrieNode1> children = root.children;

        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);

            TrieNode1 t;
            if (children.containsKey(c)) {
                t = children.get(c);
            } else {
                t = new TrieNode1(c);
                children.put(c, t);
            }

            children = t.children;

            //set leaf node            if (i == word.length() - 1)
                t.isLeaf = true;
            t.size++;
        }
    }

    // Returns if the word is in the trie.    

public boolean search(String word) {
        TrieNode1 t = searchNode(word);

        if (t != null && t.isLeaf)
            return true;
        else            return false;
    }

    // Returns if there is any word in the trie    

// that starts with the given prefix.   

       public int startsWith(String prefix) {
        TrieNode1 val = searchNode(prefix);
        if (val == null)
            return 0;
        else            return val.size;
    }

    public TrieNode1 searchNode(String str) {
        Map<Character, TrieNode1> children = 
                root.children;
        TrieNode1 t = null;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (children.containsKey(c)) {
                t = children.get(c);
                children = t.children;
            } else {
                return null;
            }
        }

        return t;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Trie t = new Trie();
        for (int a0 = 0; a0 < n; a0++) {
            String op = in.next();
            String contact = in.next();
            if (op.equals("add")) {
                t.insert(contact);
            } else {
                System.out.println(t.startsWith(contact));
            }
        }
    }
}