Boot software development

Dijkstra's algorithm

Dijkstra's algorithm shortest path algorithm is one of the most commonly used algorithms for finding short distances between two nodes. This article list down some of the important points for this algorithm and list down some of the useful contents available online.

Important Points

It does not work if the edges have negative weights. It is used to find shortest path between source and destination in a graph. Real life uses includes Map, Network communication.

Complexity

The complexity of this algorithm depends on the data structure used. For a graph G with V vertices and E edges, For Adjecency Matrix : Complexity is O(V**2) For Adjecency List and using Priority Queue with O(n) for sorting : O(E + VlogV)

References

Wikipedia

Algorithm with Visual Intro

Dijkstras Algo in Java

Dijkstras Algorithm with Java Code

An array is monotonic if it is either monotone increasing or monotone decreasing. More formally if all the elements are either in increasing order or decreasing order. That is for an given array nums[], it is monotone increasing if all i <= j, nums[i] <= nums[j]. it is monotone decreasing if for all i <= j, nums[i] >= nums[j]. In in article we will see how to efficiently decide if a given array is monotonic or not.

Examples

Examples of Monotonic arrays
Increasing monotonic array:
[1, 2, 20, 30]
[1, 2, 20, 20, 30]
decreasing monotonic array:
[66, 50, 40, 4]
[66, 50, 40, 40]

Algorithm

Iterate over the array and keep track of the first nonequal comparison to a variable signal. And once the signal is set check if holds true for the next set of array items.

Implementation

Implementation of the monotonic array is not very tough. Here we will see how to implement it in a single pass (single iteration of the input array) in Java.

MonotonicArray

Following Java, the class implement is a monotonic method that checks if an array is monotonic in a single pass.

public class MonotonicArray {
	public boolean isMonotonic(int[] nums) {
		int signal = -1; // -1 = not set, 0 = increasing, 1 = decreasing
		// iterate over the array till the arry.length-1 from 0
		for (int i = 0; i < nums.length - 1; i++) {
			// if signal is not initialized and we see either increasing or decreasing array
			// initialize it accordingly
			if (signal == -1) {
				if (nums[i] < nums[i + 1]) {
					signal = 0; // increasing
				} else if (nums[i] > nums[i + 1]) {
					signal = 1; // decreasing
				}
			} else {
				// once the signal is already initialized
				// then check if for other elements it holds true or not
				if (signal == 0 && nums[i] > nums[i + 1]) {
					return false;
				}
				if (signal == 1 && nums[i] < nums[i + 1]) {
					return false;
				}
			}
		}
		return true;
	}
}

Code Complexity

Runtime complexity: O(n) where n is the number of elements in the array. As we are iterating the array once. Space complexity: O(1) as we are not using extra storage

References

Leetcode Monotonic Array

Monotonic array In Python

Another implementation in Java

Java TreeMap, TreeSet, and PriorityQueue have something in common, they all maintain some kind of ordering.

HashSet is implemented using a HashMap, TreeSet is implemented using a TreeMap. The TreeMap itself is implemented using a red-black tree which is a self-balancing binary search tree. On the other hand, a HashMap has an average time complexity of O(1) for put(), contains() and remove() operations. The worst-case time complexity for those operations is O(log n) since Java 8, and O(n) before that. Big O complexities are as follows.

PriorityQueue

log(n) operations: offer(), poll(), remove(), add()
O(1) opearations: peek(), size()
O(n) operations: remove(object), contains(object)

HashMap

log(n) operations: get(), put(), contains(), remove()
O(n) operations: clone(), equals(), hashCode(), toArray(), toString()
O(1) opearations: clear(), isEMpty(), size()

TreeMap

log(n) operations: get(), put(), containsKey() and remove()
O(n) operations: clone(), equals(), hashCode(), toArray(), toString(), containsValue()
O(1) opearations: clear(), isEMpty(), size()

TreeSet

log(n) operations: add(), contains(), remove()
O(1) opearations: clear(), first(), isEMpty(), size(), last(), pollFirst(), pollLast()
O(n) operations: clone(), equals(), hashCode(), toArray() and toString()

Java un-initializing Array

We can create and initialize array using different statements, but what will be the content of the arrays if we cont initialize the array after creating it?

