Coding Interview - Java for Competitive Programming

Competitive programming and Coding interviews requires candidates to have strong command on any one programming language to translate the problem solution to code. Ideally it would be good to learn multiple programming languages, but because the "Language Agnostic" interview policy adopted by many tech companies, it is generally fruitless to spend time and effort to master multiple languages instead of focusing on one language & algorithms.

Java language is predominantly used by many for coding interviews due to its simple syntax and widely available help online. Below are some of the commonly used code, functions, hints, tricks which come handy during coding interview.

It is very important to note that different Java Online IDE's used for the interviews, which have different level of support for various standard library methods, hence be prepared to use alternative API's in order to carry out a given operation. Further in some interviews the interviewee is not even provided a java compiler, but just a simple text editor (Codepad). The interviewee is expected to run and debug the code in mind to determine correctness of the code which can be very challenging.

Basics

The default value of char primitive type variable is '\u0000'.

Swapping two variables without temp variable

a = a + b
b = a - b
a = a - b

Alternative approach to swap using XOR operation

x = x ^ y;
y = x ^ y;
x = x ^ y;

The break statement can be used to exit from a single loop. To break from multiple loops, use return statement or use break with a label for the outer loop as below.

outerloop:
  for (int i=0; i < 5; i++) {
    for (int j=0; j < 5; j++) {
        if (i * j > 6) {
            System.out.println("Breaking");
            break outerloop;
       }
        System.out.println(i + " " + j);
    }
  }

Pass By Value

Arguments in Java are always passed by value regardless of the original variable type. Each time a method is invoked, a copy for each argument is created in the stack memory and the copy version is passed to the method. A copy of variable is created in the stack for Primitive type. For Object type, a new reference or pointer is created inside the stack memory, which points to the actual object data. Hence any change to the reference inside the method is actually changing the reference of the copies and not the original references. When defining an arraylist or any collection in java, a reference is created inside the stack that points to multiple objects inside the heap memory. When the list is updated in the called method, then the original list reference can see the modification, since both references are pointing to the same object in memory.

String or Character operations

String Tokenization is used to process each token string one at a time.

import java.util.StringTokenizer;

StringTokenizer tokenizer = new StringTokenizer(str, ",");

while (tokenizer.hasMoreElements()) {
   tokens.add(tokenizer.nextToken());
}

The split() method of String is used to tokenize string and store result in array.

String[] info = someString.split("\\s+");            // split by space
String[] fragments = info[1].split("\\.");           // split by dot

Each alphabet character has a numeric value, for example numeric value of alphabet 'a' is 10.

Character.getNumericValue('a')

The substring() method returns a new string that is a substring of given string based on the passed indexes.

String substring(int beginIndex)
String substring(int beginIndex, int endIndex)

To reverse a String use the StringBuilder's reverse method as below.

new StringBuilder("String to reverse").reverse().toString();

Given a string containing a prefix word, return remaining substring.

if(string.startsWith(word)) {
   String remainingString = string.substring(word.length());
}

Math Library

The Math library is Java has very useful methods for performing any mathematical operations.

• Math.abs(num): Returns the absolute value.
• Math.ceil(num): Returns the smallest integer that is greater than or equal to the argument
• Math.floor(num): Returns the largest integer that is less than or equal to the argument.
• Math.max(a, b) and Math.min(c, d): Returns the largest and smallest of the two arguments respectively.
• Math.pow(a, b): Returns the value of the first argument raised to the power of the second argument. 
• Math.round(a): Returns the closed int or long (as per the argument)
• Math.random(): Returns a double value with a positive sign, greater than or equal to 0.0 and less than 1.0

Arrays

Print Array elements for debugging purposes

System.out.println(Arrays.toString(array));

Initialize or set all elements of array with one value

int[] intarry = new int[n+1];
Arrays.fill(intarry, -1);
Arrays.fill(intarry, 0);

Arrays can be copied in entirely or partially. The copyOf() method copies entire array, while the copyOfRange() method copies the subset of the specified array. The arrays can be of either primitive or object type.

Arrays.copyOf(original[], int newLength) and 
Arrays.copyOfRange(original[], int from, int to)

Array elements can be sorted using sort()

char[] charArray = string.toCharArray();
java.util.Arrays.sort(charArray);

The Arrays.binarySearch()(SET 1 | SET2) method is used to apply binary search on a sorted array.

Convert int array to List of Integer using IntStream.boxed() which box each element of the stream to an Integer.

List<Integer> list = Arrays.stream(arr)
                           .boxed()
                           .collect(Collectors.toList());

We can also use IntStream.of() to get IntStream from integer array.

List<Integer> list = IntStream.of(arr)    // returns IntStream
                            .boxed()
                            .collect(Collectors.toList());

Converting primitive integer array to an Integer array.

Integer[] boxedArray = Arrays.stream(arr).boxed().toArray(Integer[]::new);

Comparable and Comparator

Comparable object is capable of comparing itself with another object. The class (of element to be compared) itself must implements the java.lang.Comparable interface and override the compareTo method to compare its instances. Comparable compares "this" reference with the object specified in the compareTo(T o) method.

Comparator is an external class from the element type that is to be compared. Multiple separate classes implementing Comparator are created to compare by different members. The Collections.sort() method takes Comparator argument which invokes the compare() to sort objects. Comparator compares objects of two different class passed to the compare(T o1,T o2) method. Comparator also provides built in method such as naturalOrder() and reverseOrder() for natural ordering, reversed() to reverse ordering of the comparator.

Both compareTo() method of Comparable and compare() method of Comparator return integer with:

negative = first argument (or this object) is less than the (second) argument.

positive = first argument (or this object) is greater than the (second) argument.

zero = both objects are equal

If sorting of objects needs to be based on natural order then use Comparable whereas if sorting needs to be done on attributes of different objects, then use Comparator.

Collections and Lists

Sort collection elements using sort method

Collections.sort();

Sort collection elements using sort method

Collections.copy(List<T> dest, List<T> src)  copies specified collection.

The Collections.rotate() to rotate a collection or an array by a specified distance.

The Collections.frequency() method can be used to get the frequency of a specified element in a collection or an array.

The Collections.binarySearch() used to apply binary search on a collection based on comparators.

The Set collection does not have index, hence to get the first element from a Set we use Iterator.

HashSet<String> hashSet = new HashSet<String>();
Iterator<String> iter = hashSet.iterator();
if (iter.hasNext()) {
  String value = iter.next();
}

LinkedHashSet is subclass of HashSet that guarantees insertion-order.

SortedSet is a set in which the elements are stored in some sorted order.

NavigableSet extends the SortedSet interface with navigation (searching) methods.

Queue<E> extends the Collection interface to maintain a collection whose elements need to be processed in some way, i.e., insertion at one end and  removal at the other, usually as FIFO. E.g. PriorityQueue<E>, LinkedList<E>. 

The offer(E e) method of Queue Interface inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions. This method is preferable to add() method since this method does not throws an exception when the capacity of the container is full since it returns false.

The peek() method returns the object at the top of the current queue, without removing it, while the poll() method returns the object at the top and removes it. If the queue is empty then both peek() and poll() methods returns null. The remove() method is returns the top object from the queue and throws NoSuchElementException if the queue is empty.

The LinkedList implementation uses a doubly-linked list and, Insertions and deletions are very efficient. If frequent insertions and deletions occur inside a list, a LinkedList can be more efficient. LinkedList class also implements two other interfaces that allow it to be used for stacks and different kinds of queues.

