The following Java class shows how to implement Selection sort in Java.

/**
 * Insertion Sort Implementation In Java
 * 
 * @author zparacha
 *
 * @param <T>
 */

package com.zparacha.algorithms;

import java.util.Arrays;

public class InsertionSort<T extends Comparable<T>> {
	int size;
	T[] data;

	public InsertionSort(int n) {
		data = (T[]) new Comparable[n];
	}

	public void insert(T a) {
		data[size++] = a;

	}

	public boolean isSmaller(T x, T y) {
		return x.compareTo(y) < 0;
	}

	public void swap(int i, int j) {
		T temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}

	public void sort() {
		for (int i = 1; i < size; i++) {
			for (int j = i; j > 0 && isSmaller(data[j], data[j - 1]); j--) {
				swap(j, j - 1);
			}
		}
	}

	public static void main(String[] args) {
		InsertionSort<Integer> is = new InsertionSort<>(5);
		is.insert(3);
		is.insert(1);
		is.insert(5);
		is.insert(4);
		is.insert(2);
		System.out.println(Arrays.toString(is.data));
		is.sort();
		System.out.println(Arrays.toString(is.data));
	}
}

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

https://en.wikipedia.org/wiki/Selection_sort

Following Java class shows how to implement Selection sort in Java.

package com.zparacha.algorithms;

import java.util.Arrays;

/**
 * Selection Sort Implementation In Java
 * 
 * @author zparacha
 *
 * @param <T>
 */
public class SelectionSort<T extends Comparable<T>> {
	int size;
	T[] data;

	public SelectionSort(int n) {
		data = (T[]) new Comparable[n];
	}

	public void insert(T a) {
		data[size++] = a;
	}

	public boolean isSmaller(T x, T y) {
		return x.compareTo(y) < 0;
	}

	public void swap(int i, int y) {
		T temp = data[i];
		data[i] = data[y];
		data[y] = temp;
	}

	public void selectionSort() {
		for (int i = 0; i < size; i++) {
			int minIndex = i; //set the minIndex to current element
			for (int j = i + 1; j < size; j++) {
				//compare the value of current element with remaining elements in 
				// the array. If a value smaller than current value is found, set the
				//minIndex to that value's index and keep comparing until end of 
				//array. 
				if (isSmaller(data[j], data[minIndex])) {
					minIndex = j;
				}
			}
			//if minIndex is different than the current value, it means 
			//that current value is not the smallest, swap it with the smallest value. 
			if (minIndex != i) {
				swap(i, minIndex);
			}
		}
	}

	public static void main(String[] args) {
		SelectionSort<Integer> ss = new SelectionSort<>(5);
		ss.insert(4);
		ss.insert(3);
		ss.insert(1);
		ss.insert(5);
		ss.insert(2);
		System.out.println(Arrays.toString(ss.data));
		ss.selectionSort();
		System.out.println(Arrays.toString(ss.data));
	}
}

The example method I am sharing can be used to compute the height of any tree. So even if you have a non-binary tree, you can use this method to get the tree height.

Since we are talking about a non-Binary tree, a node can have more than 2 children hence we have to declare the children as a list in the Node class. Here is the Node class.

class Node<E> {
	int height;
	Node<E> parent;
	List<Node<E>>childern;
}

As you can see we have a field of type Node to reference the parent node, and a list of Nodes to reference the children of this node.

Using this class definition with recursion we can compute the height of a tree (including non-Binary tree).

getTreeHeight:

public int getTreeHeight(Node<Integer> root) {
   int height = 0;
    if (root == null ) {
	return height;
    }
    if (root.childern == null) {
	return 1;
  }

   for (Node<Integer> child : root.childern) {
	height = Math.max(height, getTreeHeight(child));
  }
   return height + 1;
}

The following example shows how you can do it.

long startTime = System.nanoTime();
System.out.println("Random string = " + getRandomAlphNumeircString(n));
long endTime = System.nanoTime();
double runTime = (endTime-startTime)/10000000000.0;
NumberFormat formatter = new DecimalFormat("#00.0000000000000000");
System.out.println("RumTIme = "+ formatter.format(runTime));

Before calling the method for which we want to measure the execution time we record the current time in a local variable (startTime), we then call the method. After the method is complete we call System.nanoTime() to get the current time again. To find the elapsed time we subtract startTime from endTime and divide the result by 1 billion (to convert nanoseconds into seconds).