Let's create arrays of different data types and then print the content of each array to see what they contain.

Create Different Arrays

Create different arrays of primitive data types and one Object type (Integer)

byte rollNums1[] = new byte[10];
short rollNums2[] = new short[10];
int rollNums3[] = new int[10];
long rollNums4[] = new long[10];
float rollNums5[] = new float[10];
double rollNums6[] = new double[10];
char rollNums7[] = new char[10];
boolean rollNums8[] = new boolean[10];
Integer rollNums9[] = new Integer[10];

Iterate the arrays and print the content.

    byte rollNums1[] = new byte[10];
    System.out.println("\nbyte array");
    for (byte i : rollNums1) {
      System.out.print(i + ", ");
    }
    short rollNums2[] = new short[10];
    System.out.println("\nshort array");
    for (short i : rollNums2) {
      System.out.print(i + ", ");
    }
    
    int rollNums3[] = new int[10];
    System.out.println("\nint array");
    for (int i : rollNums3) {
      System.out.print(i + ", ");
    }
    
    long rollNums4[] = new long[10];
    System.out.println("\nlong array");
    for (long i : rollNums4) {
      System.out.print(i + ", ");
    }
    
    float rollNums5[] = new float[10];
    System.out.println("\nfloat array");
    for (float i : rollNums5) {
      System.out.print(i + ", ");
    }
    
    double rollNums6[] = new double[10];
    System.out.println("\ndouble array");
    for (double i : rollNums6) {
      System.out.print(i + ", ");
    }
    
    
    char rollNums7[] = new char[10];
    System.out.println("\nchar array");
    for (char i : rollNums7) {
      System.out.print(i + ", ");
    }
    
    boolean rollNums8[] = new boolean[10];
    System.out.println("\nboolean array");
    for (boolean i : rollNums8) {
      System.out.print(i + ", ");
    }
    
    Integer rollNums9[] = new Integer[10];
    System.out.println("\nInteger array");
    for (Integer i : rollNums9) {
      System.out.print(i + ", ");
    }

Output

byte array 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

short array 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

int array 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

long array 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

float array 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
double array 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,

char array , , , , , , , , , ,

boolean array false, false, false, false, false, false, false, false, false, false,

Integer array null, null, null, null, null, null, null, null, null, null,

Conclusion

If the array is just created and not initialized with data then the content of the arrays depends on the data type.
For byte, short, int, long it is 0
For float and double it is 0.0
for char it is '' (empty character)
for boolean it is false
for Integer or any other object, it is null
The value of the array depends on the type of the array and a default value for the respective data types.

References

Java datatypes default value

Array Initialize

An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. Each item in the array can be accessed with its index very efficiently. In this post we examine different ways to create and initialize arrays in java

Creating array of specific size and populating using for loop

We create a new int array of size 10 and set values using for loop.

//initialize array of size 10 of type int
int rollNums[] = new int[10];
//iterate from 0 to the last index of the array and set values
for (int i = 0; i < rollNums.length; i++) {
      rollNums[i] = i + 1;
}

Assigning value while creating the array.

Here we create a new int array and pass the values in the curly braces.

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

Assigning value while creating the array without specifying array type.

Even shorter versions just assign values in the curly braces.