PriorityQueue is implementation for a queue with priority ordering.

Deque<E> extends the Queue interface to maintain a queue whose elements can be processed at both ends. E.g. ArrayDeque<E>, LinkedList<E>. Deque inherits the offer method from Queue interface which is similar to offerLast. It allows to insert from the front and end, as well as remove from the front and the end from the constant time.

Deque<Integer> deque = new ArrayDeque<>();
deque.offerFirst(val);
deque.offerLast(val);

Maps

HashMap is implemented as a hash table, and there is no ordering on keys or values. HashMap is same as Hashtable, except that it is unsynchronized and permits nulls.

TreeMap is a map, sorted by the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used. It is an efficient way of sorting and storing the key-value pairs. The storing order maintained by the TreeMap must be consistent with equals just like any other sorted map, irrespective of the explicit comparators.

LinkedHashMap is a subclass of HashMap with an additional feature of preserving the insertion-order of the elements.

Print Map key-value pairs using java8

map.forEach((key, value) -> System.out.println(key + ":" + value));

Simple way to increment or update values in a Map.

map.put(sum, map.getOrDefault(sum, 0) + 1);

The putIfAbsent is handy method to only put the key and value if it doesn't exists.

map.putIfAbsent(first_key, value);

The ceilingEntry() method call returns an entry with the least key greater than or equal to key, or null if there is no such key.

Integer value = map.ceilingEntry(dollar - sum).getValue();

Threads

The Thread.start() method sets the thread in Ready-to-run state and makes it eligible for running. It waits for its turn to get CPU time. Once picked by thread scheduler it goes in Running state.

The sleep() causes the currently running thread to temporarily pause its execution and transit to the Sleeping state. The Sleep method does not relinquish any lock that the thread might have. After the sleep time, the thread transitions to the Ready-to-run state where it takes its turn to run again.

The yield() method may cause the current thread in the Running state to transit to the Ready-to-run state, relinquishing the CPU and giving other threads in the Ready-to-run state a chance to run. The thread is then at the mercy of the thread scheduler as to when it will run again, which is possible if there are no threads in the Ready-to-run state. The yield() method is an advisory method, and comes with no guarantees that the JVM will carry out the call's bidding. A call to the yield() method does not affect any locks that the thread might hold.

The wait() and notify() methods can only be executed on an object whose lock the thread holds (synchronized object). When a thread invokes the wait() method on the object whose lock it holds, it leaves the Running state and transits into Waiting-for notification state. The thread relinquishes the ownership of the object lock on which the wait() method was invoked, which can then be acquired by other threads. A thread in the Waiting-for-notification state is awakened by:

1. Another thread invokes the notify() method on the object of the waiting thread, and the waiting thread is selected as the thread to be awakened.
2. The waiting thread times out.
3. Another thread interrupts the waiting thread

The notify() method on an object relinquishes the lock from the current thread, and wakes up another thread waiting for the same object's lock. After being notified, the waiting thread first transits to the Blocked-for-lock-acquisition state to acquire the lock on the object, and then to the Ready-to-run state.

A thread can invoke the join() method on another thread in order to wait for the other thread to complete its execution before continuing. Thread calling join waits until other thread completes its execution, or waiting thread is timeout or interrupted.

Bit Manipulation

Check if the number is even or odd without using the % operator, with bitwise & operation.

System.out.println((a & 1) == 0 ?  "EVEN" : "ODD" );

Fast Multiplication or Division by 2.

n = n << 1;   // Multiply n with 2
n = n >> 1;   // Divide n by 2

0110 + 0110 is equivalent to 0110 * 2, which is equivalent to shifting 0110 left by 1.

0100 equals 4, and multiplying by 4 is just left shifting by 2. So we shift 0011 left by 2 to get 1100.

If we XOR a bit with its own negated value, we will always get 1. Therefore, the solution to a^(~a) will be a sequence of 1s.

~0 is a sequence of 1s, so ~0 << 2 is 1s followed by two Os. ANDing that with another value will clear the last two bits of the value.

x ^ 0s = x
x ^ 1s = ~x 
x ^ x = 0

x & 0s = 0
x & 1s = x 
x & x = x 

x | 0s = x
x | 1s = 1s 
x | x = x

A positive number is represented as itself while a negative number is represented as the two's complement of its absolute value (with a 1 in its sign bit to indicate that a negative value).

To find two's complement, we invert the bits in the positive representation and then add 1. For example, 3 is represented as 011 in binary. Flip the bits to get 100, add 1 to get 101, then prepend the sign bit (1) to get 1101.

In a logical right shift, we shift the bits and put a 0 in the most significant bit. It is indicated with a >>> operator.

In an arithmetic right shift, we shift values to the right but fill in the new bits with the value of the sign bit, which has the effect of(roughly) dividing by two. It is indicated by a > > operator.

The right shift operator ">>" keeps the sign bit intact i.e. first or most significant bit never lost, doesn't matter how many times you shift. On the other hand unsigned right shift operator ">>>" doesn't preserve sign of original number and fills the new place with zero, hence its also known as right shift with zero fill.

A sequence of all ls in a(signed) integer represents -1.

Binary bits is can be used instead of array of flags and enables to easily check if any flag is true. In order to check that no bits in the integer are 1, we just compare the integer to 0. There is actually a very elegant way to check that an integer has exactly one bit set to 1. If we subtract 1 from it and then AND it with the new number, we should get 0.

var1 = 010010
var2 = 000010

010010 & 111101 = 000000

The below method shifts 1 over by i bits, creating a value that looks like 00010000. By performing an AND with num, we clear all bits other than the bit at bit i. Finally, we compare that to 0. If that new value is not zero, then bit i must have a 1. Otherwise, bit i is a 0.

boolean getBit(int num, int i) {
   return ((num & (1 << i)) != 0);
}

SetBit shifts 1 over by i bits, creating a value like 00010000. By performing an OR with num, only the value at bit i will change. All other bits of the mask are zero and will not affect num.

int setBit(int num, int i) {
   return num | (1 << i);
}

An efficient trick to determine if a number is a power of 2:

boolean isPowerOfTwo(int x) {
     // First x in the below expression is for the case when x is 0
      return x!=0 && ((x&(x-1)) == 0);    
}

Regular Expressions

import java.util.regex.Matcher;
import java.util.regex.Pattern;

Pattern pattern = Pattern.compile("(.*)(\\d+)(.*)", Pattern.CASE_INSENSITIVE);
Matcher matcher = pattern.matcher("order is for QT3000!");
if (matcher.find( )) {
   System.out.println("Found value: " + matcher.group(0) );
   System.out.println("Found value: " + matcher.group(1) );
   System.out.println("Found value: " + matcher.group(2) );
}

I/O Operations

Get input from system input.

Scanner scanner = new Scanner(System.in);
String myString = scanner.next();
int myInt = scanner.nextInt();
scanner.close();

Dynamic Programming

Problems having optimal substructure and overlapping subproblems can be solved by dynamic programming, in which subproblem solutions are Memoized rather than computed again and again. The problems are usually solved in bottom-up manner, were smaller sub-problems are solved first, then the larger sub-problems are solved from them.

Memoization Matrix usually has the column with increasing number from 0 to final result, while the row has the elements which needs to selected for the optimal solution. The first column (and sometimes row) has the 0th column which is a hypothetical condition providing initial values with the matrix.

Levenshtein Distance

Determine the minimum edit distance for converting one string to another string