To display the elapsed time in a more readable format we used NumberFormat class, otherwise, since the values will be too small you will get the result in scientific notation.

/** isSSNValid: Validate Social Security number (SSN) using Java regex.
* This method checks if the input string is a valid SSN.
* @param email String. Social Security number to validate
* @return boolean: true if social security number is valid, false otherwise.
*/
 public static boolean isSSNValid(String ssn){
boolean isValid = false;
 /*SSN format xxx-xx-xxxx, xxxxxxxxx, xxx-xxxxxx; xxxxx-xxxx:
         ^\\d{3}: Starts with three numeric digits.
	[- ]?: Followed by an optional "-"
	\\d{2}: Two numeric digits after the optional "-"
	[- ]?: May contain an optional second "-" character.
	\\d{4}: ends with four numeric digits.

        Examples: 879-89-8989; 869878789 etc.
*/

//Initialize regex for SSN. 
String expression = "^\\d{3}[- ]?\\d{2}[- ]?\\d{4}$";
CharSequence inputStr = ssn;
Pattern pattern = Pattern.compile(expression);
Matcher matcher = pattern.matcher(inputStr);
if(matcher.matches()){
isValid = true;
}
return isValid;
}

This method will return true if the given String matches one of these SSN formats xxx-xx-xxxx, xxxxxxxxx, xxx-xxxxxx, xxxxx-xxxx:

Social Security RegEx Explained:

A String would be considered a valid Social Security Number (SSN) if it satisfies the following conditions:

^\\d{3}: Starts with three numeric digits.

[- ]?: Followed by an optional “-“

\\d{2}: Two numeric digits after the optional “-“

[- ]?: May contain an optional second “-” character.

\\d{4}: ends with four numeric digits.

Look at the code, then read through the explanation that follows

public static boolean isStringANumber(String str) {
		String regularExpression = "[-+]?[0-9]*\\.?[0-9]+$";
		Pattern pattern = Pattern.compile(regularExpression);
		Matcher matcher = pattern.matcher(str);
		return matcher.matches();
				
	}

Regular Expression Explained:

A String would be a numeric value if it satisfies following conditions:

1. [-+]? can begin with an optional + or – sign
2. [0-9]* may have any number of digits between 0 and 9.
3. \\.? may have a decimal point
4. [0-9]$ the String must end with a digit.

Here is the code

package com.zparacha.utils;

import java.util.Random;
import java.util.Scanner;

public class StringUtilities {


	
	/**
	 * 
	 * @param n
	 *            Desired Length of random string
	 * @return
	 */
	public static String getRandomAlphNumeircString(int n) {
		// Get a n-digit multiplier of 10
		int maxDigit = (int) Math.pow(10, n - 2);
		Random random = new Random();
		/*
		 * Get a random character by getting a number from 0 t0 26 and then adding an
		 * 'A' to make it a character
		 * 
		 */
		char randomCharacter = (char) (random.nextInt(26) + 'A');
		/*
		 * Add 1*maxDigit to ensure that the number is equals to or greater than minimum
		 * value nextInt() method will return the number between 0 and 9*maxDigit
		 */
		int randomNumber = 1 * maxDigit + random.nextInt(9 * maxDigit);
		return String.valueOf(randomCharacter) + randomNumber;

	}
	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		System.out.print("Enter desired lenght of random string: ");
		int n = in.nextInt();
		in.nextLine();
		System.out.println("Random string = " + getRandomAlphNumeircString(n));

	}
}

Method getRandomAlphNumeircString accepts a numeric parameter for the desired length of the String.  Using the max length value it creates a variable maxDigit to a 10 muliple number.

It then calls Random.nextInt() method to get a number between 0 and 26 (number of English alphabets) and then adds an ‘A’ to convert that number into a character.

Next, it generates a Random number by calling Random.nextInt() method again.

Finally, it concatenates random character and the random number to generate a random alpha-numeric String.

main method is included to test getRandomAlphNumeircString method.

A sample run produced following output.

Enter desired lenght of random string: 10
Random string = W742681415

Consider the following example.

try (Scanner in = new Scanner(System.in)) {
	System.out.print("Enter Item ID: ");
	String itemID = in.nextLine();
	System.out.print("Enter item price: ");
	double price = in.nextDouble();
	System.out.println("Price of item " + itemID + " is $" + price);
} catch (Exception e) {
	e.printStackTrace();
}

As expected the output from this code will look something like:

Enter Item ID: XY1234
Enter item price: 99.99
Price of item XY1234 is $99.99