int rollNums[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

Using Arrays.setAll (Lambda)

First, create an int array of size 10, then using setAll to set the value of the corresponding indices. setAll takes IntUranaryOperator as the second argument. IntUranaryOperator is a functional interface and we can use lambda expressions to implement it.

int rollNums[] = new int[10];
Arrays.setAll(rollNums, p -> p + 1);

Using Arrays.setAll (Anonymous Class)

Same as above but rather than lambda expression implementing it as Anonymous class and implementing applyAsInt method.

int rollNums[] = new int[10];
Arrays.setAll(rollNums, new IntUnaryOperator () {
      @Override
      public int applyAsInt(int operand) {
        return operand + 1;
 }} );

Arrays.copyOf

We can also copy contents of an existing array to a different array of the same type.

int rollNums2[] = Arrays.copyOf(rollNums, rollNums.length);

Summary

We can create an array in java using a new operator and specify size while creating.
We can also specify the content of the array and java will create an array of sufficient size.
When we create an array and does not initialize then the content of the array is null if the type of the array is of type object
and 0 if the type is int.

Default Method in Java

The default method in Interfaces was introduced in Java 8. It allows the interface to implement a method in the interface which is inherited by implementing classes.

What are default methods?

Before Java 8 methods in the interface could have only public and abstract modifiers for methods and public, static and for fields public and static or blank (blank means public and static field).

Java 5

Following are two interfaces in Java 5, the first one is valid and the second one is not.

Valid Interface in Java 5

interface Java5Interface {
	public static int four = 4;
	int five = 5; // implicitly public static

	public abstract void welcome();
	public void sayHi();
	void bye();
}

Invalid Interface in Java 5

interface Java5Invalid {
	private int six = 6;            //illegal only public static and final is permitted
	private void cleanuup(); // illegal only public and abstract is permitted
}

As you can see for fields only public, static, and final modifiers are allowed. If nothing is mentioned then also all fields in Java 5 is public static and final implicitly. For methods, we can have only public and abstract as modifiers.

Java 8 and onwards

Starting Java 8 methods in the interface can have the following modifiers public, private, abstract, default, static, strictfp. Nothing changes for fields, fields can still have public, static, final modifiers. In the following example, we have a Greetings Interface with two default methods greet and openDoor respectively. This interface also has one static method lockdoor.

Interface Greetings in Java 8

interface Greetings {
	
	public default void greet() {
		openDoor();
		sayHi();
		sayBye();
		closeDoor();
	}
	
	default void openDoor() {
		//open the door
	}
	
	void sayHi();
	
	void sayBye();
	
	private void closeDoor() {
		lockDoor();
	}

	static void lockDoor() {
		//lock door implementation
	}
}

The benefit of having a default method is that now the interface can provide a default implementation of methods through the default modifier. For instance, the interface Greetings provided a default implementation for method greet(). Also the later we can add more default, private or static methods to the Interface without breaking binary compatibility meaning implementing classes don't need to do any modification to be able to compile and run successfully.

Importat Points

default methods are public.
default methods are inherited by implementation classes.
default methods can be overridden by implementation classes.
a default method can add more functionality to the Interface without breaking binary compatibility.
static methods are also allowed which are Interface level methods and cannot be overridden by subclasses.
Java 8 methods can have public, private, abstract, default, static, and strictfp.

References

Oracle Java Docs Default Methods

Convert Java Set to List

In this article, we will go through 4 different ways to convert java Set to Java List object.

Java Set Object

mySet is the Set object which contains 4 Strings.

Set  mySet = new HashSet(Arrays.asList("Red", "Yellow", "Green", "Blue"));

Using Constructor

List  myList = new ArrayList(mySet);

Using addAll

Using the addAll method we can add all the items in the set to list-objects.

List  myList2 = new ArrayList();
myList2.addAll(mySet);

Using for each

By using for each to loop though all the items in the Set we can add them one by one to the List.

List  myList3 = new ArrayList();
mySet.forEach(a->myList3.add(a));

Using Java Stream

List  myList4 = mySet.stream().collect(Collectors.toList());

Full source code

package myjava.work.general;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

public class JavaListFromSet {

	public static void main(String[] args) {
		Set<String> mySet = new HashSet<String>(Arrays.asList("Red", "Yellow", "Green", "Blue"));

		// Using Constructor
		List<String> myList = new ArrayList<String>(mySet);
		myList.forEach(a -> System.out.println(a));

		// Using addAll
		List<String> myList2 = new ArrayList<String>();
		myList2.addAll(mySet);
		myList2.forEach(a -> System.out.println(a));

		// Using For Each
		List<String> myList3 = new ArrayList<String>();
		mySet.forEach(a -> myList3.add(a));
		myList3.forEach(a -> System.out.println(a));

		// Using Stream
		List<String> myList4 = mySet.stream().collect(Collectors.toList());
		myList4.forEach(a -> System.out.println(a));

	}
}

In this article, we will examine different ways to write Comparators in java to sort the multidimensional arrays. Comparator is a functional interface in java.

java.util.Arrays class contains various utility methods to manipulate arrays one of the important methods is Sort. This method takes two parameters the array that needs to be sorted and the optional Comparator. If we don't pass the Comparator then the array will be sorted based on the natural ordering of the elements.

Sorting Array

Our Array

Let's say we want to represent multiple points with x,y coordinates in an array. The following represents one such example.

{ { 20, 25 },{ 10, 15 }, { 10, 25 }, { 20, 15 }}

We want to sort the array based on x and y-axis values.

Comparators

Comparator Implementation as a Class

Here we are implementing a Comparator called MultiDimArrayComparator and then we can use this comparator to sort Array

class MultiDimArrayComparator implements Comparator {
	@Override
	public int compare(int[] m, int[] n) {
		return m[0] == n[0] ? m[1] - n[1] : m[0] - n[0];
	}
}

Arrays.sort(arr, new MultiDimArrayComparator());

Comparator as an anonymous class

Here we are implementing Comparator as an anonymous class and providing a definition of compare method.

Arrays.sort(arr, new Comparator() {
	@Override
	public int compare(int[] m, int[] n) {
		return m[0] == n[0] ? m[1] - n[1] : m[0] - n[0];
	}
});

Comparator as lambda expression (Java 8+)

Here we are implementing Comparator as a lambda function.

Arrays.sort(arr, (m, n) -> m[0] == n[0] ? m[1] - n[1] : m[0] - n[0]);

Full Example


public class ArraysSort {

	public static void main(String[] args) {
		int arr[][] = { { 20, 25 },{ 10, 15 }, { 10, 25 }, { 20, 15 }};

		int arr1[][] = arr;
		
		Arrays.sort(arr1, new MultiDimArrayComparator());
		System.out.println("Sorted Result");
		for (int[] x : arr1) {
			System.out.println(x[0] + " " + x[1]);
		}
		
		arr1 = arr;
		Arrays.sort(arr1, new Comparator<int[]>() {
			@Override
			public int compare(int[] m, int[] n) {
				return m[0] == n[0] ? m[1] - n[1] : m[0] - n[0];
			}
		});
		System.out.println("Sorted Result");
		for (int[] x : arr1) {
			System.out.println(x[0] + " " + x[1]);
		}

		arr1 = arr;
		Arrays.sort(arr1, (m, n) -> m[0] == n[0] ? m[1] - n[1] : m[0] - n[0]);
		System.out.println("Sorted Result");
		for (int[] x : arr1) {
			System.out.println(x[0] + " " + x[1]);
		}
	}

}

class MultiDimArrayComparator implements Comparator<int[]> {
	@Override
	public int compare(int[] m, int[] n) {
		return m[0] == n[0] ? m[1] - n[1] : m[0] - n[0];
	}
}

Running the code

Sorted Result 10 15 10 25 20 15 20 25 Sorted Result 10 15 10 25 20 15 20 25 Sorted Result 10 15 10 25 20 15 20 25

Conclusion

Here we implemented the same Comparator to sort two-dimensional arrays in three different styles.

Aws lambda handlers

While implementing AWS lambda functions in java we need to implement a Handler interface . The lambda environment will invoke the implementation of the Handler interface.

The Handler interface is a functional interface It has just one method that needs to be implemented. Broadly speaking AWS supports two different types of handlers. Following are the two interfaces that can be chosen to implement the handler.
The aws-lambda-java-core library defines two interfaces for handler methods.
com.amazonaws.services.lambda.runtime.RequestHandler
com.amazonaws.services.lambda.runtime.RequestStreamHandler

Choosing the right handler

Choosing the right Handler depends on the use cases. If we are working with simple Objects as input like String, Integer, Map, etc then RequestHandler is a good choice. If we want to work with more complicated input/output objects or we want to control the way the input and output get converted to String then RequestStreamHandler is the option.

RequestHandler

This interface is a generic interface. The handleRequest method takes two objects as input and also returns an object. The java runtime in the lambda environment deserializes and serializes input event and returned object from the method

public interface RequestHandler {
    /**
     * Handles a Lambda Function request
     * @param input The Lambda Function input
     * @param context The Lambda execution environment context object.
     * @return The Lambda Function output
     */
    public O handleRequest(I input, Context context);
}

RequestStreamHandler

This handler works with InputStream and OutputStream. It gives more control over how we want to perform the serialization/deserialization etc.

public interface RequestStreamHandler {
    /**
     * Handles a Lambda Function request
     * @param input The Lambda Function input stream
     * @param output The Lambda function output stream
     * @param context The Lambda execution environment context object.
     * @throws IOException
     */
    public void handleRequest(InputStream input, OutputStream output, Context context) throws IOException;
}

Summary

RequestStreamHandler : If we need to customize the serialization and deserialization process then RequestStreamHandler is the choice.
RequestHandler: It is the most suitable handler in most cases.

References

AWS Documentations

AWS samples github

How to download source for maven artifacts

Maven builds a project using its project object model (POM) and a set of plugins. Dependencies used by the project are mentioned in the pom.xml file. We can also get the dependencies artifact from maven along with source codes.

In the following section, we will cover two use cases
1) How to generate source code for third-party artifacts that my project is using