The Levenshtein distance is a string metric for measuring the difference between two sequences. It is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other. Here we first create a matrix with Source String as the columns while Destination String as rows. If the row and column character are same then no operation is needed and we directly copy the previous value of the diagonal cell as it is. If the row and column character is different then we find the minimum previous value from the top, side and diagonal, add 1 to it to get the final value as below.

Character Operations: Replace, Delete, Insert.

Below is the code for Levenshtein Distance.

static void editDP(String s1, String s2) 
    { 
        int l1 = s1.length(); 
        int l2 = s2.length(); 
        int[][] DP = new int[l1 + 1][l2 + 1]; 
  
        // initilize by the maximum edits possible 
        for (int i = 0; i <= l1; i++) 
            DP[i][0] = i; 
        for (int j = 0; j <= l2; j++) 
            DP[0][j] = j; 
  
        // Compute the DP matrix 
        for (int i = 1; i <= l1; i++) { 
            for (int j = 1; j <= l2; j++) { 
  
                // if the characters are same 
                // no changes required 
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) 
                    DP[i][j] = DP[i - 1][j - 1]; 
                else { 
  
                    // minimu of three operations possible 
                    DP[i][j] = min(DP[i - 1][j - 1], 
                                   DP[i - 1][j], DP[i][j - 1]) 
                               + 1; 
                } 
            } 
        }  
    } 

---

Coin Change Problem

When given coins of different denominations and a total amount, find out the number of combinations that make up that amount. Here the assumption is that there are unlimited supply of given coin denominations.

In the below table shows the P(n) for each number, which is the Number of ways representing an Integer as addition of positive Integers.

n	Ways	P(n)
1	(1)	1
2	(2), (1+1)	2
3	(3), (2+1), (1+1+1)	3
4	(4), (3+1), (2+2), (2+1+1), (1+1+1+1)	5

Lets see below example

Amount = 12

Coins = {1, 2, 5}

ForEach Coin in the given coin denominations i.e. {1, 2, 5}

If Amount >= Coin then

   Combinations[Amount] += Combinations[Amount - Coin]

First initialize the Combinations array with 0 value for all elements.

Combinations when Coin is 1

Set Combinations[0] = 1 when coin is 0, which means using coin 0 to achieve amount 0 there is only 1 combination.

Then we use the above logic to determine the next value of the combination when coin is 1 and amount is 1.

Combinations[1] = Combinations[1-1] + Combinations[1] = Combinations[0] + Combinations[1] = 1 + 0 = 1

Similarly, 

Combinations[2] = Combinations[2-1] + Combinations[2] = Combinations[1] + Combinations[2] = 1 + 0 = 1

0	1	2	3	4	5	6	7	8	9	10	11	12
1	1	1	1	1	1	1	1	1	1	1	1	1

Combinations when Coin is 2

When Amount is 0 or 1 and Coin is 2, the condition (Amount >= Coin) becomes false, so we skip for Amounts 0 and 1.

When Amount is 2 and Coin is 2, we have,

Combinations[2] = Combinations[2-2] + Combinations[2] = Combinations[0] + Combinations[2] = 1 + 1 = 2

The original value of Combinations[2] was 1 from above.

Similarly when Amount is 3 and Coin is 2, we have,

Combinations[3] = Combinations[3-2] + Combinations[3] = Combinations[1] + Combinations[3] = 1 + 1 = 2

Similarly when Amount is 4 and Coin is 2, we have,

Combinations[4] = Combinations[4-2] + Combinations[4] = Combinations[2] + Combinations[4] = 2 + 1 = 3

0	1	2	3	4	5	6	7	8	9	10	11	12
1	1	2	2	3	3	4	4	5	5	6	6	7

Combinations when Coin is 5

When Amount is 0 to 4 and Coin is 5, the condition (Amount >= Coin) becomes false, so we skip Amounts 0 and 4.

When Amount is 5 and Coin is 5, we have,

Combinations[5] = Combinations[5-5] + Combinations[5] = Combinations[0] + Combinations[5] = 1 + 3 = 4

Similarly when Amount is 6 and Coin is 5, we have,

Combinations[6] = Combinations[6-5] + Combinations[6] = Combinations[1] + Combinations[6] = 1 + 4 = 5

0	1	2	3	4	5	6	7	8	9	10	11	12
1	1	2	2	3	4	5	6	7	8	10	11	13

Another example were Amount = 4 and Coins = {1, 2, 3}

Below is the code for Coin Change Problem

int change(int amount, int[] coins) {

  int[] combinations = new int[amount + 1];
  combinations[0] = 1;

  for(int coin : coins) {
    for(int i = 1; i < combinations.length; i++) {
       if(i >= coin) {
         combinations[i] += combinations[i - coin];
       }
    }
  }
}

---

Longest Common Subsequence (LCS) Problem

Longest Common Subsequence Problem is to find the common subsequences but are not required to occupy consecutive positions with the original sequences.

For example, consider the following sequences, A and B

A = bqdrcvefgh

B = abcvdefgh

Here the length of LCS is 7,

LCS are bdefgh and bcvefgh

We first construct a matrix with columns as characters of string A and rows as characters of string B.

• If one of the string is empty or both the strings are empty then the length of the longest common subsequence is 0, hence we put zero for both the empty character row and empty character column.
• When the row character matches with the column character for the cell, then take the previous diagonal value in the matrix and add 1 since there is a match, to get the final value of the cell.
• When the row character does not match with the column character for the cell, then take the maximum between the above cell and the left cell, to get the final value of the cell.

int longestCommonSubsequence(String A, String B) {

  int m = A.length(), n = B.length();

  int[][] table = new int[m+1][n+1];

  for(int i = 0; i <= m; i++) {
     table[i][0] = 0;
  }

  for(int j = 0; j <= n; j++) {
     table[0][j] = 0;
  }

  for(int i = 1; i <= m; i++) {

     for(int j = 1; j <= n; j++) {

        if(A.charAt(i - 1) == B.charAt(j - 1))
           table[i][j] = table[i - 1][j - 1] + 1;
        else 
           table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
     }
  }

  return table[m][n];
}

---

Subset Sum Problem

Given a set of positive integers and an integer s, find if there is any non-empty subset whose sum is s.

For example set = { 1, 2, 7, 5 }

sum = 8 has subset { 1, 2, 5 }

sum = 4 has no subset

First the given set is sorted in ascending order.

Logic:

Since this is a dynamic programming problem we create a matrix with columns as 0 incrementing by 1 till the sum s. The rows are each element in the example set in a sorted order.

Truth Value = (Truth Value by Excluding New Value) OR (Truth Value by Including New Value)

Truth value by excluding the new value in the current cell comes from the value of upper cell within the matrix.

Truth value by including the new value in the current cell comes from getting the cell value of previous/upper row and the column equal to (sum - new value of the row) within the matrix.

Finally, we return true if we get subset by including or excluding current item else we return false.

To find the subset which gives the sum s, we go to the last cell and backtrack to check were the True value is coming from. If value in the cell above it is False, then it means current cell has become True after including the current element. So include the current element and check for the sum = sum – current element.