Everything worked as expected. The program prompted the user to enter an item ID and price. It read the values and then displayed them on console correctly.  Now, let’s see what happens if we ask the user to enter the price first followed by item ID.

try (Scanner in = new Scanner(System.in)) {
	System.out.print("Enter item price: ");
	double price = in.nextDouble();
	System.out.print("Enter Item ID: ");
	String itemID = in.nextLine();
	System.out.println("Price of item " + itemID + " is $ " + price);
} catch (Exception e) {
			e.printStackTrace();
}

This version resulted in a bizarre output.

Enter item price: 85.79
Enter Item ID: Price of item  is $ 85.79

What happened here? The program didn’t wait for the user to enter item ID. After prompting the user to enter the item ID, it right away printed the final message with a blank item ID.

Understanding Scanner.getDouble() and Scanner.getInt()

What caused this behavior? To solve this mystery we have to understand how Scanner.getDouble() or Scanner.getInt() methods work.  Basically, Scanner’s get methods read the input character by character instead of reading the entire line at once. getDouble and getInt methods read input until they reach a non-numeric character. In this example, the user entered 99.99 and then hit enter (“\n“). So the character sequence would be 99.99\n.  The method getDouble() reads the characters up to the last “9”. Since the next character is a non-numeric value (\n), the method stopped and returned the value 85.79 to be saved in the price variable. That left \n character in the buffer. Next, the program called nextLine() method. This method reads the input until it reaches the newline character (\n). Since the input stream had the \n character from the last input, the method reads it and returns immediately without allowing the user to input the ID.

To overcome this issue you have two options.

1. Always call nextLine() method after calling nextInt() or nextDouble() method to consume line feed.
2. Always read command line input using nextLine() method and then converts numeric values from String to appropriate numeric type.

try (Scanner in = new Scanner(System.in)) {
			System.out.print("Enter item price: ");
			double price = in.nextDouble();
			in.nextLine();
			System.out.print("Enter Item ID: ");
			String itemID = in.nextLine();
			System.out.println("Price of item " + itemID + " is $ " + price);
		} catch (Exception e) {
			e.printStackTrace();
		}

Which gives correct results.

Enter item price: 85.79
Enter Item ID: XY1234
Price of item XY1234 is $ 85.79

try (Scanner in = new Scanner(System.in)) {
			System.out.print("Enter item price: ");
			String priceStr = in.nextLine();
			double price = Double.valueOf(priceStr);
			System.out.print("Enter Item ID: ");
			String itemID = in.nextLine();
			System.out.println("Price of item " + itemID + " is $ " + price);
		} catch (Exception e) {
			e.printStackTrace();
		}

Enter item price: 85.99
Enter Item ID: AB2314
Price of item AB2314 is $ 85.99

Personally, I prefer the first approach.

The == operator checks the reference of two objects, i.e. it checks if both operands are the same objects. The Object.equals method, on the other hand, compares the value of the two operands.

Consider following example

package com.zparacha.utils; 
public class StringUtilities { 
  public static void main(String args[]) { 
     String a = new String("ABC"); 
     String b = "abc"; 
     String c = "abc"; 
     System.out.println("a = " + a + ", b = " + b + ", c = " + c); 
     System.out.println("a==b is " + (a==b)); 
     System.out.println("a==c is " + (a==c)); 
     System.out.println("b==c is " + (b==c)); 
     System.out.println("a.equals(c) is " + a.equals(c)); 
     System.out.println("b.equals(c) is " + b.equals(c)); 
  } 
}

Here is the output of this program

a = abc, b = abc, c = abc
a==b is false
a==c is false
b==c is true
a.equals(c) is true
b.equals(c) is true

As you can see, all three String variables have the same value of “abc”, but the two comparison methods gave different results.

It depends on how the object is initialized. If a String object is created using String literal (e.g.; String b = “abc”; and String c = “abc”;), it may be interned. Interned means that the character sequence "abc"will be stored at a specific memory location, and whenever the same literal is used again, the JVM will not create a new String object instead it will use the reference of the first String object created with the same value. This is the most efficient way of creating String objects.

If you use a String constructor (like  String a = new String("abc");), Java will always create a new object. Then, if you try to compare this String with another String using the == operator, you will always get a “false” return, since you are checking references to two distinct objects.

So, it is highly recommended to use String literals to create new String objects for efficiency and use Object.equals method to compare String to ensure that you get the expected results.