2) How to generate source code for my project

Download sources for third party artifacts

Executing the following command from the terminal will download the sources for all the artifacts for the project and will attach it to Eclipse IDE.

mvn eclipse:eclipse -DdownloadSources=true

Executing the following command from the terminal will download the sources for all the artifacts only, attaching the sources in the IDE with the binaries needed to be done seperately..
mvn dependency:sources -Dsilent=true

Generate source code for project

This command will generate the sources jar under the target folder for the project.

mvn source:jar install

Generating Random Number in Java

This article summarizes different ways to use the Random() class in java to generate bounded or unbounded random numbers. It also shows another important feature of the class that is using seed to generate same set of random numbers.

java.util.Random used used to generate bounded or unbounded random numbers. It supports specifying a seed which is used to set the internal state of the pseudorandom number generator. Random(): creates new random generator Random(long seed): creates new random generator using specified seed

Unbounded generate 5 random numbers

Following code prints 5 random numbers unbounded without any seed

public static void generateRadom() {
	System.out.println("\nPrinting 10 Random Numbers");
	Random generator = new Random();
	for (int i = 0; i < 5; i++) {
		System.out.print(generator.nextInt() + " ");
	}
}

Invocation 1

Printing 5 Random Numbers -1937915077 75383412 -901884443 1725835531 1371480362