public static boolean subSetDP(int[] A, int sum) {
        boolean[][] solution = new boolean[A.length + 1][sum + 1];
        // if sum is not zero and subset is 0, we can't make it 
        for(int i=1; i<=sum; i++){
            solution[0][i]=false;
        }
        // if sum is 0 the we can make the empty subset to make sum 0
        for(int i=0; i<=A.length; i++){
            solution[i][0]=true;
        }
        
        // do for ith item
        for(int i=1; i<=A.length; i++){
            // consider all sum from 1 to sum
            for(int j=1; j<=sum; j++){
            
                // don't include ith element if j-array[i-1] is negative
                if(A[i-1] > j) {
                   //first copy the data from the top
                   solution[i][j] = solution[i-1][j];
                }
                else {
                    // find subset with sum j by excluding or including the ith item
                    solution[i][j] = solution[i-1][j] || solution[i-1][j - A[i-1]];
                }
            }
        }
        return solution[A.length][sum];
    }

---

Partition Problem

Given a set of positive integers, find if it can be divided into two subsets with equal sum.

Example Set S = {3,1,1,2,2,1}

We can partition S into two partitions each having sum 5.

S1 = {1,1,1,2}

S2 = {2,3}

Another solution could be,

S1 = {3,1,1}

S2 = {2,2,1}

// Return true if there exists a subset of array[0..n) with given sum
private bool subsetSum(int arr[], int n, int sum)
{
	// T[i][j] stores true if subset with sum j can be attained with
	// using items up to first i items
	bool T[n + 1][sum + 1];

	// if 0 items in the list and sum is non-zero
	for (int j = 1; j <= sum; j++)
		T[0][j] = false;

	// if sum is zero
	for (int i = 0; i <= n; i++)
		T[i][0] = true;

	// do for ith item
	for (int i = 1; i <= n; i++)
	{
		// consider all sum from 1 to sum
		for (int j = 1; j <= sum; j++)
		{
			// don't include ith element if j-arr[i-1] is negative
			if (arr[i - 1] > j)
				T[i][j] = T[i - 1][j];
			else
			// find subset with sum j by excluding or including the ith item
				T[i][j] = T[i - 1][j] || T[i - 1][j - arr[i - 1]];
		}
	}

	// return maximum value
	return T[n][sum];
}

// Partition problem - Return true if given array arr[0..n-1] can
// be divided into two subsets with equal sum
public bool partition(int arr[], int n)
{
	int sum = 0;
	for (int i = 0; i < n; i++)
	sum += arr[i];

	// return true if sum is even and array can can be divided into
	// two subsets with equal sum
	return !(sum & 1) && subsetSum(arr, n, sum/2);
}

---

0/1 Knapsack Problem

We are given a set of items, each with a weight and a value (or profit) and need to determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. The 0/1 indicates that the item can either be selected or not selected, i.e. items are indivisible.

Sum of the Weights <= Total Weights

Sum of the value should be maximum

Consider the below example were we have items {a, b, c, d, e} with weights and values as below. We need to in the subset with maximum sum of value were sum of their weights should be equal to or less then 9. The quantity of all the items is 1. We create the matrix as below, with the columns as increasing number of weights aka Sum of weights from 0 to the total weight. The rows of the matrix are the sorted using item values.

	weight	value
a	1	1
b	3	4
c	4	5
d	5	7
e	2	4

item	value	weight	0	1	2	3	4	5	6	7	8	9
a	1	1	0	1	1	1	1	1	1	1	1	1
e	4	2	0	1	4	5	5	5	5	5	5	5
b	4	3	0	1	4	5	5	8	9	9	9	9
c	5	4	0	1	4	5	5	8	9	10	10	13
d	7	5	0	1	4	5	5	8	9	11	12	13

We cannot achieve the zero weight, using the weights of any items so entire column is assigned the value 0.  For column with weight 1, since item a which has weight 1 can contribute in forming the sum of the weights from 1 to 9, we add 1 to entire row. Now we follow below logic to determine the current value of the cell,

1)   If item weight <= sum of weights,

      value = maximum of(value by excluding the new item, value by including the new item)

To calculate the value by including the new item, we add

• value of the new item (not the weight)
• value from above row and the column (sum of weights in column - current item's weight).

2)   If item weight > sum of the weights, copy the value from the above cell.

Use backtracking to determine from were the final value of 13 came to determine the weights or the items included in the result collection.

private int knapSack(int sumWeight, int weights[], int values[]) { 

        int n = values.length;
        
        // K[i][j] stores the maximum value that can be attained with
        // weight less than or equal to j using items up to first i items
        int K[][] = new int[n + 1][sumWeight + 1]; 

	    for (int j = 0; j <= sumWeight; j++) {
		   K[0][j] = 0;
        }

        for (int i = 1; i<= n; i++) { 
        
            // consider all weights from 0 to maximum capacity sumWeight
            for (int j = 0; j<= sumWeight; j++) { 
                    
               	// don't include ith element if j-weights[i-1] is negative
			    if (weights[i-1] > j)
				    K[i][j] = K[i-1][j];
			    else
			    // find max value by excluding or including the ith item
				    K[i][j] = Math.max(K[i-1][j], K[i-1][j-weights[i-1]] + values[i-1]);
            } 
        } 
  
        return K[n][sumWeight]; 
    } 

---

Rod Cutting Problem

Given a rod of length n and list of pieces of rod of length i where 1 <= i <= n, find the optimal way to cut the rod into smaller rods in order to maximize the profit.

Rod of length = 5

lengths of pieces = {1, 2, 3, 4}

profits of pieces = {2, 5, 7, 8}

If we cut the rod in the given lengths of piece, then profit of each piece is given in corresponding profits set. The rod has to be cut in such a way that we get the maximum profit.

We create the memoization matrix, with column as total length of from 0 to length of the rod, and rows as length of each piece given in the set. Each cell has the profit value for the corresponding piece with the length.

The piece with length 0 is hypothetical condition, hence, entire row's values is 0.

Also if we want to make the total length of 0 for column with sum of length as 0, none of the piece from length 1 to 4 satisfy the condition, hence all entries there are 0.

If we have a piece of length 1 and we want total length to be 1, we need only 1 piece with length 1 to achieve that, hence the profit value of piece 1 is added to the corresponding cell. Similarly, to achieve the total length of 2, we need two pieces of length 1, hence we add profit value of piece 1 twice to corresponding cell. Similar goes for columns 3,4 and 5 with row of piece length 1.

When the row piece length is greater than column total length we copy the cell value from upper row. If the row piece length is less than or equal to column total length, then we use the below logic. Profit by including new piece is,

(Profit of current piece) + 

(Profit of cell with column as (Current Total length - Current piece length) in current row).

Profit = max (Profit by excluding new piece, Profit by including new piece)

profit	length	0	1	2	3	4	5
0	0	0	0	0	0	0	0
2	1	0	2	4	6	8	10
5	2	0	2	5	7	10	12
9	3	0	2	5	9	11	14
6	4	0	2	5	9	11	14

// n is the maximum length of the rod
public int rodCut(int[] price, int n)
	{
		// T[i] stores maximum profit achieved from rod of length i
		int[] T = new int[n + 1];
        T[0] = 0;

		// consider rod of length i
		for (int i = 1; i <= n; i++)
		{
			// divide the rod of length i into two rods of length j
			// and i-j each and take maximum
			for (int j = 0; j < i; j++) {
				T[i] = Math.max(T[i], price[j] + T[i - (j + 1)]);
			}
		}

		// T[n] stores maximum profit achieved from rod of length n
		return T[n];
	}

---

Word Break Problem

Given a string and a dictionary of words, determine if string can be segmented or split into a space-separated sequence of one or more dictionary words.

E.g. dictionary[] = { "this", "th", "is", "famous", "break", "b",

                    "r", "e", "a", "k", "br", "bre", "brea", "ak", "problem"}

string = "Wordbreakproblem"

---

Programming Interview - Mathematics Basics

Permutations and Combinations

When the order doesn't matter, it is a Combination. When the order does matter it is a Permutation.

There are 2 types of Permutation, repetition is allowed and no repetition allowed.

Permutations with Repetition = n ^ pow(r) = n * n * n * ... (r times)

Here n is the number of things to choose from, and we choose r of them, repetition is allowed, and order matters.

Permutations without Repetition = n! / (n − r)!

Here n is the number of things to choose from, and we choose r of them, no repetitions and order matters.

Similarly there are 2 types of Combination, repetition is allowed and no repetition allowed.

Combinations without Repetition = n! / ( r! * (n − r)! )

Combinations with Repetition = (r + n - 1)! / ( r! * (n − 1)! )

REMEMBER: (a + b) / 2 = a + (b - a) / 2    (Used as (a+b) could overflow Integer's range)

Programming Interview - Mathematics Problems

Find all factors of the number ?

A number is always divisible by 1 and itself. The smallest factor a number can have is 2, while largest factor would be n/2. But as a * b = number n, were a and b are co-efficient, the pairs of numbers will be duplicated after a = b, i.e. square-root of n. Hence we only need to loop till square-root of n, and add both i and n/i to the list of factors.

Verify if number is a prime number ?

To verify a prime number we only need to loop through from 2 to square-root of number n. As the number n to be non-prime there must be factors "a" and "b" such that a = n / b, i.e. a * b = n. As we observe for example number 36, the factor pairs {1,36} {2,18} {3,12} {4,9} {6,6} {9,4} {12,3} {18,2} {36,1} are repeated after {6,6} which is after square-root of 36, i.e. 6. Hence after square-root of n, the numbers would be either repeated factor-pairs, multiple of other prime numbers.

Also 1 is not regarded as a prime number. 

Fibonacci Sequence

F(n) = { F(n - 1) + F(n - 2)   if n > 1

           {  n                             if n = 0,1 }

0  1  1  2  3  5  8  ...

The first two terms of the series are 0, 1.

Using Recursion: if(n <= 1)  return n;   return fibonacci(n-1) + fibonacci(n-2)

Recursion: Exponential Time

Fibonacci Sequence Recursion: O(2^n)

Iteration: Here we need three variables, the previousNumber, the currentNumber and a temp Number as we cannot assign the new value to currentNumber directly because, we have to first move currentNumber's value to previousNumber.

    System.out.print(previousNumber + ", ");

    for (int i = 1; i < n; i++) {

        newNumber = currentNumber + previousNumber;
        previousNumber = currentNumber;
        currentNumber = newNumber;

        System.out.print(currentNumber + ", ");
    }
  

Modular Exponentiation

Calculate: x^n mod M

Since integer is 32 bit, with 1 bit reserved for sign, the range of integer is -2^31 to 2^31, hence calculating x^n directly will not fit many cases within integer range.

Since (a * b) % M = {(a % M) * (b % M)} % M

x^n % M = (x * x^n-1) % M

        = {(x % M) * (x^n-1 % M)} % M

When n is even,  {(x^n/2 % M) * (x^n/2 % M)} % M

Time complexity is O(log n)

Power(x,n) i.e. x^n

x^n = { x^n/2 * x^n/2  if n is even

        x * x^n-1      if n is odd

        1              if n=0       }

To calculate the time complexity, use the variance of the number being updated and passed to the recursive function.

T(n) = T(n/2) + C

T(n) = T(n/2^k) + K*C    assuming this is done k times.

Hence k is log2(n) which is the time complexity.

Find all factors of the number:

12 = {1,2,3,4,6,12}

Trial Division were we try to divide the number with all the numbers from 1 to n itself.

But 1 and the number itself are its factors. Also since the smallest factor of the number is 2 and largest factor is n/2, there are no factors of the number above n/2. Also if a * b = n, assuming a.b are factors, then when a > sqrt n, then b < sqrt n. Further when a = sqrt n, then a = b = sqrt n. Hence only search factor till square root of number, as remaining are just number/factor.

Divide all the numbers starting from 2 to square-root of n, and add [current-no] with (n / [current-no]) to the factors list. Numbers 1 and n are already added to factors list.

Time complexity is O(sqrt n)

Prime Factorization of a number n

24 = 3 * 2 * 2 * 2

Start dividing the number n by smallest number (starting with 2) such that the remainder is 0. Continue dividing the quotient from previous division until the remainder is non-zero, then select the next number for division of the quotient. The loop continues selecting next smallest number (i) until the (i) becomes greater than square-root of quotient, which indicates that the quotient is a prime number. Since we already know that there cannot be any factors for a number (quotient here) after square-root of that number.

Time complexity is O(sqrt n)

How do implement Sieve of Eratosthenes Algorithms for Prime Number?

How to check if a given year is a leap year in Java?

How to convert a decimal number to binary in Java?

How to reverse given Integer in Java?

How to find the largest prime factor of a given integral number?

How to print Floyd’s triangle?

How to print Pascal’s triangle? (solution)

How to calculate the square root of a given number?

Programming Interview - Core

Binary Search

1. Sorted array is pre-condition for binary Search. Take two pinter with start = 0, end = n-1 where n is length of the array.
2. Search a sorted array by repeatedly dividing the search interval in half. 
3. mid = (start + end) / 2
4. Case 1:  x == A[mid]   return mid
5. Case 2:  x < A[mid]    end = mid - 1    (x lies before the mid element, so shift end)
6. Case 3:  x > A[mid]    start = mid + 1    (x lies after the mid element, so shift start)
7. Continue till start <= end, (because even when start == end, we have 1 element to check)

If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

  int binarySearch(int array[], int start, int end, int numberToFind);
  

Complexity: (n / 2^k) = 1, were k is no of steps to reach result, while n is length of array. This gives k = log n. Hence the time complexity is O(log n).

Recursive Version:

• binarySearch(array, start, end, numberToFind)
• When start > end, then return -1
• mid = (start + end) / 2
• Case 1: x == array[mid], then return mid
• Case 2: x < array[mid],   then call binarySearch(array, start, mid-1, numberToFind)
• Case 3: x > array[mid],   then call binarySearch(array, mid+1, end, numberToFind)

Binary Search - First Occurrence of the element

We have a sorted array with duplicate elements to find the first occurrence of the element.

Modify the Case1 as below:

result = -1  (initialize the result with -1 indicating that no match found)

Case 1:  x == A[mid]   then  

              result = mid;     (capture the result i.e. the position of the matched element) 

              end = mid - 1    (to find first occurrence of the element x, check if there is one more occurrence of x before matched mid element, hence we shift end before mid)

Finally return result

Binary Search - Last Occurrence of the element

Similar to above we modify the Case1 as below:

Case 1:  x == A[mid]   then  

              result = mid;     (capture the result i.e. the position of the matched element) 

              start = mid + 1    (to find last occurrence of the element x, check if there is one more occurrence of x after the matched mid element, hence we shift start after mid)

Finally return result

Time complexity of both these variations of binary search is O(log n).

Count number of occurrences of element in sorted array

Strategy 1: Loop through the sorted array until there is a match and count until there is no match.

Strategy 2: Find the element in the sorted array using binary search, then first shift left and then shift right to count all the occurrences of the element.

Strategy 3: Find the first occurrence of element using binary search and then the last occurrence of element using binary search, using that determine the count of occurrences since the array is sorted i.e. (Last - First + 1).

Search element in a circular sorted array

Given a sorted circular array were the start element followed by end element lies somewhere in the middle of the array. 

E.g. 12,  14,  18,  21,  3,  6,  8,  9

      low               mid                high

The start element in the above array is 3. 

In the below code, x is the input element to be searched and we need to determine the position of x in the array.

mid = (low + high) / 2

Case1: A[mid] == x, return mid

Case2: A[mid] <= A[high]         // Right half is sorted

2A:    x > A[mid] && x <= A[high]

        low = mid + 1                   // search in right sorted half

Else

       high = mid - 1                    // search in left half

Case 3: A[low] <= A[mid]         // Left half is sorted

3A: x >= A[low] && x < A[mid]

       high = mid - 1                    // search in left sorted half

Else

        low = mid + 1                   // search in right half

Precedence of Operators

(high + low) / 2 is same as low + ((high - low)/2), as low + high can overflow if range exceeds integer.

Memoization

Memoization is an optimization technique used to speed up programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

Sorting

Quick Sort

It is in place sorting.

Average case: O(n log n)

Worst case: n pow 2

1) Select a Pivot.

2) Move the elements lower than pivot to left side, while move elements higher than pivot to right side.