Invocation 2

Printing 5 Random Numbers -1261854044 328673857 -1787159304 446964878 -283294822

Notice that in both the invocations the generated numbers are different. This is because we have not set any seed in the Random Class.

Random Bounded Number

Following method will generate 5 random numbers between 0 and 99

public static void generateRadomBounded() {
	System.out.println("\nPrinting 5 Random Numbers Between 0 and 99");
	Random generator = new Random();
	for (int i = 0; i < 5; i++) {
		System.out.print(generator.nextInt(100) + " ");
	}
}

Invocation 1

Printing 5 Random Numbers Between 0 and 99 25 95 13 60 67

Invocation 2

Printing 5 Random Numbers Between 0 and 99 17 10 21 96 15

Generate Random number bounded with a seed

Bellow function will generate bounded 5 random numbers but since we are setting a seed, if the seed is same on multiple invocation then each invocation will generate the same set of random numbers.

public static void generateRadomWithSeed(long seed) {
	System.out.println("\nPrinting 5 Random Numbers Between 0 and 99 with seed");
	Random generator = new Random(seed);
	for (int i = 0; i < 5; i++) {
		System.out.print(generator.nextInt(100) + " ");
	}
}

Invocation 1

Printing 5 Random Numbers Between 0 and 99 with seed 4 62 52 3 58 67

Invocation 2

Printing 5 Random Numbers Between 0 and 99 with seed 4 62 52 3 58 67

Summary

If we want to generate the same set of random numbers, we can set seed.
Test cases can use seed to make sure it gets same set of random numbers.
We can have bounded or unbounded random numbers.

Dijkstra's algorithm

Important Points

Complexity

References

Examples

Algorithm

Implementation

References

PriorityQueue

HashMap

TreeMap

TreeSet

Java un-initializing Array

References

Array Initialize

Default Method in Java

What are default methods?

Java 5

Java 8 and onwards

References

Convert Java Set to List

Sorting Array

Comparators

Full Example

Running the code

Conclusion

Aws lambda handlers

Choosing the right handler

References

How to download source for maven artifacts

Generating Random Number in Java

Popular Posts

Total Pageviews