In below example we select the pivot always as the last element.

QuickSort(A, start, end) { 

  if (start < end) {

    pIndex = Partition(A, start, end)

    QuickSort(A, start, pIndex-1)

    QuickSort(A, pIndex+1, end)

  }

}

Partition(A, start, end) {

 pivot = A[end]             // Pivot is always the last element of list

 pIndex = start

 for i=start to end-1 {

   if(A[i] <= pivot) {

     swap(A[i], A[pIndex])

     pIndex = pIndex + 1

   }

 }

 swap(A[pIndex], A[end])

 return

}

Merge Sort

1) Split the list into half, at the mid point. Continue to split the 2 lists each recursively further until only 1 element is present. 

2) Now merge all the splitted list earlier recursively from bottom up such that, the final list at each step is sorted. Note here while merging two lists, we first take original list which was splitted in those two lists in the first place. Loop through both the Left and Right splitter list to check which is greater/less and place them elements in sorted fashion into the original list. Repeat this for all list in each recursive step.

Merge(Left, Right, A) {

  sizeLeft = length(Left)

  sizeRight = length(Right)

  i = j = k = 0

  while(i < sizeLeft && j < sizeRight) {

    if( Left[i] <= Right[j] )  {

       

       A[k] = Left[i]

       k = k + 1

       i = i + 1

    }

    else {

       A[k] = Right[j]

       k = k + 1

       j = j + 1

    }

  }

  // If there are elements remaining in either Left or Right list then simply append to result list

  while(i < sizeLeft) {

     A[k] = Left[i]

     i = i + 1

     k = k + 1

  }

  while(j < sizeRight) {

     A[k] = Right[j]

     j = j + 1

     k = k + 1

  }

}

MergeSort(A) {

  n = length(A)

  if(n < 2) return

  mid = n/2

  left = array of size(mid)

  right = array of size(n - mid)

  for i = 0 to mid - 1

     left[i] = A[i]

  for i = mid to n - 1

     right[i-mid] = A[i]

  MergeSort(left)

  MergeSort(right)

  Merge(left, right, A)

}

Java 8 Features

Lambda expressions allow to pass in a block of code, a function without a name. The -> separates the parameter from the body of the lambda expression. The parameter of lambda expression does not have a type as the type is inferred from the context of the variable. The lambda method parameters are statically typed. Some different ways of writing lambda expressions areas below:

// 1) empty pair of parentheses, (), can be used to signify that there are no arguments.

Runnable noArguments = () -> System.out.println("Hello World");

// 2) when there is only one argument to the lambda expression we can leave out the parentheses around the arguments.

ActionListener oneArgument = event -> System.out.println("button clicked");

// 3) full block of code, bookended by curly braces ({})

Runnable multiStatement = () -> {
   System.out.print("Hello");
   System.out.println(" World");
};

// 4) This creates a function that adds together two numbers, were the variable called add 
//    isn’t the result of adding up two numbers; it is code that adds together two numbers.

BinaryOperator<Long> add = (x, y) -> x + y;

// 5) providing explicit type to arguments requires to surround the arguments to the lambda expression with parentheses. 
//    The parentheses are also necessary if you’ve got multiple arguments.

BinaryOperator<Long> addExplicit = (Long x, Long y) -> x + y;

The target type of a lambda expression is the type of the context in which the lambda expression appears—for example, a local variable that it’s assigned to or a method parameter that it gets passed into.

Lambda expressions only use final variables since they capture values, not variables. Although we are not required to declare the variable(s) as final, we cannot use them as nonfinal variable(s) if they are to be used in lambda expressions. If you assign to the variable multiple times and then try to use it in a lambda expression, you’ll get a compile error.

Lambda expressions are statically typed, and these types of lambda expressions are called functional interfaces. A functional interface is an  interface with a single abstract method that is used as the type of a lambda expression.

Table 2-1. Important functional interfaces in Java

Interface name	Arguments	Returns	Example
Predicate<T>	T	boolean	Has this album been released yet?
Consumer<T>	T	void	Printing out a value
Function<T, R>	T	R	Get the name from an Artist object
Supplier<T>	None	T	A factory method
UnaryOperator<T>	T	T	Logical not (!)
BinaryOperator<T>	(T, T)	T	Multiplying two numbers (*)

Java 8 allows you to leave out the types for whole parameters of lambda expressions. Java compiler looks for information close to the lambda expression and uses this information to figure out what the correct type should be. It’s still type checked and provides all the safety that you’re used to, but you don’t have to state the types explicitly. This is what we mean by type inference.

A Predicate is a functional interface that checks whether something is true or false. It is also a lambda expression that returns a value, unlike the previous ActionListener examples.

Predicate<Integer> atLeast5 = x -> x > 5;

Here the return value of the lambda expression is the value its body evaluates to.

BinaryOperator is a functional interface that takes two arguments and returns a value, all of which are of same type. It takes only a generic argument. If no generic argument is specified the code doesn't compile.

BinaryOperator<Long> addLongs = (x, y) -> x + y;

Some of the Key Points on Lambda Expressions:

• A lambda expression is a method without a name that is used to pass around behavior as if it were data.
• Lambda expressions look like this: BinaryOperator<Integer> add = (x, y) ? x + y.
• A functional interface is an interface with a single abstract method that is used as the type of a lambda expression.

Streams

In for loop for collections, the iteration proceeds by creating a new Iterator object and then explicitly calling the hasNext and next methods on the Iterator. Hence its too hard to abstract away the different behavioral operations and is inherently serial in nature.

Streams allow to write collections-processing code at a higher level of abstraction. A Stream is a tool for building up complex operations on collections using a functional approach. The Stream interface contains a series of functions each of which corresponds to a common operation that we might perform on a Collection. The call to stream() returns a Stream which is an equivalent interface with the Iterator in the internal iteration of collection.

long count = allArtists.stream().filter(artist -> artist.isFrom("London")).count();

The operations using Streams API does not change the contents of collection but declared the contents of the Stream. The Stream object returned isn’t a new collection—it’s a recipe for creating a new collection. The filter method of the Stream above keeps only those objects that pass a test by returning either true or false. The call to filter builds up a Stream recipe, but there’s nothing to force this recipe to be used. Methods such as filter that build up the Stream recipe but don’t force a new value to be generated at the end are referred to as lazy. Methods such as count that generate a final value out of the Stream sequence are called eager. If the operation gives back a Stream, it’s lazy; if it gives back another value or void, then it’s eager. The values in the Stream that are operated on are derived from the initial values and the recipe produced by the sequence of Stream calls.

The collect(toList()) is an eager operation that generates a list from the values in a Stream.

List<String> collected = Stream.of("a", "b", "c").collect(Collectors.toList());

The map operation allows to apply a function (say converting a value of one type into another) to a stream of values, producing another stream of the new values. It is an instance of Function.

List<String> collected = Stream.of("a", "b", "hello").map(string -> string.toUpperCase()).collect(toList());

The filter method on the stream allows to check each element of the collection. The Stream after the filter has the elements of the Stream
beforehand, which evaluated to true. It is an instance of Predicate interface.

The flatMap method allows to replace a value with a Stream and concatenates all the streams together. It is a variant of map operation which produces a new Stream object as the replacement. It is associated with functional interface but its return type is restricted to streams and not any value.

// Takes Stream of lists of numbers and returns all the numbers from in the sequences.

List<Integer> together = Stream.of(asList(1, 2), asList(3, 4)).flatMap(numbers -> numbers.stream()).collect(toList());

The max and min methods of stream API finds the maximum or minimum element in the streams. The Comparator is passed to determine the ordering of the elements. The comparing method in java 8 allows to build a Comparator using keys. The getter function for the value allows to get the same element out of both elements being compared. When the max method is called on an empty Stream it returns an Optional value, which represents a value that may exist, or may not.

Track shortestTrack = tracks.stream().min(Comparator.comparing(track -> track.getLength())).get();

The reduce operation is used to generate a single result from a collection of values. It takes the initial count and the lambda expression. The count always starts with 0 which is the count of an empty Stream. The type of the reducer is a BinaryOperator.

int count = Stream.of(1, 2, 3).reduce(0, (acc, element) -> acc + element);

Higher-order functions: A higher-order function is a function that either takes another function as an argument or returns a function as its result. If a functional interface is used as a parameter or return type, then we have a higher-order function. Nearly all the functions that we’ve encountered on the Stream interface are higher-order functions. Comparator is also a functional interface as it has only a single abstract method.

Streams describes the operations on data by saying what transformation is made rather than how the transformation occurs. They help to get towards an idea of side effect–free function. Functions with no side effects don’t change the state of anything else in the program or the outside world. Lambda expressions allow to capture values rather than capturing variables (as variables are final), hence promoting to write code free from side effects. The only exception to this is the forEach method, which is a terminal operation.

Java 8 introduces default methods and static methods on interfaces enabling to have methods with bodies containing code.

Boxed types which wrap up the primitive types are objects and have a memory overhead. An primitive int takes 4 bytes of memory, an boxed type Integer takes 16 bytes. Further an Integer[] take up nearly six times more memory than an int[] of the same size. There is also a computational overhead when converting from a primitive type to a boxed type (boxing) and vice versa (unboxing). The streams library hence differentiates between the primitive and boxed versions of some library functions e.g. mapToLong higher-order function and ToLongFunction.
        If the return type is a primitive, the interface is prefixed with To and the primitive type, as in ToLongFunction. If the argument type is a primitive type, the name prefix is just the type name, as in LongFunction. If the higher-order function uses a primitive type, it is suffixed with To and the primitive type, as in mapToLong. These methods such as mapToLong return specialized streams such as IntStream, DoubleStream and LongStream instead of Stream. The min, max, average, sum along with summaryStatistics methods are all available on all three primitive specialized Stream variants.

While overloading the methods, java infers the type of lambda to be the most specific functional interface when calling these methods.

• If there is a single possible target type, the lambda expression infers the type from the corresponding argument on the functional interface.
• If there are several possible target types, the most specific type is inferred.
• If there are several possible target types and there is no most specific type, you must manually provide a type.

@FunctionalInterface is an annotation that should be applied to any interface that is intended to be used as a functional interface. The new interfaces provide Stream interoperability and are really there to bundle up blocks of code as data. Interfaces such as java.lang.Comparable and java.io.Closeable have only a single method (which depends on the object's internal state) but aren’t normally meant to be implemented by lambda expressions. The @FunctionalInterface annotation can be applied to such interfaces enabling them to be used with lambda expressions.

Default Methods allow to let the implementing classes of the interface use their implementation e.g. the stream method of collection or forEach method on Iterable. Unlike classes, interfaces don’t have instance fields, so default methods can modify their child classes only by calling methods on them. This helps to avoid making assumptions about the implementation of their children. The default method is a virtual method opposite of a static method. The class or concrete method override always takes precedence over the default method. If a child class extends a parent class which in turn implemented an interface with a default method. Then the child class also implemented another interface with the default method of the same signature. But the default method from the parent class takes precedence over the default method from the interface.

When a class implements multiple interface with the same default method it results in the compile error. With the new enhanced super syntax i.e. using the InterfaceName.super variant it’s possible to specify a method from an inherited interface.

Below are the rules for multiple inheritance for default methods.

1. Any class wins over any interface. So if there’s a method with a body, or an abstract declaration, in the superclass chain, we can ignore the interfaces completely.
2. Subtype wins over supertype. If we have a situation in which two interfaces are competing to provide a default method and one interface extends the other, the subclass wins.
3. No rule 3. If the previous two rules don’t give us the answer, the subclass must either implement the method or declare it abstract.

The default methods avoids multiple inheritance of state but rather allows inheritance of blocks of code. Java 8 enables static methods on an interface e.g the of() method of the Stream interface.

Optional is a new core library data type that is designed to provide a better alternative to null. null is often used to represent the absence of a value, and this is the use case that Optional is replacing. The problem with using null in order to represent absence is the dreaded NullPointerException. Optional encourages the coder to make appropriate checks as to whether a variable is null in order to avoid bugs. Second, it documents values that are expected to be absent in a class’s API. The factory method is used to create an Optional instance from a value. The empty factory method of Optional is used to represent Optional as an absent value. Also a a nullable value can be converted into an Optional using the ofNullable method.

A common idiom you may have noticed is the creation of a lambda expression that calls a method on its parameter.

artist -> artist.getName()

Such common idiom can be written using method reference as below:

Artist::getName

The standard form of method reference is Classname::methodName. There are no method brackets, since we are not actually calling the method but providing the equivalent of a lambda expression that can be called in order to call the method. Constructors can also be called using the same abbreviated syntax as below:

(name, nationality) -> new Artist(name, nationality) // original
Artist::new // creating an Artist object
String[]::new // creating String array

Method references automatically support multiple parameters, as long as you have the right functional interface.

Element Ordering
The encounter order is defined depends on both the source of the data and the operations performed on the Stream. When you create a Stream from a collection with a defined order e.g. List, the Stream has a defined encounter order. When we try to map values and there’s a defined encounter order, then that encounter order will be preserved. When there’s no encounter order on the input Stream, there’s no encounter order on the output Stream. Most operations, such as filter, map, and reduce, can operate very efficiently on ordered streams. Although ordering can be removed by using stream's unordered method. The forEachOrdered method provides an ordering guarantee compared to forEach method especially while using parallel streams.

The collector is a general-purpose construct for producing complex values from streams. These can be used with any Stream by passing them into the collect method. The collectors can be statically imported from the java.util.stream.Collectors class.
The toList collector produces java.util.List instances, while the toSet and toCollection collector produces instances of Set and Collection.

List<Integer> numbers = asList(1, 2, 3, 4);
List<Integer> stillOrdered = numbers.stream().map(x -> x + 1).collect(toList());

By calling toList or toSet we don’t get to specify the concrete implementation of the List or Set and the implementation is picked by stream library.

The collector e.g. toCollection can take a function to build a specified type of collection as its argument as below:

stream.collect(toCollection(TreeSet::new));

Also single value can be collected using collector such as maxBy and minBy collectors.

public Optional<Artist> biggestGroup(Stream<Artist> artists) {
   // defines a lambda expression that can map an artist to the number of members
   Function<Artist,Long> getCount = artist -> artist.getMembers().count();
   return artists.collect(maxBy(comparing(getCount)));
}

The averagingInt method takes a lambda expression in order to convert each element in the Stream into an int before averaging the values as below.

public double averageNumberOfTracks(List<Album> albums) {
    return albums.stream().collect(averagingInt(album -> album.getTrackList().size()));
}

A collector partitioningBy takes a stream and partitions its contents into two groups. It uses a Predicate to determine whether an element should be part of the true group or the false group and returns a Map from Boolean to a List of values.

public Map<Boolean, List<Artist>> bandsAndSolo(Stream<Artist> artists) {
 // The method reference Artist::isSolo can be also written as artist -> artist.isSolo()
 return artists.collect(partitioningBy(Artist::isSolo));
}

The groupingBy collector takes a classifier function in order to partition the data similar to the partitioningBy collector which took a Predicate to split it up into true and false values. Below is an example which groups a Stream of albums by the name of their main musician. The groupingBy form below divides elements into buckets. Each bucket gets associated with the key provided by the classifier function, e.g. here its getMainMusician. The groupingBy operation then uses the downstream collector to collect each bucket and makes a map of the results.

public Map<Artist, Long> numberOfAlbums(Stream<Album> albums) {
    return albums.collect(groupingBy(album -> album.getMainMusician(),
    counting()));
}

The mapping collector allows to perform a map-like operation over the collector’s container. The mapping collector needs the collection to store the results, which can be done using the toList collector.

public Map<Artist, List<String>> nameOfAlbums(Stream<Album> albums) {
    return albums.collect(groupingBy(Album::getMainMusician,
    mapping(Album::getName, toList())));
}

In both the above cases, the second collector is used in order to collect a subpart of the final result, hence also called downstream collectors.

Comma separated string from the formatted list can be generated using Collectors.joining which collects the Stream to string as below:

String result =
    artists.stream()
              .map(Artist::getName)
              .collect(Collectors.joining(", ", "[", "]"));

Data Parallelism

Amdahl’s Law is a simple rule that predicts the theoretical maximum speedup of a program on a machine with multiple cores. If we take a program that is entirely serial and parallelize only half of it, then the maximum speedup possible, regardless of how many cores we throw at the problem, is 2×. Given a large number of cores—and we’re already into that territory—the execution time of a problem is going to be dominated by the serial part of that problem

When we have a Stream object, we can call its parallel method in order to make it parallel. If we’re creating a Stream from a Collection, we can call the parallelStream method in order to create a parallel stream from the get-go. Below is the example which calculates the total length of a sequence of albums in parallel.

public int parallelArraySum() {
    return albums.parallelStream()
                 .flatMap(Album::getTracks)
                 .mapToInt(Track::getLength)
                 .sum();
}

The kinds of problems that parallel stream libraries excel at are those that involve simple operations processing a lot of data, such as Simulations. Below is the example of parallel Monte Carlo simulation. Here we first use the IntStream range function to create a stream of size N, then call the parallel method in order to use the parallel version of the streams framework. The twoDiceThrows function simulates throwing two dice and returns the sum of their results, which is used on the data stream using the mapToObj method. All the simulation results are combined using the groupingBy collector. Then the numbers are mapped to 1/N and added using the summingDouble function.

public Map<integer double=""> parallelDiceRolls() {
    double fraction = 1.0 / N;
    return IntStream.range(0, N)
            .parallel()
            .mapToObj(twoDiceThrows())
            .collect(groupingBy(side -> side,
                                summingDouble(n -> fraction)));
}

When calling reduce the initial element could be any value, but for same operation to work correctly in parallel, it needs to be the identity value of the combining function. The identity value leaves all other elements the same when reduced with them. For example, if we’re summing elements with our reduce operation, the combining function is (acc, element) -> acc + element. The initial element must be 0, because any number x added to 0 returns x. Another caveat specific to reduce is that the combining function must be associative. This means that the order in which the combining function is applied doesn’t matter as long the values of the sequence aren’t changed.

The streams framework deals with any necessary synchronization itself, so there’s no need to lock the data structures. If we tried to hold locks on any data structure that the streams library is using, such as the source collection of an operation then it would likely cause issues. Stream also has a sequential method other than the parallel method. When a stream pipeline is evaluated, there is no mixed mode, i.e. the orientation is either parallel or sequential. If a pipeline has calls to both parallel and sequential, the last call wins. Under the hood, parallel streams back onto the fork/join framework. The fork stage recursively splits up a problem, were each chunk is operated upon in parallel and then the results are merged back together in the the join stage.

The common data sources from the core library can be split up into three main groups by performance characteristics:

The good: An ArrayList, an array, or the IntStream.range constructor. These data sources all support random access, which means they can be split up arbitrarily with ease.
The okay: The HashSet and TreeSet. These cannot be decomposed easily with perfect amounts of balance, but most of the time it’s possible to do so.
The bad: Some data structures don’t split well; for example, they may take O(N) time to decompose. Examples here include a LinkedList, which is computationally hard to split in half. Also, Streams.iterate and BufferedReader.lines have unknown length at the beginning, so it’s pretty hard to estimate when to split these sources.

Ideally, once the streams framework has decomposed the problem into smaller chunks, we’ll be able to operate on each chunk in its own thread, with no further communication or contention between threads.

Java 8 includes a couple of other parallel array operations that utilize lambda expressions outside of the streams framework These operations are all located on the utility class Arrays, which also contains a bunch of other useful array-related functionality from previous Java versions

Name	Operation
parallelPrefix	Calculates running totals of the values of an array given an arbitrary function
parallelSetAll	Updates the values in an array using a lambda expression
parallelSort	Sorts elements in parallel

The parallelSetAll method is used to easily initialize an array in parallel instead of using a for loop. An array is provided to operate on and a lambda expression, which calculates the value given the index. The array passed into the operation is altered, rather than creating a new copy.

public static double[] parallelInitialize(int size) {
      double[] values = new double[size];
      Arrays.parallelSetAll(values, i -> i);
      return values;
}

The parallelPrefix operation is useful for performing accumulation-type calculations over time series of data. It mutates an array, replacing each element with the sum (or any BinaryOperator) of that element and its predecessors. The below example takes a rolling window over a time series and produces an average for each instance of that window.

public static double[] simpleMovingAverage(double[] values, int n) {
      double[] sums = Arrays.copyOf(values, values.length);
      Arrays.parallelPrefix(sums, Double::sum);
      int start = n - 1;
      return IntStream.range(start, sums.length)
                  .mapToDouble(i -> {
                        double prefix = i == start ? 0 : sums[i - n];
                        return (sums[i] - prefix) / n;
                  })
            .toArray();
}