Leetcode 189: Rotate Array to the Right by K Times

$\mathtt{REFERENCE}$ @ LeetCode

Problem Definition

You are given an array and integer $k$ (>= 0). The problem is to rotate the input array to the right by $k$ times. Details can be found at LeetCode.

Example

Input: [1,2,3,4,5,6,7] and k = 3

Output: [5,6,7,1,2,3,4]

Solution 1 : Using Auxiliary Array of Size Same as Input Array.

In this method we go on saving the elements to the new rotated location in the auxiliary array. Finally when all elements are rotated to their proper indices, all elements are copied back to the original array in the same order as they appear after rotation.

Complexity

This method takes $\cal{O(n)}$ Time and $\cal{O(n)}$ Space.

Implementation

	//-------------------------------------------------------------------------------------
	//------------- METHOD 1 --------------------------------------------------------------
	/**
	* Rotation method that uses an auxiliary array to store the result
	* of rotation. Once the rotation is done, each element is copied to
	* the original array.
	*
	* The method requires O(n) time and O(n) space.
	*
	* @param nums input array to rotate.
	* @param k number of times to ratate the array.
	*/
	public void rotate(int[] nums, int k) {
	int N = nums.length;
	k = k % N;
	if (k == 0 || N < 2) return;
	int[] auxiliary = new int[N];
	for (int i = 0; i < k; i++) {
	int idx = N - 1 - i;
	int temp = nums[idx];
	while (idx - k >= 0) {
	auxiliary[idx] = nums[idx - k]; // push element from left to right
	idx -= k;
	}
	auxiliary[k - 1 - i] = temp; // bring element in the end section to front
	}
	for (int i = 0; i < N; i++) {
	nums[i] = auxiliary[i];
	}
	} // rotate

view raw ArrayRotation.java hosted with ❤ by GitHub

Solution 2 : Using Auxiliary array of size k

In the first solution we have used auxiliary array of size same as input to store rotated elements. If we look carefully, we can move in place those elements which can be pushed to right from left. Only those rightmost $k$ elements which can not be moved right cannot be moved in place because they have potential to replace the elements which have not been moved.

So it is sufficient to save only the right most $k$ elements in the auxiliary space. This will reduce the space requirement from ${O(n)}$ to ${O(k)}$.

In this method we use auxiliary array of size $k$ only. Rotation of the first $(N - k)$ elements will be done in place. Rotation of the last $k$ elements is stored in the auxiliary array. Once all elements are done, elements from the auxiliary array are copied in the front of input array.

Complexity

This method takes $\cal{O(n)}$ Time and $\cal{O(k)}$ Space.

Implementation

	//-------------------------------------------------------------------------------------
	//------------- METHOD 2 --------------------------------------------------------------
	/**
	* Rotation method that uses only a partial auxiliary array of size k.
	* Rotation mechanism is similar to first method difference being the beginning (n-k)
	* elements are rotated in place, only the last k elements are rotated and saved in
	* auxiliary array. Once the rotation is done, result is copied the be beginning of
	* original array.
	*
	* This method requires O(n) Time and O(k) space *
	*
	* @param nums input array to rotate.
	* @param k number of times to ratate the array.
	*/
	public void rotate2(int[] nums, int k) {
	k = k % nums.length;
	if (k == 0) return;
	int N = nums.length;
	int[] prefix = new int[k];
	for(int i = 0; i < k; i++) {
	int idx = N - 1 - i;
	int temp = nums[idx];
	while (idx - k >= 0) {
	//if (idx - k > 0) continue;
	nums[idx] = nums[idx - k]; // push element from left to right
	idx -= k;
	}
	prefix[k-1-i] = temp; // elements which cannot be pushed right. Save in prefix array
	}
	for (int i = 0; i < k; i++) {
	nums[i] = prefix[i]; // save elements from prefix array to original array
	}
	} // rotate2

view raw ArrayRotation.java hosted with ❤ by GitHub

Solution 3 : Using Reversal Algorithm

The solutions we discussed above uses auxiliary array of some size to solve the problem. Hence they have certain extra space requirement.

Here we are going to discuss a solution that does not use any extra space. So this is a constant space solution.

Here we divide the input array into two parts

1. First $(N - k)$ elements
2. and Last $k$ elements

Now,

1. Reverse the first part of the array.
2. Reverse the second part.
3. Reverse the whole array. Result will the required rotation of the array by $k$ times to the right.

Complexity

In this method we have managed to reduce the space complexity from O(n) to a constant space. This method still takes $\cal{O(n)}$ Time but $\cal{O(1)}$ Space.

Implementation

	//-------------------------------------------------------------------------------------
	//------------- METHOD 3 --------------------------------------------------------------
	/**
	* This method first reverses first N - k and last k elements separately.
	* Finally reverse the whole array to give the required output array.
	*
	* This method requires O(n) time and O(1) space.
	*
	* @param nums input array to reverse.
	* @param k number of times to rotate the intput.
	*/
	public void rotate3(int[] nums, int k) {
	k = k % nums.length;
	if (k == 0 || nums.length < 2) return;
	int N = nums.length;
	reverse(nums, 0, N - k);
	reverse(nums, N - k, N);
	reverse(nums, 0, N);
	} // rotate3
	//-------------------------------------------------------------------------------------
	/**
	* Reverses the array from index start (inclusive) to index end (exclusive)
	* @param nums input array
	* @param start start index
	* @param end end index
	*/
	private void reverse(int[] nums, int start, int end) {
	while (start < end) {
	swap(nums, start, end-1);
	start++;
	end--;
	}
	} // reverse
	//-------------------------------------------------------------------------------------
	/**
	* Swaps two elements in an array at index i and j.
	* @param nums input array
	* @param i index i
	* @param j index j
	*/
	private void swap(int[] nums, int i, int j) {
	int temp = nums[i];
	nums[i] = nums[j];
	nums[j] = temp;
	} // swap

view raw ArrayRotation.java hosted with ❤ by GitHub

---

---

---

Permutations of a String - Unique Characters and Duplicates

$\mathtt{REFERENCE}$ @ Geek For Geeks

Permutation

Permutation of a set is simply a different ordering of the elements. For the given string, we can order the characters into different locations producing different string. All such strings constitute the permutation of that string.

Example: Permutation of a string XYZ are:

XYZ XZY YXZ YZX ZXY ZYX

For given string of length $n$ there are total of $n!$ permutations.

Algorithm - For String with Unique Characters

As explained HERE, following image explains how we can compute the permutations of given string.

In this algorithm,

• For each character in the input String:
1. Select the character and keep it fixed.
2. Compute permutations of remaining $n-1$ characters.
3. Finally append all those permutations of $n-1$ characters to the character selected in the $Step\ 1$.

Algorithm - For String with Duplicate Characters

Algorithms described above will also work with strings with duplicate characters. However, the algorithm will also produce duplicate results. So a simple solution will be to check for unique solutions, probably using Hashing, in the above solution.

Problem

The problem with this solution is, for a string with two many duplicate characters, it will end up computing all $n!$ solutions while there are very few number of solutions.

Example: String AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA has only one permutation which the input string itself.

But the above algorithm will be doing a lot of unnecessary computation.

Solution

So for string with duplicate entries, we can write efficient solution. For string with all unique characters, its performance will still become $n!$.

The solution is very much similar to the Coin Exchange Problem.

In this algorithm,

1. We can create Frequency table which keeps count of all unique characters in the string.
2. For each unique character if it count is Greater Than 0:
   1. Append the character to Current Permutation. When length of the Current Permutation is equal to the length of input string, we have one solution.
   2. Decrease count by 1.
   3. Recurse through the same updated Map.
   4. Reset or Increase the count by 1.

Implementation (Both Method)

Following is the implementation for both the method.

	/* File: Permutations.java
	* Created: 10/1/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	import java.util.*;
	//=======================================================================================
	/**
	* @author Sabbir Manandhar manandharsabbir@gmail.com
	* @version 1.0
	*/
	public class Permutations {
	public static void main(String[] args) {
	List<String> permutations = permutationWithoutDuplicates("ABCD");
	for (String permutation : permutations)
	System.out.println(permutation);
	System.out.println();
	permutations = permuteWithDuplicates("AAABB");
	for (String permutation : permutations)
	System.out.println(permutation);
	} // main
	//-------------------------------------------------------------------------------------
	//------ Solution 1: For Input with Unique Characters Only -----------
	/**
	* Computes permutation of given string without any duplicate characters.
	* For string duplicate character, results will contain duplicate entries.
	* @param s input string
	* @return List of permutations
	*/
	public static List<String> permutationWithoutDuplicates(String s) {
	char[] chars = s.toCharArray();
	List<String> permutations = new ArrayList<>();
	permutationWithoutDuplicatesHelper(chars, 0, permutations);
	return permutations;
	} // permutationWithoutDuplicates
	//-------------------------------------------------------------------------------------
	/**
	* Recursive helper method to compute permutations of a character array without duplicates.
	* @param chars input character array
	* @param cursor pointer to current location considered. Characters before this pointer and kept fixed.
	* @param permutations List holding resulting permutations
	*/
	private static void permutationWithoutDuplicatesHelper(char[] chars, int cursor, List<String> permutations) {
	if (cursor == chars.length) {
	permutations.add(new String(chars));
	return;
	}
	for (int i = cursor; i < chars.length; i++) {
	swap(chars, cursor, i);
	// keep the selected character fixed and compute permutations of remaining characters
	permutationWithoutDuplicatesHelper(chars, cursor + 1, permutations);
	swap(chars, cursor, i);
	}
	} // permutationWithoutDuplicatesHelper
	//-------------------------------------------------------------------------------------
	/**
	* Utility method to swap two characters in the given character array.
	* @param chars input character array
	* @param i first index to swap.
	* @param j second index to swap.
	*/
	private static void swap(char[] chars, int i, int j) {
	if (i == j) return;
	char temp = chars[i];
	chars[i] = chars[j];
	chars[j] = temp;
	} // swap
	//------ END Solution 1 ---------------------------------------------------------------
	//-------------------------------------------------------------------------------------
	//------ Solution 2: For Input with Duplicate Characters ------------------------------
	/**
	* Computes permutation of an string with Duplicate characters.
	* Obviously, it will also work for the string with unique characters.
	* @param s input string.
	* @return Permutations of given input.
	*/
	public static List<String> permuteWithDuplicates(String s) {
	char[] chars = s.toCharArray();
	Map<Character, Integer> frequencyMap = createFrequencyMap(chars);
	List<String> results = new ArrayList<>();
	permuteWithDuplicatesHelper(frequencyMap, new char[s.length()], 0, results);
	return results;
	} // permuteWithDuplicates
	//-------------------------------------------------------------------------------------
	/**
	* Recursive helper method to compute permutations of a string with duplicate characters.
	* @param frequencyMap Map holding character counts of input.
	* @param permutation current permutation
	* @param cursor current location in permutation
	* @param results List of all permutations of input.
	*/
	private static void permuteWithDuplicatesHelper(Map<Character, Integer> frequencyMap, char[] permutation, int cursor, List<String> results) {
	if (cursor == permutation.length) {
	results.add(new String(permutation));
	return;
	}
	for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
	if (entry.getValue() > 0) {
	permutation[cursor] = entry.getKey();
	entry.setValue(entry.getValue() - 1);
	permuteWithDuplicatesHelper(frequencyMap, permutation, cursor + 1, results);
	entry.setValue(entry.getValue() + 1);
	}
	}
	} // permuteWithDuplicatesHelper
	//-------------------------------------------------------------------------------------
	/**
	* Utility method to create character counts as a Map.
	* @param chars input character array
	* @return Character Counts Map.
	*/
	private static Map<Character, Integer> createFrequencyMap(char[] chars) {
	Map<Character, Integer> result = new HashMap<>();
	for (Character c : chars) {
	if (result.containsKey(c)) {
	result.put(c, result.get(c) + 1);
	} else {
	result.put(c, 1);
	}
	}
	return result;
	} // createFrequencyMap
	//------ END Solution 2 ---------------------------------------------------------------
	} // Permutations

view raw Permutations.java hosted with ❤ by GitHub

Time Complexity

There are $n!$ permutations. We need to compute each of these permutations. $\therefore$ The complexity of this approach is $\cal{\theta(n!)}$ which is exponential with the size of the input.

---

---

---

Extract Text From PPTX using POI - java.lang.ArrayStoreException

I had been trying to extract textual content from PPTX file using Apache POI. Then I struggled with following exception.

 java.lang.ArrayStoreException 
  at java.lang.System.arraycopy(Native Method) 
  at org.apache.xmlbeans.impl.values.XmlObjectBase._typedArray(XmlObjectBase.java:409) 
  at org.apache.xmlbeans.impl.values.XmlObjectBase.selectPath(XmlObjectBase.java:457) 
  at org.apache.xmlbeans.impl.values.XmlObjectBase.selectPath(XmlObjectBase.java:415) 
  at org.apache.poi.xslf.usermodel.XSLFDrawing.<init>(XSLFDrawing.java:44) 
  at org.apache.poi.xslf.usermodel.XSLFSheet.initDrawingAndShapes(XSLFSheet.java:170) 
  at org.apache.poi.xslf.usermodel.XSLFSheet.getShapes(XSLFSheet.java:157) 
      

Solution

Well the problem turns out to be version of library I had been using.

I was running xmlbeans 2.3. Upgrading to 2.6 resolves the issue.

---

---

---

Power Sets

For a given set of items, power set is the set of all subsets of it. If there are $n$ items in the given set, then there are $2^n$ subsets.

Generating Power Sets

One of the way to generate Power Sets is using binary numbers. For each of the set in the power sets, we have $two$ choices for an item in the given set - include it or not include it. This can be denoted as 1 and 0. We know that, if we have $n$ bits, then we can form $2^n$ numbers using a sequence $0$ and $1$ $n$ bits. Similarly, if have $n$ items set, then each of the binary number from $0$ to $2^n - 1$ will represent a sub set. If a bit is $ith$ bit is $0$, then the $ith$ item is excluded from the subset, else we include it.

Following picture should clearly explain this concept.

Implementation

	/* File: PowerSetGenerator.java
	* Created: 9/28/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	//=======================================================================================
	import java.util.ArrayList;
	import java.util.List;
	//=======================================================================================
	/**
	* @author Sabbir Manandhar manandharsabbir@gmail.com
	* @version 1.0
	*/
	public class PowerSetGenerator {
	/**
	* Driver method
	* @param args
	*/
	public static void main(String[] args) {
	PowerSetGenerator generator = new PowerSetGenerator();
	for (List<Character> set : generator.generatePowerSets(new char[]{'A', 'B', 'C', 'D'})) {
	System.out.println(set.toString());
	}
	} // main
	//-------------------------------------------------------------------------------------
	/**
	* For each of the number from 0 to 2^n - 1, generate a sub set represented by the number.
	* Assemble all the subsets together to generate Power Set.
	* @param set Input Set.
	* @return Power Set of the given input set.
	*/
	public List<List<Character>> generatePowerSets(char[] set) {
	List<List<Character>> powerSets = new ArrayList<>();
	int max = 1 << set.length; // max = 2^n formed by right shifting 1 for n times
	for (int i = 0; i < max; i++) {
	powerSets.add(convertNumberToSet(set, i)); // for each binary number from 0 to 2^n - 1, generate sub set
	}
	return powerSets;
	} // generatePowerSets
	//-------------------------------------------------------------------------------------
	/**
	* Generate subset represented by given number
	* @param set Given Input set.
	* @param number Given number which represents a subset
	* @return Subset represented by given number
	*/
	private List<Character> convertNumberToSet(char[] set, int number) {
	List<Character> subset = new ArrayList<>();
	int index = 0;
	for (int i = 1; index < set.length; i = i << 1, index++) {
	if ((number & i) == i) { // determine if index th bit is 1 or 0 in the given number
	subset.add(set[index]); // include index th number if corresponding bit is 1 in the given number
	}
	}
	return subset;
	} // convertNumberToSet
	} // PowerSetGenerator

view raw PowerSetGenerator.java hosted with ❤ by GitHub

Time Complexity

There are $2^n$ subsets. We can't avoid computation of each subset. Here in this method, to determine each subset, we traverse through each of the item. $\therefore$ The complexity of this approach is $\cal{O(n2^n)}$ which is exponential with the size of the input.

---

---

---

Mockito: Mocking Final Methods With PowerMockito

Introduction

Mockito makes the testing job easier. But Mockito itself has its own limitations.

Poblem with Mocking final Method

One of such limitations is mocking of final method. When we try to mock a final method, as we normally mock other methods, it is not mocke. Real implementation of that method is executed. In fact, Mockito does not even complains about it. The real implementation is run without any Warning or Exception.

  /* File:    JobsTest.java
 * Created: 9/24/2018
 * Author:  Sabbir Manandhar
 *
 * Copyright (c) 2018 Hogwart Inc.
 */

package com.hogwart;


import org.junit.Assert;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.mockito.Mockito;
import org.powermock.modules.junit4.PowerMockRunner;

import java.util.ArrayList;
import java.util.List;

//=======================================================================================


/**
 * @author Sabbir Manandhar
 * @version 1.0
 */
@RunWith(PowerMockRunner.class)
public class JobsTest {

  //-------------------------------------------------------------------------------------

  @Test
  public void testGetJobCount() {
    List expectedJobIds = new ArrayList();
    expectedJobIds.add("J456");
    expectedJobIds.add("J459");

    Jobs jobs = Mockito.mock(Jobs.class);
    Mockito.doReturn(expectedJobIds).when(jobs).getJobIds();

    List jobIds = jobs.getJobIds(); // Here we expect to receive mocked Job IDs
    Assert.assertEquals(expectedJobIds.size(), jobIds.size());
  } // testGetJobCount

} // JobsTest

//=======================================================================================

/**
 * Class Representing Jobs Queue
 */
class Jobs {

  //-------------------------------------------------------------------------------------

  /**
   * Retrieves List of Job IDs and return
   * @return List of Job IDs
   */
  public final List getJobIds() {
    List result = new ArrayList();

    // ...
    // Implementations to compute list of job ids
    // ...

    return result;
  } // getJobIds

  // Other Methods

} // Jobs

      

Here the test will fail because we are expecting mocked job ids of size 2, but the actual implementation is run and an empty list is returned.

Solution - PowerMockito

Even though Mockito cannot mock final methods, they can be mocked using PowerMockito.

We need to use following in our code to fix our test.

  
@RunWith(PowerMockRunner.class)
@PrepareForTest(Jobs.class)
public class JobsTest {

  ...

    Jobs jobs = PowerMockito.mock(Jobs.class);
    PowerMockito.doReturn(expectedJobIds).when(jobs).getJobIds();

      

Following is the complete working solution:

  
/* File:    JobsTest.java
 * Created: 9/24/2018
 * Author:  Sabbir Manandhar
 *
 * Copyright (c) 2018 Hogwart Inc.
 */

package com.hogwart;


import org.junit.Assert;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.mockito.Mockito;
import org.powermock.api.mockito.PowerMockito;
import org.powermock.core.classloader.annotations.PrepareForTest;
import org.powermock.modules.junit4.PowerMockRunner;

import java.util.ArrayList;
import java.util.List;

//=======================================================================================


/**
 * @author Sabbir Manandhar
 * @version 1.0
 */
@RunWith(PowerMockRunner.class)
@PrepareForTest(Jobs.class)
public class JobsTest {

  //-------------------------------------------------------------------------------------

  @Test
  public void testGetJobCount() {
    List expectedJobIds = new ArrayList();
    expectedJobIds.add("J456");
    expectedJobIds.add("J459");

    Jobs jobs = PowerMockito.mock(Jobs.class);
    PowerMockito.doReturn(expectedJobIds).when(jobs).getJobIds();

    List jobIds = jobs.getJobIds(); // Here we expect to receive mocked Job IDs
    Assert.assertEquals(expectedJobIds.size(), jobIds.size());
  } // testGetJobCount

} // JobsTest

//=======================================================================================

/**
 * Class Representing Jobs Queue
 */
class Jobs {

  //-------------------------------------------------------------------------------------

  /**
   * Retrieves List of Job IDs and return
   * @return List of Job IDs
   */
  public final List getJobIds() {
    List result = new ArrayList();

    // ...
    // Implementations to compute list of job ids
    // ...

    return result;
  } // getJobIds

  // Other Methods

} // Jobs


      

Note

If you spy a class and mock a final method, then you might get some exception messages when you try to run the test class. One of possible exception is org.mockito.exceptions.misusing.WrongTypeOfReturnValue.

---

---

---

LeetCode: Word Search in 2D Matrix of characters

Difficulty Level: $\mathtt{MEDIUM}$
This is a LeetCode question. Find the DESCRIPTION HERE

Solution

This problem can be solved using Depth First Search (DFS) which will employ necessary Backtracking. Starting from any cell, we look for a match of characters from the beginning of input word. If there is a match, we look for the next character in the input word in the neighboring unvisited cells of the board. When the whole word is found, we return true.

Backtracking

When there is a match for a character in a word, we move to next character and also move to next neighbor. For the given cell there are Four possible neighbors. At a time, we select one neighbor and expand the search. It can happen that one neighbor might lead to a path where only some characters are matched while other neighbor can lead to the path where whole word is matched. So if we select the first neigbor, it will ultimately lead the end where we don't have any match. At such time, we should be able to backtrack and follow different path to look for possible desirable path.

Implementation

Following is the implemenation of the backtracking solution using DFS discussed above.

	/* File: WordSearch.java
	* Created: 9/19/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 WorldLingo Inc.
	*/
	//=======================================================================================
	/**
	* @author Sabbir Manandhar manandharsabbir@gmail.com
	* @version 1.0
	*/
	public class WordSearch {
	/**
	* Verifies if the given word can be found in the given board by moving left, right, top and bottom
	* unvisited cells of the board.
	* @param board Given board.
	* @param word Given word.
	* @return True if the word is found in the board, False otherwise.
	*/
	public boolean exist(char[][] board, String word) {
	int ROW = board.length;
	int COL = board[0].length;
	for (int row = 0; row < ROW; row++) {
	for (int col = 0; col < COL; col++) {
	if (dfs(board, new boolean[ROW][COL], word, 0, row, col, ROW, COL)) return true;
	}
	}
	return false;
	} // exist
	//-------------------------------------------------------------------------------------
	/**
	* Searches for the occurrence of characters in given word from the position <code>cursor</code>
	* in the given 2D board starting from given row and col.
	*
	* @param board Input 2D board of characters
	* @param visited Visited characters in the cell
	* @param word Given input word
	* @param cursor current location in the given word
	* @param row current row in the board
	* @param col current column in the board
	* @param ROW number of Rows in the board
	* @param COLUMN number of Columns in the board
	* @return True if the word occurs in the board, False otherwise
	*/
	public boolean dfs(char[][] board, boolean[][] visited, String word, int cursor, int row, int col, int ROW, int COLUMN) {
	if (cursor == word.length()) return true;
	if (!inBoard(row, col, ROW, COLUMN)) return false;
	if (visited[row][col]) return false;
	if (board[row][col] == word.charAt(cursor)) {
	visited[row][col] = true;
	boolean exist = dfs(board, visited, word, cursor + 1, row + 1, col, ROW, COLUMN) ||
	dfs(board, visited, word, cursor + 1, row, col + 1, ROW, COLUMN) ||
	dfs(board, visited, word, cursor + 1, row - 1, col, ROW, COLUMN) ||
	dfs(board, visited, word, cursor + 1, row, col - 1, ROW, COLUMN);
	if (exist) return true;
	visited[row][col] = false;
	} else {
	return false;
	}
	return false;
	} // dfs
	//-------------------------------------------------------------------------------------
	/**
	* Verify if given row and column are withing the limit
	* @param row given row
	* @param col given column
	* @param ROW ROW limit
	* @param COLUMN Column limit
	* @return True if the row and column are within the limit, False otherwise
	*/
	private boolean inBoard(int row, int col, int ROW, int COLUMN) {
	return row >= 0 && row < ROW && col >= 0 && col < COLUMN;
	} // inBoard
	} // WordSearch

view raw WordSearch.java hosted with ❤ by GitHub

Time Complexity

The exist() method runs two loops for $row \times column$ times and the dfs() method can also run upto $row \times column$ times.
$\therefore$ The complexity of this approach is $\cal{O(mn)^2}$ where $m\ = \ number\ of\ rows$ and $n\ = \ number\ of\ columns$.

Space Complexity

Here we are using extra 2D matrix visited to keep track of cells which are already visited.
$\therefore$The space complexity is $\cal{O(mn)}$.
This can be reduced to $\cal{O(1)}$ by modifying the input board to update each character with special character to mark that it has been visited. The modified character can be reset afterwards.

---

---

---

HackerRank - Flatland Space Stations (EASY)

Difficulty Level: $\mathtt{EASY}$
This is a HackerRank question. Find the DESCRIPTION HERE

	/* File: FlatlandSpaceStations.java
	* Created: 9/12/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	//=======================================================================================
	import java.util.Arrays;
	/**
	* @author Sabbir Manandhar manandharsabbir@gmail.com
	* @version 1.0
	*/
	public class FlatlandSpaceStations {
	/**
	* main method
	*
	* @param args
	*/
	public static void main(String[] args) {
	System.out.println(flatlandSpaceStations(6, new int[]{0, 1, 2, 4, 3, 5})); // expected 0
	System.out.println(flatlandSpaceStations(5, new int[]{0, 4})); // expected 2
	} // main
	//-------------------------------------------------------------------------------------
	/**
	* Computes the maximum distance among all distances from a city to nearest space station
	*
	* @param n number of cities
	* @param c array of cities with space stations
	* @return maximum distance
	*/
	static int flatlandSpaceStations(int n, int[] c) {
	Arrays.sort(c);
	int stationIndex = 0;
	int prevStation = c[stationIndex];
	int nextStation = prevStation;
	int max = -1;
	for (int i = 0; i < n; i++) {
	int cityDistance = Math.min(Math.abs(i - prevStation), Math.abs(i - nextStation));
	max = Math.max(max, cityDistance);
	if (i == nextStation) {
	stationIndex++;
	prevStation = nextStation;
	nextStation = stationIndex < c.length ? c[stationIndex] : prevStation;
	}
	}
	return max;
	} // flatlandSpaceStations
	} // FlatlandSpaceStations

view raw FlatlandSpaceStations.java hosted with ❤ by GitHub

Complexity

The time complexity is $\cal{O(nlogn)}$.

The space complexity is also $\cal{O(n)}$.

---

---

---

Binary Tree Inversion

Difficulty Level: $\mathtt{EASY}$ @ This is a LeetCode question found HERE

What is Tree Inversion?

Tree Inversion means to swap all the left and right child for all the nodes in the tree. Following picture should explain this:

Solution

The solution is itself obvious from the definition of inversion itself. We need to swap the children of each of the node. Therefore we need to traverse through each of the node and swap their children. So the time complexity is going to $\cal{\theta(n)}$, $n$ being the number of nodes in the tree.

This can be solved either Recursively or Iteratively. In either way, we traverse through all the nodes and swap the children.

Following is the implementation for both the methods.

	/* File: InvertBinaryNode.java
	* Created: 8/30/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	//=======================================================================================
	import java.util.Stack;
	/**
	* Class to invert a Binary Tree.
	* Inversion of a binary tree means to invert all the left and right node. That is
	* make left child right and right child left.
	*
	* @author Sabbir Manandhar
	* manandharsabbir@gmail.com
	* @version 1.0
	*/
	public class InvertBinaryTree {
	/**
	* This is a recursive method to invert the tree.
	* @param root root of the tree to invert
	* @return root of inverted tree
	*/
	public TreeNode invertTree(TreeNode root) {
	if (root == null) return root;
	invertTree(root.left);
	invertTree(root.right);
	TreeNode temp = root.left;
	root.left = root.right;
	root.right = temp;
	return root;
	} // invertTree
	//-------------------------------------------------------------------------------------
	/**
	* This is iterative method to invert the tree
	* @param root root of the tree to invert
	* @return root of inverted tree
	*/
	public TreeNode invertTreeIterative(TreeNode root) {
	if (root == null) return root;
	Stack<TreeNode> stack = new Stack<>();
	stack.push(root);
	while (!stack.isEmpty()) {
	TreeNode node = stack.pop();
	if (node.left != null) {
	stack.push(node.left);
	}
	if (node.right != null) {
	stack.push(node.right);
	}
	TreeNode temp = node.left;
	node.left = node.right;
	node.right = temp;
	}
	return root;
	}
	} // InvertBinaryTree
	//=======================================================================================
	class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	/**
	* Constructor
	* @param val
	*/
	public TreeNode(int val) {
	this.val = val;
	} // TreeNode
	} // TreeNode

view raw InvertBinaryTree.java hosted with ❤ by GitHub

Complexity

In both the methods we visit each of the node once and swap the children. Swapping actions is constant time. $\therefore$ The time complexity is $\cal{O(n)}$.

As of space, both the method will mainain a stack of nodes. $\therefore$ The space complexity is also $\cal{O(n)}$.

---

---

---

Git: Rename a Local and Remote Branch

$\mathtt{REFERENCE}$ @ StackOverflow

If you ever need to Rename a branch which has also been pushed to the remote, you can follow the following steps:

1. Rename Local Branch

If you are on the branch you want to rename, you can use following command:

git branch -m <new_branch_name>

If you are on a different branch, then use the following command:

git branch -m <old_branch_name> <new_branch_name>

2. Delete the Old_Name Branch and Push the New_Name Branch

git push origin :<old_branch_name> <new_branch_name>

3. Reset the UpStream Branch for the New_Name Local Branch

git push origin -u <new_branch_name>

---

---

---

Git: Delete a Branch from Local and Remote

$\mathtt{REFERENCE}$ @ StackOverflow

1. Delete Local Branch

Local branch can be deleted using one of the following commands:

git branch -d <branch_name>

git branch -D <branch_name>

Note: The -d option is an alias for --delete, which only deletes the branch if it has already been fully merged in to its upstream branch.

You could also use -D, which is an alias for --delete --force, which deletes the branch irrespective of its merged status.

2. Delete Remote Branch

As of Git V1.7.0, you can delete a remote branch using

git push <remote_name> --delete <branch_name>

---

---

---

Git: Editing the Pushed Remote Commit Message and Recent Local Commit

Editing the Commit Message Which is already Pushed to Remote

Sometimes you might need to change the git commit messages which you have already pushed to the remote. It is unfortunate that we face such situation, but fortunately git provides a mechanism to do this. Following steps explain to change the commit message.

1. git rebase -i <commit hash you want to change>^


2. This will open your default editor (usually vi) with a list of commits and actions for each one. By default, the action is pick. You will be able to edit all the commit messages of the commit whose hash you have provited and those above it.


3. For any commit you wish to change the message, change pick to reword.


4. Save and quit (in vi: :wq).


5. For each such commit, you'll get an editor to edit the commit message. Change it as you see fit, save and quit.


6. Once you're done editing all the commit messages, you'll return to the command prompt, and have a new tree with the updated messages.


7. You can now upload them to github by using git push origin --force.


8. If you just need to fix your last commit, you can replace steps 1-4 with git commit --amend.

Editing Your Most Recent Local Commit

Editing Message

If there is a case when you just made a commit with a wrong message, then you can edit the message using following command

git commit --amend -m "New commit message"

Adding a Missing File

It can also be a case that you might have missed to add a file to your recent commit. In that case, you can still add the missing file to the same commit without deleting the commit and committing again. It can be done using following command.

git add file.file
git commit --amend --no-edit

--no-edit means that the commit message does not change.

---

---

---

Git: Git Stash Commands

1. Git Stash Save

You can give a custom message to a Git Stash. Following is the command:

git stash save "message of your wish"

2. Git Stash List

You can see the list of all the stashes currently stashed.

git stash list

3. Git Stash - Specific Stash details

You can view detail of a specific stash in the stash list.

git stash show -p stash@{1}

Enter different number to see details of different stash.

---

---

---

Git: Copy a File from another Branch

Following command can be used for copyig a file from another branch.

git checkout <branch_name> path/to/new/file

---

---

---

Quick Sort of a Linked List

Quick Sort - Main Idea

1. Select a node (Probably Head node) as Pivot Node
2. Traverse through the remaining nodes to divide into two lists - one containing smaller or equal values and another containing larger values.
3. Recursively apply the sort algorithm to two smaller lists. As a base case, the recursive method will return the input when the input list is of size 1 or 0.
4. Merge First List, Pivot and Second List

Partition

Partition Method selects head node of given list as Pivot node. Based upon this pivot, the input list is divided into two smaller lists - First one with smaller or equal value and Second one with larger values.

Return Type

This method will return an array of Three Nodes - First one is head of first list, Second is Pivot node and the Third is the head of the second list.

	/**
	* Partitions the given linked list. Takes O(n) time and O(1) space
	*
	* @param head head node of the linked list to be partitioned
	* @return array of 3 elements, 1. head of first half 2. Pivot node and 3. head of second half
	*/
	public static ListNode[] partition(ListNode head) {
	ListNode pivot = head;
	ListNode node = head.next;
	pivot.next = null;
	ListNode firstHalfHead = null;
	ListNode secondHalfHead = null;
	while (node != null) {
	ListNode curr = node;
	node = node.next;
	if (curr.val <= pivot.val) {
	curr.next = firstHalfHead;
	firstHalfHead = curr;
	} else {
	curr.next = secondHalfHead;
	secondHalfHead = curr;
	}
	}
	return new ListNode[]{firstHalfHead, pivot, secondHalfHead};
	} // partition

view raw QuickSortLinkedList.java hosted with ❤ by GitHub

Sort Helper

sortHelper() is the recursive method that recursively sorts the smaller lists to finally return the sorted list.

Return Type

This method returns an array of two nodes - Head and Tail nodes of the Sorted List. They are required to ultimately merge the smaller lists and pivot.

	/**
	* Recursive helper method to sort the list. Recursively sorts the partitioned lists
	* and finally return the merged list which is sorted.
	* Average Case Time Complexity is O(nLogn) and Space Complexity is O(1)
	* @param head
	* @return
	*/
	public static ListNode[] sortHelper(ListNode head) {
	if (head == null || head.next == null) return new ListNode[]{head, head};
	ListNode[] partitions = partition(head);
	ListNode[] firstHeadTail = sortHelper(partitions[0]);
	ListNode[] secondHeadTail = sortHelper(partitions[2]);
	return merge(firstHeadTail, partitions[1], secondHeadTail);
	} // sortHelper

view raw QuickSortLinkedList.java hosted with ❤ by GitHub

Merge

merge() method merges the two smaller sorted list and the pivot.

Return Type

This method returns an array of two nodes - Head and Tail nodes of the Sorted List. They are required to ultimately merge the smaller lists and pivot.

	/**
	* Merges Two sorted lists and a pivot in between them. First list contains elements smaller than
	* or equal to pivot and Seconds list contains elements greater than pivot
	* Takes O(1) time and O(1) space
	*
	* @param firstHeadTail Array of Head and Tail Nodes of first sorted list
	* @param pivot Pivot node
	* @param secondHeadTail Array of Head and Tail Nodes of seconds sorted list
	* @return
	*/
	public static ListNode[] merge(ListNode[] firstHeadTail, ListNode pivot, ListNode[] secondHeadTail) {
	if (firstHeadTail[1] != null && secondHeadTail[1] != null) {
	firstHeadTail[1].next = pivot;
	pivot.next = secondHeadTail[0];
	return new ListNode[]{firstHeadTail[0], secondHeadTail[1]};
	} else if (firstHeadTail[1] != null) {
	firstHeadTail[1].next = pivot;
	return new ListNode[]{firstHeadTail[0], pivot};
	} else {
	pivot.next = secondHeadTail[0];
	return new ListNode[]{pivot, secondHeadTail[1]};
	}
	} // merge

view raw QuickSortLinkedList.java hosted with ❤ by GitHub

Complete Implementation

	/* File: SortLinkedList.java
	* Created: 8/21/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	//=======================================================================================
	/**
	* @author Sabbir Manandhar
	* manandharsabbir@gmail.com
	* @version 1.0
	*/
	public class QuickSortLinkedList {
	/**
	* main method
	* @param args
	*/
	public static void main(String[] args) {
	ListNode head = new ListNode(6);
	ListNode newNode = new ListNode(7);
	newNode.next = head;
	head = newNode;
	newNode = new ListNode(1);
	newNode.next = head;
	head = newNode;
	newNode = new ListNode(3);
	newNode.next = head;
	head = newNode;
	newNode = new ListNode(2);
	newNode.next = head;
	head = newNode;
	newNode = new ListNode(9);
	newNode.next = head;
	head = newNode;
	newNode = new ListNode(23);
	newNode.next = head;
	head = newNode;
	newNode = new ListNode(5);
	newNode.next = head;
	head = newNode;
	newNode = new ListNode(5);
	newNode.next = head;
	head = newNode;
	newNode = new ListNode(15);
	newNode.next = head;
	head = newNode;
	System.out.println(sort(head));
	} // main
	//-------------------------------------------------------------------------------------
	/**
	* Method to sort
	* @param head head of the list to sort
	* @return head of sorted list
	*/
	public static ListNode sort(ListNode head) {
	return sortHelper(head)[0];
	} // sort
	//-------------------------------------------------------------------------------------
	/**
	* Recursive helper method to sort the list. Recursively sorts the partitioned lists
	* and finally return the merged list which is sorted.
	* Average Case Time Complexity is O(nLogn) and Space Complexity is O(1)
	* @param head
	* @return
	*/
	public static ListNode[] sortHelper(ListNode head) {
	if (head == null || head.next == null) return new ListNode[]{head, head};
	ListNode[] partitions = partition(head);
	ListNode[] firstHeadTail = sortHelper(partitions[0]);
	ListNode[] secondHeadTail = sortHelper(partitions[2]);
	return merge(firstHeadTail, partitions[1], secondHeadTail);
	} // sortHelper
	//-------------------------------------------------------------------------------------
	/**
	* Merges Two sorted lists and a pivot in between them. First list contains elements smaller than
	* or equal to pivot and Seconds list contains elements greater than pivot
	* Takes O(1) time and O(1) space
	*
	* @param firstHeadTail Array of Head and Tail Nodes of first sorted list
	* @param pivot Pivot node
	* @param secondHeadTail Array of Head and Tail Nodes of seconds sorted list
	* @return
	*/
	public static ListNode[] merge(ListNode[] firstHeadTail, ListNode pivot, ListNode[] secondHeadTail) {
	if (firstHeadTail[1] != null && secondHeadTail[1] != null) {
	firstHeadTail[1].next = pivot;
	pivot.next = secondHeadTail[0];
	return new ListNode[]{firstHeadTail[0], secondHeadTail[1]};
	} else if (firstHeadTail[1] != null) {
	firstHeadTail[1].next = pivot;
	return new ListNode[]{firstHeadTail[0], pivot};
	} else {
	pivot.next = secondHeadTail[0];
	return new ListNode[]{pivot, secondHeadTail[1]};
	}
	} // merge
	//-------------------------------------------------------------------------------------
	/**
	* Partitions the given linked list. Takes O(n) time and O(1) space
	*
	* @param head head node of the linked list to be partitioned
	* @return array of 3 elements, 1. head of first half 2. Pivot node and 3. head of second half
	*/
	public static ListNode[] partition(ListNode head) {
	ListNode pivot = head;
	ListNode node = head.next;
	pivot.next = null;
	ListNode firstHalfHead = null;
	ListNode secondHalfHead = null;
	while (node != null) {
	ListNode curr = node;
	node = node.next;
	if (curr.val <= pivot.val) {
	curr.next = firstHalfHead;
	firstHalfHead = curr;
	} else {
	curr.next = secondHalfHead;
	secondHalfHead = curr;
	}
	}
	return new ListNode[]{firstHalfHead, pivot, secondHalfHead};
	} // partition
	} // QuickSortLinkedList
	//=======================================================================================
	class ListNode {
	ListNode next;
	int val;
	//-------------------------------------------------------------------------------------
	public ListNode(int data) {
	this.val = data;
	}
	//-------------------------------------------------------------------------------------
	public String toString() {
	StringBuilder sb = new StringBuilder();
	ListNode node = this;
	while (node != null) {
	sb.append(node.val + " ");
	node = node.next;
	}
	return sb.toString();
	} // toString
	} // ListNode

view raw QuickSortLinkedList.java hosted with ❤ by GitHub

---

---

---

Merge Two Sorted Lists - Different Implementations

$\mathtt{REFERENCE}$ @ LeetCode

$\mathtt{RELATED\ PROBLEM}$ @ Sort a LinkedList Using Merge Sort

Main Idea

The main idea to merge two sorted linked lists is to pick the node out of the two head nodes whose value is smaller and move that head to its next node. Selected node will be placed at the tail of the result linked list. We continue this process until we have no more nodes in either of the lists.

When one of the head becomes null, we no longer need to traverse through the other list. Because other list is already sorted and all its elements will be smaller than the elements in the resulting list (WHY?), we can simply append this list to the result list.

Obviously this can be implemented in different ways. Following are few :

Method 1

In this method:

1. If one of the list is empty, return other list.
2. Otherwise, select smaller head node and set it as Head and Tail of the result. Move head of the selected list to next.
3. Repeat, until ONE of the list is not empty, to select smaller head, move head to next and append the selected node to the Tail of the result.
   1. At any time, if one of the head becomes null, append other list to the tail of the result.
4. Return Head

  /**
   * Merge Two sorted Linked Lists
   * @param l1 first sorted linked list
   * @param l2 second sorted linked list
   * @return Head of the sorted linked list
   */
  ListNode merge(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;

    ListNode head, tail;
    // initialize the head and tail node of result list with one of the heads of two given lists
    if (l1.val < l2.val) {
      head = tail = l1;
      l1 = l1.next;
    } else {
      head = tail = l2;
      l2 = l2.next;
    }
    while(l1 != null || l2 != null) {
      if (l1 == null) {
        // if l1 is null, we can append l2 to the result and we are done
        tail.next = l2;
        break;
      }

      if (l2 == null) {
        // if l2 is null, we can append l1 to the result and we are done
        tail.next = l1;
        break;
      }

      // otherwise select and append smaller of the two head nodes
      if (l1.val < l2.val) {
        tail.next = l1;
        tail = l1;
        l1 = l1.next;
      } else {
        tail.next = l2;
        tail = l2;
        l2 = l2.next;
      }
    } // end while

    return head;
  } // merge
    

Method 2

In this method:

1. If one of the list is empty, return other list.
2. Otherwise, select smaller head node and set it as Head and Tail of the result. Move head of the selected list to next.
3. Repeat, until BOTH of the list is not empty, to select smaller head, move head to next and append the selected node to the tail of the result.
4. Append none empty list to the Tail of the result.
5. Return Head

  /**
   * Merge Two sorted Linked Lists
   * @param l1 first sorted linked list
   * @param l2 second sorted linked list
   * @return Head of the sorted linked list
   */
ListNode merge(ListNode l1, ListNode l2) {
  if (l1 == null) return l2;
  if (l2 == null) return l1;

  ListNode head, tail;
  // initialize the head and tail node of result list with one of the heads of two given lists
  if (l1.val < l2.val) {
    head = tail = l1;
    l1 = l1.next;
  } else {
    head = tail = l2;
    l2 = l2.next;
  }
  while(l1 != null && l2 != null) {
    // select smaller node and append to Tail of the result list
    if (l1.val < l2.val) {
      tail.next = l1;
      tail = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      tail = l2;
      l2 = l2.next;
    }
  }
  // Append the remaining nodes of one list, if any
  if (l1 == null) {
    tail.next = l2;
  } else if (l2 == null) {
    tail.next = l1;
  }

  return head;
} // merge
    

Method 3 (Same Idea - But Simpler and Easier to Perceive)

In this method:

1. Initialize Head node with a dummy data and Tail node with the same node.
2. Repeat, until BOTH of the list is not empty, to select smaller head, move head to next and append the selected node to the Tail of the result.
3. Append none empty list to the Tail of the result.
4. Return Head.next

  /**
   * Merge Two sorted Linked Lists
   * @param l1 first sorted linked list
   * @param l2 second sorted linked list
   * @return Head of the sorted linked list
   */
  ListNode merge(ListNode l1, ListNode l2) {
    // Initialize a dummy node as Head and Tail
    ListNode head = new ListNode(0);
    ListNode tail = head;

    // Keep selecting smaller of two nodes and append to the Tail
    while(l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        tail.next = l1;
        tail = l1;
        l1 = l1.next;
      } else {
        tail.next = l2;
        tail = l2;
        l2 = l2.next;
      }
    }

    // Append remaining nodes of one of the lists
    if (l1 != null) {
      tail.next = l1;
    } else if (l2 != null) {
      tail.next = l2;
    }

    return head.next; // return next of the dummy node
  } // merge
    

Applications

• One of the application of this method will be to apply in Merge Sort of a Linked List where the list will be repeatedly split into half, sorted and finally merged to give the resulting sorted list.

---

---

---

Git: Delete Local Commits and Commit Pushed to Remote

1. Undo Local Commits

Following command can be used for undoing the local commits.

git reset HEAD~1

you can give number of your desire depending upon the number of commits to undo.

2. Delete Commits From Remote

Following is the example of deleting a commit from remote.

1. Revert the Full Commit
git revert dd61ab23

2. Delete the last Commit
git push <remote> +dd61ab23^:<branch>

3. Delete the Commit from a list
git rebase -i dd61ab23^ -> This will open and editor showing a list of all commits. Delete the one you want to get rid off using appropriate "drop" command.
git rebase --continue -> Finish the rebase and push force to repo if necessary.
git push <remote_repo> <remote_branch> -f -> If necessary

---

---

---

JUnit Test - Setting Private Field Using PowerMockito's Whitebox

Introduction

There might be a case when you need to write a JUnit test for a class method which depends upon some private field that is in turn set during the deployment from some disk file or database or Network source or any other source.

Now when you write the JUnit test for that method, the field is not set. You cannot set it because it is a private field. You could have have a setter method, but obviously you are not going to create a setter method just for the sake of testing.

Solution Using PowerMockito - Whitebox

Such a case can be easily handled using PowerMockito. PowerMockito framework gives us the leverage to set the private fields with some mocked values.

Consider the following class StockCache:

	class StockCache {
	private Map<String, String[]> cachedStocks;
	//-------------------------------------------------------------------------------------
	/**
	* Populates the cached stocks list
	*/
	public void initializeCachedStocks() {
	// implementation to populate the cache list
	// could be from disk or network or any other
	} // initializeCachedStocks
	//-------------------------------------------------------------------------------------
	/**
	* Returns the stock details of a stock corresponding to the stock number
	*
	* @param stockNumber stock number of the stock of which we need the detail
	* @return Stock Detail if it exists in the cache, otherwise NULL
	*/
	public String[] getStockDetail(String stockNumber) {
	return this.cachedStocks.get(stockNumber);
	} // getStockDetail
	} // StockCache

view raw StockCacheTest.java hosted with ❤ by GitHub

Here we try to write JUnit test for the method getStockDetail(). This method depends upon the private field cachedStocks. This field is in turn set by the method initializeCachedStocks(). Now to test the method getStockDetail(), the private field needs to be set. We could have called the method initializeCachedStocks() to set the field. But the question is, do we want to call this method during a test? Well the answer depends upon the nature of this method. If it simply reads some static data and sets the field, then there is no problem executing it during the test. However, if it needs to access some network location or read database, then we don't want to execute it.

At such instance, we want to set some mocked value to this field. We could have created a setter method. However, as already mentioned above, it is not good idea to create a setter method just for testing.

We can set the private field using org.powermock.reflect.Whitebox.setInternalState method.

Whitebox.setInternalState(<StockCacheInstance>, <private_field_name>, cachedStock);

Complete Implementation

Following is the complete implementation for testing the method.

	/* File: StockCacheTest.java
	* Created: 8/17/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	//=======================================================================================
	import junit.framework.Assert;
	import org.junit.Test;
	import org.junit.runner.RunWith;
	import org.powermock.modules.junit4.PowerMockRunner;
	import org.powermock.reflect.Whitebox;
	import java.util.HashMap;
	import java.util.Map;
	/**
	* @author Sabbir Manandhar manandharsabbir@gmail.com
	* @version 1.0
	*/
	@RunWith(PowerMockRunner.class)
	public class StockCacheTest {
	@Test
	public void testGetStockDetail() {
	// START Mocked cachedStock
	Map<String, String[]> cachedStock = new HashMap<String, String[]>();
	String stockNumber = "LAS3453SFDSFD";
	String[] stockDetail = new String[]{stockNumber, "This is the most active stock last week", "2500.00"};
	cachedStock.put(stockNumber, stockDetail);
	stockNumber = "UTR3453SFDSFD";
	stockDetail = new String[]{stockNumber, "The most successful", "644500.00"};
	cachedStock.put(stockNumber, stockDetail);
	stockNumber = "UIYR343SFDSFD";
	stockDetail = new String[]{stockNumber, "Heavily beaten.", "-45400.00"};
	cachedStock.put(stockNumber, stockDetail);
	stockNumber = "BJKB923FDSFD";
	stockDetail = new String[]{stockNumber, "Useless", "00.00"};
	cachedStock.put(stockNumber, stockDetail);
	// END Mocked cachedStock
	StockCache stockCache = new StockCache();
	Whitebox.setInternalState(stockCache, "cachedStocks", cachedStock); // SETS THE INTERNAL PRIVATE FIELD
	stockDetail = stockCache.getStockDetail("LAS3453SFDSFD");
	Assert.assertNotNull(stockDetail);
	Assert.assertEquals("This is the most active stock last week", stockDetail[1]);
	Assert.assertEquals("2500.00", stockDetail[2]);
	stockDetail = stockCache.getStockDetail("UIYR343SFDSFD");
	Assert.assertNotNull(stockDetail);
	Assert.assertEquals("Heavily beaten.", stockDetail[1]);
	Assert.assertEquals("-45400.00", stockDetail[2]);
	} // testGetStockDetail
	} // StockCacheTest
	//=======================================================================================
	class StockCache {
	private Map<String, String[]> cachedStocks;
	//-------------------------------------------------------------------------------------
	/**
	* Populates the cached stocks list
	*/
	public void initializeCachedStocks() {
	// implementation to populate the cache list
	// could be from disk or network or any other
	} // initializeCachedStocks
	//-------------------------------------------------------------------------------------
	/**
	* Returns the stock details of a stock corresponding to the stock number
	*
	* @param stockNumber stock number of the stock of which we need the detail
	* @return Stock Detail if it exists in the cache, otherwise NULL
	*/
	public String[] getStockDetail(String stockNumber) {
	return this.cachedStocks.get(stockNumber);
	} // getStockDetail
	} // StockCache

view raw StockCacheTest.java hosted with ❤ by GitHub

---

---

---

PowerMockito: java.security.NoSuchAlgorithmException: class configured for SSLContext: sun.security.ssl.SSLContextImpl$TLSContext not a SSLContext

Problem

Following exception is encountered while running a JUnit test written using PowerMockito.

org.apache.http.ssl.SSLInitializationException: class configured for SSLContext: sun.security.ssl.SSLContextImpl$\$$TLSContext not a SSLContext
at org.apache.http.ssl.SSLContexts.createDefault(SSLContexts.java:55)
at org.apache.http.impl.client.HttpClientBuilder.build(HttpClientBuilder.java:964)
.................
.................

Caused by: java.security.NoSuchAlgorithmException: class configured for SSLContext: sun.security.ssl.SSLContextImpl$\$$TLSContext not a SSLContext
.................
.................

Solution

This can be fixed by adding following annotation to the test class.

@PowerMockIgnore({"javax.net.ssl.*"})

---

---

---

PowerMockito: java.lang.AssertionError: Illegal subclass: class com.sun.net.ssl.internal.ssl.Provider

Problem

Following exception is encountered while running a JUnit test written using PowerMockito.

java.lang.AssertionError: Illegal subclass: class com.sun.net.ssl.internal.ssl.Provider

at sun.security.ssl.SunJSSE.subclassCheck(SunJSSE.java:235)
at sun.security.ssl.SunJSSE.(SunJSSE.java:108)
at com.sun.net.ssl.internal.ssl.Provider.(Provider.java:41)
.................
.................

Solution

This can be fixed by adding following annotation to the test class.

@PowerMockIgnore({"com.sun.net.ssl.internal.ssl.Provider"})

---

---

---

Replacing With Spaces for Tabs in VI/VIM

$\mathtt{REFERENCE}$ @ Stackover

Requirement

Recently I have been doing my programming in VIM. My IDE is customized to use 2 Space Characters for a Tab. This was not the case in the VIM. I wanted the same behavior in VIM as well.

Solution

Luckily there is a very simple solution.

:set tabstop=2 shiftwidth=2 expandtab

should do the trick.

If you already have tabs, then follow it up with a nice global RE to replace them with double spaces.

If you want to persist the behavior for all the files you work with VIM, you can place the command in the file~/.vimrc (:scriptnames to see all files loaded by VIM). Otherwise you can enter the command every time you need it.

---

---

---

Pushing Your Local Copy of JAR into the Local Maven Repository

$\mathtt{REFERENCE}$ @ Reference

If you understand the layout of the Maven repository, you can copy the jar directly into where it is meant to go. Maven will find this file next time it is run.

If you are not confident about the layout of the Maven repository, then you can adapt the following command to load in your jar file, all on one line.

     mvn install:install-file
          -Dfile=<path-to-file>
          -DgroupId=<group-id>
          -DartifactId=<artifact-id>
          -Dversion=<version>
          -Dpackaging=<packaging>
          -DgeneratePom=true
 
  Where: <path-to-file>  the path to the file to load
            <group-id>      the group that the file should be registered under
            <artifact-id>   the artifact name for the file
            <version>       the version of the file
            <packaging>     the packaging of the file e.g. jar
  

Example

If you have a jar file example.jar, then following command

     mvn install:install-file
          -Dfile=path/to/example.jar
          -DgroupId=com.hogwart
          -DartifactId=sample
          -Dversion=1.0.0
          -Dpackaging=jar
          -DgeneratePom=true

  

will generate following directory structure in the local maven repository:

~/.m2/repository/com/hogwart/sample/1.0.0/sample-1.0.0.jar

---

---

---

7 Steps to solve a Dynamic Programming Problem

$\mathtt{REFERENCE}$ @ Medium

$\mathtt{REFERENCE}$ @ Refdash

I loved the way the article has explained on how to proceed with Dynamic Programming. I am listing some key points from the article (for my own reference).

7 Steps to solve a Dynamic Programming Problem

1. How to recognize a DP problem
2. Identify Problem variables
3. Clearly Express the reccurrence relation
4. Identify the base cases
5. Decide if you want to implement it iteratively or recursively
6. Add memoization
7. Determine time complexity

Step 1: How to recognize a Dynamic Programming problem

Recognizing a Dynamic Programming problem is often the most difficult step in solving it. Can the problem solution be expressed as a function of solutions to similar smaller problems?

First, let’s make it clear that DP is essentially just an optimization technique. DP is a method for solving problems by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution. This saves computation time at the expense of a (hopefully) modest expenditure in storage space.

Recognizing that a problem can be solved using DP is the first and often the most difficult step in solving it. What you want to ask yourself is whether your problem solution can be expressed as a function of solutions to similar smaller problems.

Step 2: Identify problem variables

After identifying some recursive structure between our subproblems, we need to express the problem in terms of the function parameters and see which of those parameters are changing.

A way to determine the number of changing parameters is to list examples of several subproblems and compare the parameters. Counting the number of changing parameters is valuable to determine the number of subproblems we have to solve, but it is also important in its own right in helping us strengthen the understanding of the reccurrence relation from step 1.

Step 3: Clearly express the recurrence relation

Once you figure out that the recurrence relation exists and you specify the problems in terms of parameters, this should come as a natural step. How do problems relate to each other? In other words, let’s assume that you have computed the subproblems. How would you compute the main problem?

Step 4: Identify Base Cases

A base case is a subproblem that doesn’t depend on any other subproblem. In order to find such subproblems, you typically want to try a few examples, see how your problem simplifies into smaller subproblems, and at what point it cannot be simplified further.

The reason a problem cannot be simplified further is that one of the parameters would become a value that is not possible given constraints of a problem.

Step 5: Decide if you want to implement it iteratively or recursively

Step 6: Add memoization

Step 7: Determine Time complexity

---

Implementation for Problem Discussed in the Reference Page

	/* File: RunWaySpikes.java
	* Created: 6/12/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	import java.util.HashMap;
	import java.util.Map;
	/**
	* @author Sabbir Manandhar [lastname][dot][firstname][at]gmail[dot]com
	* @version 1.0
	*/
	public class RunWaySpikes {
	public static void main(String[] args) {
	boolean[] runway = {true, false, true, true, true, false, true, true, false, true, true};
	int position = 4;
	int speed = 5;
	System.out.println(canLand(runway, position, speed, new HashMap()));
	System.out.println(canLand(runway, position, speed));
	} // main
	//----------------------------------------------------------------------------------------------------
	/**
	* Recursive solution using Memoization
	*
	* @param runway boolean array representing runway where true means safe spot
	* @param position starting position in the runway
	* @param speed starting speed
	* @param mem Map for Memoization
	* @return true if can land safely in the runway
	*/
	private static boolean canLand(boolean[] runway, int position, int speed, Map<String, Boolean> mem) {
	if (position < 0 || position >= runway.length) {
	return false;
	} else if (speed == 0){
	return runway[position];
	} else if (runway[position]){
	String key = position + "-" + speed;
	if (mem.containsKey(key)) {
	return mem.get(key);
	} else {
	boolean result = canLand(runway, position + speed - 1, speed - 1, mem) ||
	canLand(runway, position + speed + 1, speed + 1, mem) ||
	canLand(runway, position + speed, speed + 1, mem);
	mem.put(key, result);
	return result;
	}
	}
	return false;
	} // canLand
	//----------------------------------------------------------------------------------------------------
	/**
	* Iterative solution using DP
	* @param runway boolean array representing runway where true means safe spot
	* @param position starting position in the runway
	* @param speed starting speed
	* @return true if can land safely in the runway
	*/
	public static boolean canLand(boolean[] runway, int position, int speed) {
	if (speed >= runway.length) {
	return false;
	}
	if (position < 0 || position >= runway.length) {
	return false;
	}
	// rows = positions, columns = speeds
	boolean[][] dp = new boolean[runway.length][runway.length];
	for (int i = 0; i < runway.length; i++) { // we already know answer for speed = 0 (column = 0)
	dp[i][0] = runway[i];
	}
	for (int p = runway.length - 1; p >= 0; p--) { // start from last position
	if (!runway[p]) continue; // no need to check further if current spot is spike
	for (int s = 1; s < runway.length; s++) { // check for all speeds
	int[] deltas = {-1, 0, 1};
	for (int delta : deltas) {
	int newPosition = p + s + delta;
	int newSpeed = s + delta;
	if (newPosition >= 0 && newPosition < runway.length && newSpeed < runway.length) {
	dp[p][s] = dp[p][s] || dp[newPosition][newSpeed];
	}
	}
	}
	}
	return dp[position][speed];
	} // canLand
	//----------------------------------------------------------------------------------------------------
	} // RunWaySpikes

view raw RunWaySpikes.java hosted with ❤ by GitHub

---

---

---

Longest Substring without Repeating Characters

$\mathtt{REFERENCE}$ @ This is a LeetCode Problem.

Problem Description

Given a string. We need to find the sub string of unique characters with longest length.

Examples

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution 1: Brute Force Solution

An obvious solution would be to consider all the substrings and return the maximum length. The implementation is also obvious. From each position of the string, we compute the substring with unique characters. Finally we return the length of maximum size substring.

Complexity

We are computing substring and each of the location. To compute a substring at a location, we might need to traverse the whole string. So the time complexity of this approach will be $O(n^2)$. The space complexity is $O(1)$.

Solution 2: Efficient Solution

This problem can be solved efficiently using two pointers.

1. Set two pointers start = 0 and cursor = 0.
2. Keep increasing cursor until we encounter unique characters.
3. When a duplicate character is encountered
   1. Compute length of the substring of unique characters based upon start and cursor value and update max length.
   2. Move the pointer start towards right until the repeated character is encountered.
4. Repeat steps 2 and 3 until the end.

Implementation

	/* File: LongestSubStringUniqueCharacters.java
	* Created: 6/8/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 WorldLingo Inc.
	*/
	/**
	* @author Sabbir Manandhar [lastname][dot][firstname][dot]gmail[dot]com
	* @version 1.0
	*/
	public class LongestSubStringUniqueCharacters {
	/**
	* Driver method
	* @param args
	*/
	public static void main(String[] args) {
	System.out.println(computeEfficient("azz"));
	System.out.println(computeEfficient("pwwkew"));
	System.out.println(computeEfficient("pwwkewa"));
	System.out.println(computeEfficient("abcabcbb"));
	System.out.println(computeEfficient("bbbbbbbbbbbb"));
	System.out.println(computeEfficient("udzyeavofanfxngqyhubmaftqyzq"));
	System.out.println(computeEfficient("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCD"));
	} // main
	//-------------------------------------------------------------------------------------------------------------
	/**
	* Computes the maximum length of the substring with unique characters
	* It computes in O(2n) ~ O(n) time
	* and O(1) space
	*
	* @param input
	* @return
	*/
	public static int computeEfficient(String input) {
	int maxLength = 0;
	int begin = 0, end = 0; // these variables store start and end endex of the longest substring, Used if you actually need to return longest substring
	boolean[] exists = new boolean[256]; // to identify repeated character
	int start = 0, cursor = 0;
	for (; cursor < input.length(); cursor++) {
	char curr = input.charAt(cursor);
	if (exists[curr]) { // repeated character encountered
	if (maxLength < (cursor - start)) { // compute length of substring and update max length if necessary
	maxLength = cursor - start;
	begin = start;
	end = cursor;
	}
	while (input.charAt(start) != curr) { // move pointer 'start' to first occurrence of current character
	exists[input.charAt(start)] = false;
	start++;
	}
	start++; // move pointer 'start' to next position, to start new unique characters
	} else {
	exists[curr] = true; // mark current character as visited
	}
	}
	// check the length of substring once the traversal of string is done
	if (maxLength < (cursor - start)) {
	begin = start;
	end = cursor;
	}
	//return input.substring(begin, end); // return actual longest substring
	return end - begin;
	} // computeEfficient
	} // LongestSubStringUniqueCharacters

view raw LongestSubStringUniqueCharacters.java hosted with ❤ by GitHub

Complexity

By this method, we access each of the characters in the string twice - once by the pointer cursor and other by the pointer start. Hence, the time complexity of this approach is $O(n)$. The space complexity remains O(1). To mark the visited characters we have used a fixed size array.

---

---

---

Find Two Missing Numbers in the given Array

$\mathtt{PRE-REQUISITE}$ @ One Missing Number in an Array

Task Description

Given an array of integers which contains numbers from [1,n] except two numbers. We need to find those two missing numbers.

Example

Sample Input 1:

input_array = [1, 2, 7, 9, 3, 6, 4]

Sample Output 1:

missing numbers = 5, 8

Sample Input 2:

input_array = [2, 7, 9, 3, 6, 4, 5, 8]

Sample Output 2:

missing numbers = 1, 10

Naive Solution, Hashing Solution and Sorting Solution

If the size of input array is $n$, then we are looking for the numbers $[1,\ N]]$ inclusive where $N = n + 2$.

Similar to the Single Missing Number Problem, the Naive solution, Hashing solution and Sorting solution can be implemented in the similar fashion with similar Time and Space Complexity. The changes to be made are minor. Can you try it?

Solution 2: Using Sum of Numbers and XOR Together

Sum of numbers method and XOR of numbers method can not be applied alone to compute the two missing numbers. However, we can combine those two methods to get our result.

Principle - Part 1 (Compute Pivot)

If $x$ and $y$ be the two missing numbers, then it can be guaranteed that the two numbers will lie on the either side of a $Pivot$ number because we are talking about Unique Numbers from $1$ to $N$, and $x$ and $y$ are also Unique.

We can safely choose the $Pivot$ number to be $Pivot = (x+y)/2$.

$x+y$ can be computed by the Sum of Numbers technique we applied in Single Missing Number Problem to compute single missing number. The same method here will give us the sum of two missing numbers. After we have the sum, we can compute $Pivot = sum / 2$

Principle - Part 2 (Compute Missing Numbers)

After we have chosen the $Pivot$ number we can compute the missing number on the either sides by using XOR technique.

The missing number in the lower half can be computed by computing XOR of

1. all numbers from $1$ to $Pivot$, and
2. all numbers $\le Pivot$ in the input array

The final result will be the missing number in Lower Half.

Similarly, the missing number in the uppoer half can be computed by computing XOR of

1. all numbers from $Pivot + 1$ to $N$, and
2. all numbers $\gt Pivot$ in the input array

The final result will be the missing number in Upper Half.

Implementation

Following the implementation of above principle:

	/* File: MissingTwoNumbers.java
	* Created: 6/6/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 WorldLingo Inc.
	*/
	/**
	* @author Sabbir Manandhar (lastname)(dot)(firstname)(at)gmail(dot)com
	* @version 1.0
	*/
	public class MissingTwoNumbers {
	public static void main(String[] args) {
	int[] input = new int[]{10, 9, 5, 6, 8, 3, 7, 4, 11, 1, 2, 13, 15};
	int[] res = find(input);
	System.out.println(res[0] + " " + res[1]);
	} // main
	//-------------------------------------------------------------------------------
	/**
	* Finds the two missing numbers in the array
	* @param input input array containing numbers [1,n] except two numbers
	* @return array of two missing numbers
	*/
	public static int[] find(int[] input) {
	long sum = findSumOfMissingNumbers(input); // find sum of missing numbers
	int pivot = (int) sum / 2;
	// Compute the missing number in lower half
	int lowerHalfXOR = 0;
	for (int i = 1; i <= pivot; i++) {
	lowerHalfXOR ^= i;
	}
	for (int i = 0; i < input.length; i++) {
	if (input[i] <= pivot) {
	lowerHalfXOR ^= input[i];
	}
	}
	// Compute the missing number in upper half
	int upperHalfXOR = 0;
	for (int i = pivot + 1; i <= input.length + 2; i++) {
	upperHalfXOR ^= i;
	}
	for (int i = 0; i < input.length; i++) {
	if (input[i] > pivot) {
	upperHalfXOR ^= input[i];
	}
	}
	return new int[]{lowerHalfXOR, upperHalfXOR};
	} // find
	//-------------------------------------------------------------------------------
	/**
	* Finds the sum of the two missing numbers in the input array
	* @param input array containing numbers [1,n] except two numbers
	* @return sum of the two missing numbers
	*/
	public static long findSumOfMissingNumbers(int[] input) {
	int n = input.length + 2;
	int expectedSum = (n * (n+1)) / 2;
	int actualSum = 0;
	for (int num : input) {
	actualSum += num;
	}
	return expectedSum - actualSum;
	} // findSumOfMissingNumbers
	//-------------------------------------------------------------------------------
	} // MissingTwoNumbers

view raw MissingTwoNumbers.java hosted with ❤ by GitHub

---

---

---

Find a missing number in given array containing numbers 1 to n

Task Description

Given an array of integers which contains numbers from [1,n] inclusive except One number. We need to find that missing numbers.

Example

Sample Input 1:

input_array = [1, 2, 7, 9, 3, 6, 4, 8]

Sample Output 1:

missing number = 5

Sample Input 2:

input_array = [1, 2, 7, 9, 3, 6, 4, 5, 8]

Sample Output 2:

missing number = 10

Solution 1: Naive Solution

If the size of the input array is $n$, then we are looking for the numbers in the range $[1,\ N]$ inclusive where $N\ =\ n\ +\ 1$.

The naive solution will be to run a loop from $1$ to $N$ and for each number, we look into the given array to check if it exist or not. Whenever we encounter a number that does not exist in the input array, we have our solution.

Implementation

	//-----------------------------------------------------------------------------------------------------
	/**
	* Computes the missing number using naive way
	* O(n^2) time and O(1) space
	*
	* @param input input array
	* @return missing number
	*/
	public static int naiveSolution(int[] input) {
	int N = input.length + 1;
	for (int i = 1; i <= N; i++) {
	int j = 0;
	for (; j < input.length; j++) {
	if (i == input[j]) break;
	}
	if (j == input.length) {
	return i;
	}
	}
	return -1;
	} // naiveSolution
	//-----------------------------------------------------------------------------------------------------

view raw MissingNumber.java hosted with ❤ by GitHub

Complexity

In this solution, for each number from $1$ to $N$, we check if it exists in the given input array which takes $O(n)$ time and we are repeating this for $N$ number of times. $\therefore$ The time complexity of this solution is $O(n^2)$.

This solution doesn't require any extra data structure. So the space complexity is $O(1)$.

Solution 2: Hashing the numbers

In the above solution, we see that checking if a number exist in the input array takes $O(n)$ time. If we are able to improve this lookup time, then we could have better time complexity.

To improve the lookup time, we can store the input numbers into a HashMap. In this case, we know that we are going to check for the numbers $1$ to $N$. So we could also use a Boolean Array of size N to store whether a number exist in the array or not.

Implementation

	//-----------------------------------------------------------------------------------------------------
	/**
	* Computes the missing number by using hashing technique
	* O(n) time an O(n) space
	*
	* @param input input array
	* @return missing number
	*/
	public static int hashingSolution(int[] input) {
	int N = input.length + 1;
	boolean[] exists = new boolean[N];
	for (int i = 0; i < input.length; i++) {
	exists[input[i] - 1] = true;
	}
	for (int i = 1; i <= N; i++) {
	if (!exists[i-1]) return i;
	}
	return -1;
	} // hashingSolution
	//-----------------------------------------------------------------------------------------------------

view raw MissingNumber.java hosted with ❤ by GitHub

Complexity

After hashing we can verify if the number exists in the input array in constant O(1) time and we do this for all numbers in the array. $\therefore$ The time complexity of this solution is $O(n)$.

However, we have introduced extra space for hashing whose size is equal to the number items in the input array. So the space complexity is also $O(n)$.

Solution 3: By Sorting Input Array

We can also solve this problem by sorting the input array. Once sorted, we can identify the missing number simply by traversing the sorted array.

Implementation

	//-----------------------------------------------------------------------------------------------------
	/**
	* Computes the missing number by first sorting the input
	* O(nlogn) time and O(1) space
	*
	* @param input input array
	* @return missing number
	*/
	public static int sortingSolution(int[] input) {
	int N = input.length + 1;
	Arrays.sort(input);
	for (int i = 1; i <= N; i++) {
	if (i == N || input[i-1] != i) return i;
	}
	return -1;
	} // sortingSolution
	//-----------------------------------------------------------------------------------------------------

view raw MissingNumber.java hosted with ❤ by GitHub

Complexity

Sorting takes $O(nlogn)$ time and traversing the sorted array takes $O(n)$ time. $\therefore$ The time complexity of this solution is $O(nlogn)$.

This solution doesn't require any extra data structure. So the space complexity is $O(1)$.

Solution 4: Using Sum of Numbers

We know that if the size of the input array is $n$, then we are looking for the numbers in the range $[1,\ n+1]$.

Sum of this range $S_N=\ \frac {N \times (1 + N)}{2}$

Now, if $S$ be the sum of all numbers in the input array and $x$ is a missing number in the array, then $S_N - S = x$. We can use this to easily identify the missing number.

Implementation

	//-----------------------------------------------------------------------------------------------------
	/**
	* Computes the missing number by computing the sum of numbers
	* O(n) time and O(1) space
	*
	* @param input input array
	* @return missing number
	*/
	public static int numbersSumSolution(int[] input) {
	int N = input.length + 1;
	int expectedSum = N * (1 + N) / 2; // sum of numbers from 1 to N
	int actualSum = 0; // sum of numbers in input array
	for (int num : input) {
	actualSum += num;
	}
	return expectedSum - actualSum;
	} // numbersSumSolution
	//-----------------------------------------------------------------------------------------------------

view raw MissingNumber.java hosted with ❤ by GitHub

Complexity

We need to traverse through the input array only once to sum all the numbers. $\therefore$ The time complexity is $O(n)$.

This solution doesn't require any extra data structure. So the space complexity is $O(1)$.

Solution 4: Using XOR of Numbers

We know that if the size of the input array is $n$, then we are looking for the numbers in the range $[1,\ n+1]$.

Also,

1. if we XOR a number to itself, then the result is $0$. i.e. $x\ ^\ x = 0$.
2. if we XOR a number to $0$, the the result is the number itself.

So, if we compute XOR of all the numbers from $1$ to $N$ and also all the numbers in the input array, we are XORing all the numbers twice except the missing number. Hence, the result is going to be the missing number.

Implementation

	//-----------------------------------------------------------------------------------------------------
	/**
	* Computes the missing number by computing XOR of numbers
	* O(n) time and O(1) space
	*
	* @param input input array
	* @return missing number
	*/
	public static int xorSolution(int[] input) {
	int N = input.length + 1;
	int res = 0;
	// XOR of all numbers from 1 to N
	for (int i = 1; i <= N; i++) {
	res ^= i;
	}
	// XOR of all numbers in the input array
	for (int i = 0; i < input.length; i++) {
	res ^= input[i];
	}
	return res;
	} // xorSolution
	//-----------------------------------------------------------------------------------------------------

view raw MissingNumber.java hosted with ❤ by GitHub

Complexity

We need to traverse through the input array only once to XOR all the numbers. $\therefore$ The time complexity is $O(n)$.

This solution doesn't require any extra data structure. So the space complexity is $O(1)$.

---

---

---

Mocking Non-Static Private Method Using PowerMockito

$\mathtt{RELATED\ TOPICS}$ @ Mocking Static Private method Mockito does not support the mocking of Private Methods. However, we can use PowerMockito that extends Mockito. Private methods may be mocked by following ways:

• public static WithOrWithoutExpectedArguments when(Object instance, Method method) throws Exception
• public static org.mockito.stubbing.OngoingStubbing when(Object instance, Object... arguments) throws Exception

Test Class Setup

Test class should be anotated with @RunWith(PowerMockRunner.class) and @PrepareForTest({ClassWithPrivateMethod.class}).

When a class is annotated with @RunWith or extends a class annotated with @RunWith, JUnit will invoke the class it references to run the tests in that class instead of the runner built into JUnit [REF].

@PrepareForTest tells PowerMockito to prepare listed classes for testing. Classes needed to be defined using this annotation are typically those that needs to be byte-code manipulated. This includes final classes, classes with final, private, static or native methods that should be mocked and also classes that should be return a mock object upon instantiation.

Mocking Private Method

A Private Method can be mocked in following way:

  ClassWithPrivateMethod instance = new ClassWithPrivateMethod();
  ClassWithPrivateMethod spy = PowerMockito.spy(instance);  // IMPORTANT its NOT Mockito.spy()

  PowerMockito.doReturn().when(spy, "PRIVATE_METHOD_NAME", );
  

Example

Consider a following utility class.

  public class StockDetails {

    //------------------------------------------------------------------------

    /**
     * Returns details of Stock corresponding to stockNumber
     * @param stockNumber stock number whose detail is to be found
     * @return array of strings representing stock detail
     *           array[0] = stockNumber
     *           array[1] = Stock Description
     *           array[2] = price
     *         null if stock detail is not found
     */
    public String[] getStockDetails(String stockNumber) {
      try {
        String stockDetail = requestStockDetails(stockNumber);

        String[] components = stockDetail.split("---");
        if (components[0].equals("SUCCESS")) {
          return new String[]{stockNumber, components[1], components[2]};
        }
      } catch (Exception e) {}
      return null;
    } // getStockDetails

    //------------------------------------------------------------------------

    /**
     * Retrieves the stock details from the stock information
     * server
     *
     * @param stockNumber
     * @return stock detail in json format
     */
    private String requestStockDetails(String stockNumber) {
      String stockDetail = "";

      //
      // logic for making HTTP request or any other request
      // made to the server to retrieve the stock detail
      //

      return stockDetail;
    } // requestStockDetails

    //------------------------------------------------------------------------

  } // StockDetails

  

Here I am going to write JUnit method to verify the method getStockDetails() which depends upon the private method requestStockDetails().

This private method makes an HTTP request to retrieve some results. We don't want the real HTTP request made for the unit test. So, we will need to mock this private method. Following is the implementation of the JUnit test which mocks the private method.

    import junit.framework.Assert;
    import org.junit.Test;
    import org.junit.runner.RunWith;
    import org.powermock.api.mockito.PowerMockito;
    import org.powermock.core.classloader.annotations.PrepareForTest;
    import org.powermock.modules.junit4.PowerMockRunner;

    /**
     * @author Sabbir Manandhar
     * @version 1.0
     */
    @RunWith(PowerMockRunner.class)
    @PrepareForTest({StockDetails.class})
    public class StockDetailsTest {

      @Test
      public void testGetStockDetails() throws Exception {
        String stockNumber = "LKSJf289447OIOIJ";
    
        StockDetails stockDetails = new StockDetails();
        StockDetails spy = PowerMockito.spy(stockDetails); // Make SURE you use PowerMockito.spy()

        PowerMockito.doReturn("SUCCESS---This is the most active stock last week---2500.00")
                .when(spy, "requestStockDetails", stockNumber);

        String[] details = spy.getStockDetails(stockNumber); // This will execute actual method getStockDetails() in stockDetails instance,
                                                             // but requestStockDetails() inside this method will be mocked result
        Assert.assertEquals(stockNumber, details[0]);
        Assert.assertEquals("This is the most active stock last week", details[1]);
        Assert.assertEquals("2500.00", details[2]);
      }
    } // StockDetailsTest

  

Warning - Using Mockito.spy() instead of PowerMockito.spy()

Its important that you use PowerMockito.spy() while creating spy object for the actual stockDetails instance in the test method.

If you use Mockito.spy() method, then you are going to get an Exception.

   java.lang.NullPointerException
      at org.powermock.api.mockito.internal.expectation.PowerMockitoStubberImpl.addAnswersForStubbing(PowerMockitoStubberImpl.java:67)
       at org.powermock.api.mockito.internal.expectation.PowerMockitoStubberImpl.prepareForStubbing(PowerMockitoStubberImpl.java:124)
       at org.powermock.api.mockito.internal.expectation.PowerMockitoStubberImpl.when(PowerMockitoStubberImpl.java:92)
       at com.hogwart.StockDetailsTest.testGetStockDetails(StockDetailsTest.java:34)
       at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
       at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
       at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
       at java.lang.reflect.Method.invoke(Method.java:498)
       at org.junit.internal.runners.TestMethod.invoke(TestMethod.java:66)
       at org.powermock.modules.junit4.internal.impl.PowerMockJUnit44RunnerDelegateImpl$PowerMockJUnit44MethodRunner.runTestMethod(PowerMockJUnit44RunnerDelegateImpl.java:310)
       at org.junit.internal.runners.MethodRoadie$2.run(MethodRoadie.java:86)
       at org.junit.internal.runners.MethodRoadie.runBeforesThenTestThenAfters(MethodRoadie.java:94)
       at org.powermock.modules.junit4.internal.impl.PowerMockJUnit44RunnerDelegateImpl$PowerMockJUnit44MethodRunner.executeTest(PowerMockJUnit44RunnerDelegateImpl.java:294)
       at org.powermock.modules.junit4.internal.impl.PowerMockJUnit47RunnerDelegateImpl$PowerMockJUnit47MethodRunner.executeTestInSuper(PowerMockJUnit47RunnerDelegateImpl.java:127)
       at org.powermock.modules.junit4.internal.impl.PowerMockJUnit47RunnerDelegateImpl$PowerMockJUnit47MethodRunner.executeTest(PowerMockJUnit47RunnerDelegateImpl.java:82)
       at org.powermock.modules.junit4.internal.impl.PowerMockJUnit44RunnerDelegateImpl$PowerMockJUnit44MethodRunner.runBeforesThenTestThenAfters(PowerMockJUnit44RunnerDelegateImpl.java:282)
       at org.junit.internal.runners.MethodRoadie.runTest(MethodRoadie.java:84)
       at org.junit.internal.runners.MethodRoadie.run(MethodRoadie.java:49)
       at org.powermock.modules.junit4.internal.impl.PowerMockJUnit44RunnerDelegateImpl.invokeTestMethod(PowerMockJUnit44RunnerDelegateImpl.java:207)
       at org.powermock.modules.junit4.internal.impl.PowerMockJUnit44RunnerDelegateImpl.runMethods(PowerMockJUnit44RunnerDelegateImpl.java:146)
       at org.powermock.modules.junit4.internal.impl.PowerMockJUnit44RunnerDelegateImpl$1.run(PowerMockJUnit44RunnerDelegateImpl.java:120)
       at org.junit.internal.runners.ClassRoadie.runUnprotected(ClassRoadie.java:34)
       at org.junit.internal.runners.ClassRoadie.runProtected(ClassRoadie.java:44)
       at org.powermock.modules.junit4.internal.impl.PowerMockJUnit44RunnerDelegateImpl.run(PowerMockJUnit44RunnerDelegateImpl.java:122)
       at org.powermock.modules.junit4.common.internal.impl.JUnit4TestSuiteChunkerImpl.run(JUnit4TestSuiteChunkerImpl.java:106)
       at org.powermock.modules.junit4.common.internal.impl.AbstractCommonPowerMockRunner.run(AbstractCommonPowerMockRunner.java:53)
       at org.powermock.modules.junit4.PowerMockRunner.run(PowerMockRunner.java:59)
       at org.junit.runner.JUnitCore.run(JUnitCore.java:157)
       at com.intellij.junit4.JUnit4IdeaTestRunner.startRunnerWithArgs(JUnit4IdeaTestRunner.java:68)
       at com.intellij.rt.execution.junit.IdeaTestRunner$Repeater.startRunnerWithArgs(IdeaTestRunner.java:47)
       at com.intellij.rt.execution.junit.JUnitStarter.prepareStreamsAndStart(JUnitStarter.java:242)
       at com.intellij.rt.execution.junit.JUnitStarter.main(JUnitStarter.java:70)

---

---

---

Maximum Size Square Sub Matrix with All 1's

$\mathtt{REFERENCE :}$HERE.

Problem Definition

Given a 2D $m \times n$ binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example

  Input 

  1 0 0 1 1 0 0
  1 1 1 0 0 0 0
  1 1 1 1 1 1 0
  0 0 1 1 1 1 1
  1 1 1 1 1 1 1
  1 1 1 1 1 1 1

  Output
  16

Solution 1: Naive Solution

The naive solution will be to find maximum size square from each of the cell considering them as the TOP-LEFT corner of the square and finally return the maximum size.

• Iterate through each of the cell in the given matrix
  • Consider each cell as the TOP-LEFT corner of a square. Then we go on to explore the maximum size square that it can form. The question is how do we explore?
    • If the current cell has value 0, then we don't need to explore at all. Size of square it can form is 0.
    • Else if the value is 1, then we go to the diagonally LEFT-DOWN cell. If this cell has value 1, then we check if all the cells in the column (in the left of it) and row (above it) are 1 or not (Boundary being the row and column value of current cell being considered). If all cells are not 1s, we have found the maximum square and return. But if all cells have value 1, we go on to next diagonal LEFT-DOWN cell and repeat the process.
• Finally return the maximum size found.

Implementation

	//---------------------------------------------------------------------------------
	/**
	* Computes the maximum size sub matrix in the given matrix
	* This method is a naive method O((mn)^2)
	*
	* @param matrix intput m x n matrix filled with 1s and 0s
	* @return area of the maximum square sub matrix
	*/
	public static int computeNaive(int[][] matrix) {
	int ROWS = matrix.length;
	int COLS = 0;
	if (ROWS > 0) {
	COLS = matrix[0].length;
	}
	int maxSize = 0;
	for(int row = 0; row < ROWS; row++) {
	for (int col = 0; col < COLS; col++) {
	if (matrix[row][col] == 1) {
	int diagR = row+1;
	int diagC = col+1;
	int size = 1;
	while(diagR < ROWS && diagC < COLS && matrix[diagR][diagC] == 1) {
	int r = diagR - 1;
	boolean maxFound = false;
	// check if all elements in column are 1 or not
	while (r >= row) {
	if (matrix[r][diagC] == 0) {
	maxFound = true; // 0 found
	break;
	}
	r--;
	}
	if (maxFound) {
	break;
	}
	int c = diagC - 1;
	// check if all elements in row are 1 or not
	while(c >= col) {
	if (matrix[diagR][c] == 0) {
	maxFound = true; // 0 found
	break;
	}
	c--;
	}
	if (!maxFound) {
	size++;
	} else {
	break;
	}
	diagR++;
	diagC++;
	}
	maxSize = Math.max(size, maxSize);
	}
	}
	}
	return maxSize * maxSize;
	} // computeNaive
	//---------------------------------------------------------------------------------

view raw MaximumSquareSubMatrix.java hosted with ❤ by GitHub

Complexity

We repeat the exploration process for each cell. There are $mn$ number of cells in the given matrix and the exploration of each cell can take $O(mn)$ time.$\therefore$ Total time complexity of this method $O((mn)^2)$.

As for space, it does not use any extra data structure. So its space complexity is $O(1)$

Solution 2: Dynamic Programming Solution

If the currently considered cell has a value 1, the minimum size of the square it can form is 1. To find the maximum size, we need to look into its neighbor cells at RIGHT, DOWN and RIGHT-DOWN (Assuming currently considered cell is the TOP-LEFT corner of the square)

If all the three neighbors are square of size 1, then the current cell will form square of size 2.

If any one of the three neighbors is square of size 0, then the currently considered cell can form square of size 1 only.

What will be the maximum size square if the neighbors are the square of size greater than 1.

In the example above:

1. Right Neighbor forms square of size 3
2. Right-Down Neighbor forms square of size 4
3. Down Neighbor forms square of size 2

From the figure, it is obvious that the square formed by current cell is 3.

Can we compute this value from the neighbor values? YES!! The value can be computed from neighbors as follows:

size of square that current cell can form = 1 + Minimum(size of neighbors)

Base Case

Since the bottom Row and right most column don't have cells to form square, number in them, either 0 or 1 is the maximum size of the square they can form.

Implementation

Since we will be using each of the cell as the TOP-LEFT corner of the square they can form, we can start the computation from the RIGHT BOTTOM because their value will not depend upon the values above them or left to them. We can then move towards left or up.

For this implementation we will need to maintain Auxiliary Matrix of the same size as the input matrix to hold the sizes of the square that each cell can form.

	//---------------------------------------------------------------------------------
	/**
	* Computes the maximum size sub matrix in the given matrix
	* This method uses Dynamic Programming O(mn) time and O(mn) space
	*
	* @param matrix intput m x n matrix filled with 1s and 0s
	* @return area of the maximum square sub matrix
	*/
	public static int computeDP(int[][] matrix) {
	int ROWS = matrix.length;
	int COLS = ROWS > 0 ? matrix[0].length : 0;;
	int maxSize = 0;
	int[][] size = new int[ROWS][COLS];
	// sets the bottom most row as the input itself
	for(int c = 0; c < COLS; c++) {
	if (maxSize == 0) {
	maxSize = matrix[ROWS-1][c];
	}
	size[ROWS-1][c] = matrix[ROWS-1][c];
	}
	// sets the right most column as the input itself
	for(int r = 0; r < ROWS-1; r++) {
	if (maxSize == 0) {
	maxSize = matrix[r][COLS-1];
	}
	size[r][COLS-1] = matrix[r][COLS-1];
	}
	// computes all other upper values using dynamic programming
	for(int r = ROWS - 2; r >= 0; r--) {
	for (int c = COLS - 2; c >= 0; c--) {
	if (matrix[r][c] == 1) {
	int right = size[r][c+1];
	int bottom = size[r+1][c];
	int diagonal = size[r+1][c+1];
	size[r][c] = 1 + Math.min(bottom, Math.min(diagonal, right));
	maxSize = Math.max(maxSize, size[r][c]);
	} else {
	size[r][c] = 0;
	}
	}
	}
	return maxSize * maxSize;
	} // compuateDP
	//---------------------------------------------------------------------------------

view raw MaximumSquareSubMatrix.java hosted with ❤ by GitHub

Complexity

With this method, we will be traversing through each of the cells only once. For the computation of current cell, we need to access at max three other cell values. So, the Time Complexity of this method is $O(mn)$.

As for space, we are using extra matrix of same size as an input. Thus the space complexity is also $O(mn)$.

Solution 3: Better Dynamic Programming Solution, O(n) Extra Space

In the previous implementation, we can see that we are using the Auxiliary Matrix to access only 3 of previous values to compute value for current cell. Hence, we don't need the whole matrix all the time. It is sufficient to store the result of one row at a time.For every row, when we traverse from right to left, the Auxiliary Array is also updated from right to left.

if size[] be the auxiliary array,

For any cell matrix[r][c],

size[c+1] represents Right Neighbor
size[c] represents Down Neighbor, and
prev (previous value of size[c]) represents Diagonal Neighbor

	//---------------------------------------------------------------------------------
	/**
	* Computes the maximum size sub matrix in the given matrix
	* This method uses Dynamic Programming O(mn) time and O(n) space
	*
	* @param matrix intput m x n matrix filled with 1s and 0s
	* @return area of the maximum square sub matrix
	*/
	public static int computeDP_2(int[][] matrix) {
	int ROWS = matrix.length;
	int COLS = ROWS > 0 ? matrix[0].length : 0;;
	int maxSize = 0;
	int[] size = new int[COLS];
	// sets the bottom most row as the input itself
	for(int c = 0; c < COLS; c++) {
	if (maxSize == 0) {
	maxSize = matrix[ROWS-1][c];
	}
	size[c] = matrix[ROWS-1][c];
	}
	//System.out.println(Arrays.toString(size));
	// computes all other upper values using dynamic programming
	for(int r = ROWS - 2; r >= 0; r--) {
	int prev = size[COLS-1];
	size[COLS-1] = matrix[r][COLS-1];
	for (int c = COLS - 2; c >= 0; c--) {
	if (matrix[r][c] == 1) {
	int right = size[c+1];
	int bottom = size[c];
	int diagonal = prev;
	prev = size[c];
	size[c] = 1 + Math.min(bottom, Math.min(right, diagonal));
	maxSize = Math.max(maxSize, size[c]);
	} else {
	size[c] = 0;
	}
	}
	//System.out.println(Arrays.toString(size));
	}
	return maxSize * maxSize;
	} // compuateDP

view raw MaximumSquareSubMatrix.java hosted with ❤ by GitHub

---

---

---

Super Powers of 2

$\mathtt{REFERENCE :}$ This is a HacerRank problem found HERE.

Task Description

You will be given two integers $a, b$ . You are required to output the result of $2^{2^a}$ mod $b$.

Naive Solution

The naive solution would be simple compute $2^a$, then $2^{2^a}$ and finally $2^{2^a}$ mod $b$. This will work for only very small values of $a$.

With the increase of the value $a$, we can't compute $2^a$ value, let alone be the final result.

Efficient Solution

Since the value $2^{2^a}$ is going to be huge for larger value of $a$, we need to find better approach to compute this.

We can actually simplify the value of $2^{2^a}$ by following way:

Also,
$(a\ *\ b)\ mod\ c\ =\ [(a\ mod\ c)\ *\ (b\ mod\ c)]\ mod\ c$

$\therefore$

Recursive Solution

Based upon above relationship, we can easily solve this problem using recursion.

  /**
  * Compute Super Power of 2 using recursion
  */
  public long compute(int a, int b) {
    if (a == 0) return 2 % b;
    return (compute(a - 1, b) * compute(a - 1,  b)) % b;
  }

Bottom Up Dynamic Programming Solution

With the recursive solution, we are going to end up computing for the same value again and again. This is will increase the time complexity. We can either apply memoization or dynamic programming to solve it efficiently.

Following is the Bottom Up Dynamic Programming Solution.

  /**
  * Compute Super Power of 2 using dynamic programming
  */
  public long compute(int a, int b) {
    long[] dp = new long[a+1];
    dp[0] = 2 % b;
    for(int i = 1; i <= a; i++) {
      dp[i] = (dp[i-1] * dp[i-1]) % b;
    }

    return dp[a];
  }

If we observe the solution above closely, we can observe that, to compute current value, we only need previous result. This implies that we don't need to store all previous results.

So above solution can be further simplified as:

  /**
  * Compute Super Power of 2 using dynamic programming
  */
  public long compute(int a, int b) {
    long prev = 2 % b;
    for(int i = 1; i <= a; i++) {
      prev = (prev * prev) % b;
    }

    return prev;
  }

---

---

---

Power of Powers - Minimum Number of Multiplications to compute Nth Power

Task Description

You need to find the minimum number of multiplications needed to get the desired power $n$ of a number $x$ using only previous computations.

Examples

The minimum number of multiplications required to compute $16th$ power of a number $x$ is $4$.

1. $x \times x = x^2$
2. $x^2 \times x^2 = x^4$
3. $x^4 \times x^4 = x^8$
4. $x^8 \times x^8 = x^{16}$

Similarly, the minimum number of multiplications required to compute the $15th$ power of the number is $5$.

1. $x \times x = x^2$
2. $x^2 \times x^2 = x^4$
3. $x^4 \times x = x^5$
4. $x^5 \times x^5 = x^{10}$
5. $x^5 \times x^{10} = x^{15}$

OR

1. $x \times x = x^2$
2. $x^2 \times x = x^3$
3. $x^3 \times x^3 = x^6$
4. $x^6 \times x^6 = x^{12}$
5. $x^{12} \times x^3 = x^{15}$

Solution

As can be seem from the examples, the $nth$ power of a number can be computed using previous results for power $\lt n$.

Also, as seen from the examples, there can be different combination of previous result to compute the $nth$ power. For example, we can compute $x^{15}$ using $x^5 \times x^{10}$ or using $x^{12} \times x^3$. Obviously we have multiple choices to compute this value.

Minimum Number of Multiplications

Let, $x^n = x^a \times x^b \times x^c \times x^d$ be one of the combination
Then, number of multiplication needed using this combination

$=$ number of multiplication for $x^a$ + number of multiplication for $x^b$ + number of multiplication for $x^c$ + number of multiplication for $x^d$ + 3

The last number $3$ comes from the fact that we need $3$ more multiplications to multiply $x^a,\ x^b,\ x^c\ and\ x^d$.

The required minimum number of multiplications will be the minimum of all such combinations.

Computing the Number of Multiplications for all Combinations

int min = Integer.MAX_VALUE;
for i = 2 to n/2
   // x^15, 15/2 = 7, there are 2 x^7 and we need to multiply x^7 (2-1) times
   int part1 = (i-1) + numberOfMultiplicationFor(n / i);

   // 15 % 2 = 1, 
   int part2 = numberOfMultiplicationFor(n % i)
   
   int combinationNumber =  part1 + part2;

   // if n % i != 0, we need extra 1 multiplication x^14 x x
   combinationNumber += n % i == 0 ? 0 : 1;
   
   min = Math.min(min, combinationNumber)

Special Case for Even n

For Even n, we can simply compute the number of multiplication required using,

// this will be minimum for Even n
numberOfMultiplication = numberOfMultiplicationFor(n/2) + 1;

Recursive Implementation

    if f(n) gives the minimum number of multiplication required to compute
       nth power, then

    f(n) = f(n/2) + 1 if n is even
         = Min{
                for i = 2 to n/2 
                  (i-1) + f(n/i) + f(n%i) + (1 if n%i != 0)
              }

    Base Cases:
      f(0) = f(1) = 0
      f(2) = 1
      f(3) = 2
  

Recursive implementation will give the result, but if we don't use memoization, then it will end up calculating the same value again and again. This will result into high complexity.

To improve the complexity, we can either use Memoization or Botton Up Dynamic programming. Following the Dynamic Programming solution.

Bottom Up Dynamic Programming Approach

	/* File: PowerOfPowers.java
	* Created: 2018-05-26
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	import java.io.*;
	import java.util.*;
	/**
	* Computes minimum number of multiplication required to compute the nth power of a number
	*
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class PowerOfPowers {
	/**
	* Driver method
	*/
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	System.out.println("Enter the value of n:" + compute(sc.nextInt()));
	} // main
	//---------------------------------------------------------------------------
	/**
	* Computes the minimum number of mulitplication
	* using bottom dynamic programming
	* @param
	*/
	public static int compute(int n) {
	int[] dp = new int[n + 1];
	for (int i = 0; i <= n; i++) {
	dp[i] = helper(i, dp);
	}
	return dp[x];
	} // compute
	//---------------------------------------------------------------------------
	/**
	* helper method that computes miniumum number of multplications
	* required to compute nth power of a number. It uses previous
	* results to compute the value
	*
	* @param n nth power to compute
	* @param dp previous results
	*/
	public static int helper(int n, int[] dp) {
	int[] baseCases = new int[]{0, 0, 1, 2, 2};
	if (n <= 3) return baseCases[n];
	int min = Integer.MAX_VALUE;
	if (n % 2 == 0) return dp[n / 2] + 1; // even n
	for (int i = 2; i <= n / 2; i++) {
	int part1 = (i - 1) + dp[n / i];
	int part2 = dp[n % i];
	int result = part1 + part2 + (n % i == 0 ? 0 : 1);
	min = Math.min(result, min);
	}
	return min;
	} // helper
	} // PowerOfPowers

view raw PowerOfPowers.java hosted with ❤ by GitHub

---

---

---

Shortest Distance in X x Y x Z 3D Matrix - Efficient BFS Method

$\mathtt{REFERENCE}$ @ HackerRank

$\mathtt{RELATED\ PROBLEM}$ The problem is related to path searching in 2D matrix. Only Difference is here we are dealing with 3D matrix. Searching in 2D matrix problem can be found HERE

Task Description

Herman the worm is in his terrarium and needs help getting to a grape to eat. His terrarium is $x \times y \times z$ large and is blocked by obstacles throughout the environment.

Please write an algorithm that outputs an optimal path Herman must take to get to the grape.

$H = Herman's\ starting\ point$
$O = Open$
$X = Obstacle\ (closed)\ Herman\ can't\ travel\ this\ way.$
$G = Grape$

Input Format

The first line of input will be $x,\ y,\ z$ in the format: $x\ y\ z$
Where, $x$ is the length of the X-Axis, $y$ is the length of the Y-Axis and $z$ is the length of the Z-Axis.

This will be followed by a layout of $x, y$ map for each of $z$ layer separated by a $blank\ line$.

Constraints

$0 <= X, Y, Z <= 40$

Output Format

Output will be sequence of Motion required to reach the destionation cell G from the source Cell H in separate lines.

Sample Inputs and Outputs

Sample Input 0

2 3 2

HX
OX
OX

XG
XO
OO

Sample Output 0

Y+
Y+
Z+
X+
Y-
Y-

Sample Input 1

3 3 2

HXG
OXX
OXX

XXO
XXO
OOO

Sample Output 1

Y+
Y+
Z+
X+
X+
Y-
Y-
Z-

Sample Input 2

4 4 4

GOOO
OOXO
OOOO
OOOO

OXXX
XXHX
XXXX
XXXX

OXXX
XXOX
XXXX
XXXX

OXXO
OOOO
OOOO
OOOO

Sample Output 2

Z+
Z+
X-
X-
Y-
Z-
Z-
Z-

The target is to find the shortest path distance from the source to the destination location. You can move to only $left,\ right,\ up\ or\ down cells$.

Solution: BFS Method - Efficient Method

Similar to the path searching Problem in 2D Matrix, this problem can also be solved efficiently using Breadth First Search (BFS) method. Using BFS method, we will be exploring any cell only once. $\therefore$ The Time Complexity of this method will be $\cal{O(xyz)}$.

Implementation

	/* File: HermanWorm.java
	* Created: 5/24/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.Scanner;
	/**
	* Finds the shortest distance from source to destination in
	* 3D array
	*
	* @author Sabbir Manandhar
	* manandhar.sabbir@gmail.com
	* @version 1.0
	*/
	public class HermanWorm {
	private static int X, Y, Z;
	/**
	* Driver Method
	* Reads Input from console as explained in the post
	*
	* @param args
	* @throws Exception
	*/
	public static void main(String[] args) throws Exception {
	Scanner sc = new Scanner(System.in);
	X = sc.nextInt();
	Y = sc.nextInt();
	Z = sc.nextInt();
	//System.out.println(X + " " + Y + " " + Z);
	sc.nextLine();
	sc.nextLine();
	Cell[][][] maze = new Cell[X][Y][Z];
	int sx = -1, sy = -1, sz = -1;
	for (int z = 0; z < Z; z++) {
	for (int y = 0; y < Y; y++) {
	String line = sc.nextLine();
	//System.out.println(line);
	if (line.length() != X) throw new Exception("Error reading input");
	for (int x = 0; x < X; x++) {
	char c = line.charAt(x);
	if(c == 'H') {
	sx = x;
	sy = y;
	sz = z;
	}
	maze[x][y][z] = new Cell(c, new int[]{x, y, z});
	}
	}
	if (sc.hasNextLine()) sc.nextLine();
	}
	//System.out.println(sx + " " + sy + " " + sz);
	solve(maze, sx, sy, sz);
	} // main
	//-----------------------------------------------------------------------------------------------
	/**
	* Searches for the Destination cell in a BFS fashion
	*
	* @param matrix 3D matrix where we need to find the destination cell from source
	* @param x source x location
	* @param y source y location
	* @param z source z location
	* @throws Exception
	*/
	public static void solve(Cell[][][] matrix, int x, int y, int z) throws Exception {
	// delta values to find neighboring cells of current cell
	int[][] delta = new int[][]{{-1, 0, 0}, // negative X
	{1, 0, 0}, // positive X
	{0, -1, 0}, // negative Y
	{0, 1, 0}, // positive Y
	{0, 0, -1}, // negative Z
	{0, 0, 1}}; // positive Z
	Queue<Cell> queue = new LinkedList<Cell>();
	Cell source = matrix[x][y][z];
	queue.offer(source);
	while (!queue.isEmpty()) {
	Cell parent = queue.poll();
	for (int i = 0; i < delta.length; i++) {
	// location of neighbor cell
	int nx = parent.getLocation()[0] + delta[i][0];
	int ny = parent.getLocation()[1] + delta[i][1];
	int nz = parent.getLocation()[2] + delta[i][2];
	if (isValidLocation(nx, ny, nz)) {
	Cell neighbor = matrix[nx][ny][nz];
	if (!neighbor.isVisited() && !neighbor.isObstacle()) {
	neighbor.setParent(parent);
	neighbor.setVisited();
	//System.out.println(neighbor);
	neighbor.setMotion(getMotion(parent, neighbor));
	if (neighbor.isDestination()) {
	printResult(neighbor);
	return;
	} else {
	queue.offer(neighbor);
	}
	}
	}
	}
	}
	} // solve
	//---------------------------------------------------------------------------------------------------
	/**
	* Motion required to move from Source cell to Destination Cell
	* @param source Source Cell
	* @param destination Destination Cell
	* @return X+ if the motion needed is positive unit distance in X direction
	* X- if the motion needed is negative unit distance in X direction
	* Y+ if the motion needed is positive unit distance in Y direction
	* Y- if the motion needed is negative unit distance in Y direction
	* Z+ if the motion needed is positive unit distance in Z direction
	* Z- if the motion needed is negative unit distance in Z direction
	* @throws Exception
	*/
	private static String getMotion(Cell source, Cell destination) throws Exception {
	int dx = destination.getLocation()[0] - source.getLocation()[0];
	int dy = destination.getLocation()[1] - source.getLocation()[1];
	int dz = destination.getLocation()[2] - source.getLocation()[2];
	if (dx == 1 && dy == 0 && dz == 0) return "X+";
	if (dx == -1 && dy == 0 && dz == 0) return "X-";
	if (dy == 1 && dx == 0 && dz == 0) return "Y+";
	if (dy == -1 && dx == 0 && dz == 0) return "Y-";
	if (dz == 1 && dy == 0 && dx == 0) return "Z+";
	if (dz == -1 && dy == 0 && dx == 0) return "Z-";
	throw new Exception("getMotion: Something is wrong");
	} // getMotion
	//--------------------------------------------------------------------------------------------------
	/**
	* Print the result once the destination cell is found
	* This is Recursive implementation
	* @param dest Destination Cell
	*/
	private static void printResult(Cell dest) {
	if (dest.isSource()) {
	return;
	}
	printResult(dest.getParent());
	System.out.println(dest.getMotion());
	} // printResult
	//--------------------------------------------------------------------------------------------------
	/**
	* Determine is the location represented by inputs is a valid location in the
	* given input matrix
	* @param x x location
	* @param y y location
	* @param z z location
	* @return True if the location is within the matrix else False
	*/
	public static boolean isValidLocation(int x, int y, int z) {
	return !(x < 0 || x >= X || y < 0 || y >= Y || z < 0 || z >= Z);
	} // isValidLocation
	//---------------------------------------------------------------------------------------------------
	} // HermanWorm
	//====================================================================================================
	/**
	* Class representing a Cell in a Matrix
	*/
	class Cell {
	private int[] location;
	private char c;
	private boolean visited;
	private Cell parent;
	private String motion;
	/**
	* Constructor
	* @param c character in the cell
	* @param location [x,y,z] location triplet
	*/
	public Cell(char c, int[] location) {
	this.c = c;
	this.location = location;
	this.visited = false;
	this.parent = null;
	} // Cell
	//-------------------------------------------------------------------------------------------------
	/**
	* Sets the cell as visited
	*/
	public void setVisited() {
	visited = true;
	} // setVisited
	//-------------------------------------------------------------------------------------------------
	/**
	* Sets parent of the cell during the search to a destination via shortest path
	* Parent is the parent of this cell in the path
	* @param parent
	*/
	public void setParent(Cell parent) {
	this.parent = parent;
	} // setParent
	//-------------------------------------------------------------------------------------------------
	/**
	* Determine whether the cell is visited
	* @return true if the cell is visited, else false
	*/
	public boolean isVisited() {
	return this.visited;
	} // isVisited
	//-------------------------------------------------------------------------------------------------
	/**
	* Get parent of this cell in the path, if already set
	* @return the parent cell if it has been set, else it will be null
	*/
	public Cell getParent() {
	return this.parent;
	} // getParent
	//-------------------------------------------------------------------------------------------------
	/**
	* Determine if this cell is a destination cell
	* @return True if this cell is a destination cell, else false
	*/
	public boolean isDestination() {
	return this.c == 'G';
	} // isDestination
	//-------------------------------------------------------------------------------------------------
	/**
	* Determine if this cell is an obstacle
	* @return True if this cell is an obstacle, false otherwise
	*/
	public boolean isObstacle() {
	return this.c == 'X';
	} // isObstacle
	//-------------------------------------------------------------------------------------------------
	/**
	* Determine if this cell is a source
	* @return True if this cell is source, false otherwise
	*/
	public boolean isSource() {
	return this.c == 'H';
	} // isSource
	//-------------------------------------------------------------------------------------------------
	/**
	* Get the motion which is required to reach this cell from the parent cell in the shortest path
	* @return the motion X+/X-/Y+/Y-/Z+/Z-
	*/
	public String getMotion() {
	return this.motion;
	} // getMotion
	//-------------------------------------------------------------------------------------------------
	/**
	* Sest the motion to reach this cell from the parent cell
	* @param motion the motion X+/X-/Y+/Y-/Z+/Z-
	*/
	public void setMotion(String motion) {
	this.motion = motion;
	} // setMotion
	//-------------------------------------------------------------------------------------------------
	/**
	* get the x, y, z location triplet of this cell in the input matrix
	* @return
	*/
	public int[] getLocation() {
	return this.location;
	} // getLocation
	//-------------------------------------------------------------------------------------------------
	/**
	* String representation of this cell
	* Written for debug pupose
	* @return
	*/
	public String toString() {
	return this.c + " " + this.visited + " " + (this.parent != null ? this.parent.c : null);
	} // toString
	//-------------------------------------------------------------------------------------------------
	}

view raw HermanWorm.java hosted with ❤ by GitHub

---

---

---

Shortest Distance in m x n Matrix from Source to Destination

$\mathtt{RELATED\ PROBLEM}$ Path Searching in 3D Matrix

Task Description

Given a $m \times n$ matrix filled with 0's as permissible path. There is $only\ one\ source\ location$ indicated by a character '$*$'. There are $zero\ or\ more\ location$ where there is a food (or Destination) indicated by '$\#$' character.

The target is to find the shortest path distance from the source to the destination location. You can move to only $left,\ right,\ up\ or\ down cells$.

Solution 1: Brute Force / Recursive Solution

The brute force method is to try out all the paths possible and find the minimum path out of all those.

To find all the possible paths, we need to use recursive method. Since we are computing all the possible paths and there can be exponentially many paths, this method is going to be very very slow for larger input matrix.

Implementation

	/* File: MatrixShortestDistanceRecursive.java
	* Created: 2017-06-28
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2017 Hogwarts.
	*/
	/**
	* Given a MxN matrix. Filled with 0's
	* There is one source location indicated by character '*'
	* There are one or more location where there is a Food. Indicated by '#'
	* Find the Shortest distance to any one of the Food location.
	*
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class MatrixShortestDistanceRecursive {
	static boolean pathFound = false;
	/**
	* driver method
	* @param args
	*/
	public static void main(String[] args) {
	MatrixShortestDistanceRecursive sln = new MatrixShortestDistanceRecursive();
	char[][] input = new char[][]{
	{'*','X','#','X','#'},
	{'0','0','X','X','0'},
	{'0','0','0','X','0'},
	{'0','0','0','0','0'},
	{'0','0','0','0','0'}
	};
	System.out.println(sln.getFood(input));
	} // main
	// ---------------------------------------------------------------------------------------------------
	/**
	* Find shortest distance to food location
	* @param grid input matrix
	* @return shortest distance
	*/
	public static int getFood(char[][] grid) {
	boolean sourceFound = false;
	int sourceR = 0, sourceC = 0; // Source Location
	// find source location
	for(int r = 0; r < grid.length; r++) {
	for(int c = 0; c < grid[0].length; c++) {
	if (grid[r][c] == '*') {
	sourceR = r;
	sourceC = c;
	sourceFound = true;
	break;
	}
	}
	if (sourceFound) break;
	} // end for find source location
	boolean[][] processed = new boolean[grid.length][grid[0].length];
	processed[sourceR][sourceC] = true;
	int len = expolorePath(grid, processed, sourceR, sourceC, 0, Integer.MAX_VALUE);
	return pathFound ? len : -1;
	} // getFood
	// ---------------------------------------------------------------------------------------------------
	/**
	* Recursive method.
	* explore path to destination food location from given location
	* @param grid input matrix
	* @param processed matrix indicating specifica locations have been processed
	* @param r current row
	* @param c current column
	* @param pathSize current pathSize at location r,c
	* @param shortestSoFar shortest path discovered so far
	* @return shortest path found
	*/
	public static int expolorePath(char[][] grid, boolean[][] processed, int r, int c, int pathSize, int shortestSoFar) {
	if (grid[r][c] == '#') {
	pathFound = true;
	return pathSize;
	}
	int[] deltaR = {-1, 0, 1, 0};
	int[] deltaC = {0, 1, 0, -1};
	for(int i = 0; i <= 3; i++) {
	int neighborR = r + deltaR[i];
	int neighborC = c + deltaC[i];
	if (isPermitted(grid, neighborR, neighborC) && !processed[neighborR][neighborC]) {
	processed[neighborR][neighborC] = true;
	int len = expolorePath(grid, processed, neighborR, neighborC, pathSize+1, shortestSoFar);
	if ( len > -1) {
	shortestSoFar = Math.min(shortestSoFar, len);
	}
	processed[neighborR][neighborC] = false;
	}
	}
	return pathFound ? shortestSoFar : -1;
	} // expolorePath
	// ---------------------------------------------------------------------------------------------------
	/**
	* determine if a given location is permissible to move or not
	* @param grid input matrix
	* @param r given location's row
	* @param c given location's column
	* @return boolean whether the location is permitted or not
	*/
	public static boolean isPermitted(char[][] grid, int r, int c) {
	if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length) {
	return grid[r][c] != 'X';
	}
	return false;
	} // isPermitted
	// ---------------------------------------------------------------------------------------------------
	}

view raw MatrixShortestDistanceRecursive.java hosted with ❤ by GitHub

Time Complexity

There are exponentially many paths possible from source to destination. Since we are considering all those paths, the time complexity is also Exponential which becomes very slow with increase in input size.

Solution 2: BFS Method - Efficient Method

This problem can be solved efficiently using Breadth First Search (BFS) method. Using BFS method, we will be exploring any cell only once. $\therefore$ The Time Complexity of this method will be ${\cal O}(mn)$.

Implementation

	/* File: MatrixShortestDistanceBFS.java
	* Created: 2017-06-28
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2017 Hogwarts.
	*/
	import java.util.LinkedList;
	import java.util.Queue;
	/**
	* Given a MxN matrix. Filled with 0's
	* There is one source location indicated by character '*'
	* There are one or more location where there is a Food. Indicated by '#'
	* Find the Shortest distance to any one of the Food location.
	*
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class MatrixShortestDistanceBFS {
	/**
	* driver method
	* @param args
	*/
	public static void main(String[] args) {
	MatrixShortestDistanceRecursiveBFS sln = new MatrixShortestDistanceRecursiveBFS();
	char[][] input = new char[][]{
	{'0','X','#','X','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0'},
	{'0','0','X','X','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','*','X','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','X',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','X','#',},
	};
	/*char[][] input = new char[][]{
	{'*','X','#','X','#'},
	{'0','0','X','X','0'},
	{'0','0','0','X','0'},
	{'0','0','0','0','0'},
	{'0','0','0','0','0'}
	};*/
	System.out.println(sln.getFood(input));
	} // main
	// ---------------------------------------------------------------------------------------------------
	/**
	* Find shortest distance to food location
	* @param grid input matrix
	* @return shortest distance
	*/
	public static int getFood(char[][] grid) {
	boolean sourceFound = false;
	int sourceR = 0, sourceC = 0; // Source Location
	// find source location
	for(int r = 0; r < grid.length; r++) {
	for(int c = 0; c < grid[0].length; c++) {
	if (grid[r][c] == '*') {
	sourceR = r;
	sourceC = c;
	sourceFound = true;
	break;
	}
	}
	if (sourceFound) break;
	} // end for find source location
	boolean[][] processed = new boolean[grid.length][grid[0].length];
	processed[sourceR][sourceC] = true;
	int[][] pathLenths = new int[grid.length][grid[0].length];
	return explorePath(grid, processed, pathLenths, sourceR, sourceC);
	} // getFood
	// ---------------------------------------------------------------------------------------------------
	/**
	* BFS method.
	* explore path to destination food location from given location
	* @param grid input matrix
	* @param processed matrix indicating specifica locations have been processed
	* @param r current row
	* @param c current column
	* @return shortest path found
	*/
	public static int explorePath(char[][] grid, boolean[][] processed, int[][] pathLen, int r, int c) {
	Queue<int[]> ngbs = new LinkedList<int[]>();
	ngbs.add(new int[]{r, c});
	while(!ngbs.isEmpty()) {
	int[] ngb = ngbs.poll();
	int currentR = ngb[0];
	int currentC = ngb[1];
	int currLen = pathLen[currentR][currentC];
	if (grid[currentR][currentC] == '#') {
	return currLen;
	}
	int[] deltaR = {-1, 0, 1, 0};
	int[] deltaC = {0, 1, 0, -1};
	for(int i = 0; i <= 3; i++) {
	int neighborR = currentR + deltaR[i];
	int neighborC = currentC + deltaC[i];
	if (isPermitted(grid, neighborR, neighborC) && !processed[neighborR][neighborC]) {
	pathLen[neighborR][neighborC] = currLen + 1; // set length of neighbor
	ngbs.add(new int[]{neighborR, neighborC});
	processed[neighborR][neighborC] = true;
	}
	}
	}
	return -1;
	} // explorePath
	// ---------------------------------------------------------------------------------------------------
	/**
	* determine if a given location is permissible to move or not
	* @param grid input matrix
	* @param r given location's row
	* @param c given location's column
	* @return boolean whether the location is permitted or not
	*/
	public static boolean isPermitted(char[][] grid, int r, int c) {
	if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length) {
	return grid[r][c] != 'X';
	}
	return false;
	} // isPermitted
	// ---------------------------------------------------------------------------------------------------
	}

view raw MatrixShortestDistanceBFS.java hosted with ❤ by GitHub

---

---

---

HackerRank Problem: Birthday Chocolate

This is a HackerRank Problem. You can find it HERE

This is actually a very easy problem. I have decided to write a blog on it to remind myself of a mistake that I did when solving this.

Task Description

Lily has a chocolate bar that she wants to share it with Ron for his birthday. Each of the squares has an integer on it. She decides to share a contiguous segment of the bar selected such that the length of the segment mathches Ron's birth month and the sum of the integers on the squares is equal to his birth day. You must determine how many ways she can divide the chocolate.

Consider the chocolate bar as an array of squares, $s = [2, 2, 1, 3, 2]$. She wants to find segments summing to Ron's birth day, $d = 4$ with a length equalling his birth month, $m = 2$. In this case, there are two segments meeting her criteria: $[2, 2]\ and\ [1, 3]$.

Assumption

Chocolate bar has at least the length of 1. $i.e.$ The input $array\ length >= 1$.

Initial Solution (Fails For an Edge Case)

  static int solve(int n, int[] s, int d, int m) {
    int i = 0, j = 1;
    int sum = s[i];
    int counts = 0;
    for(; j < s.length; j++) {
        sum += s[j];
        
        if (sum > d) {
            sum -= s[i];
            i++;
        } else if (j - i == m - 1) {
            if (sum == d) counts++;
            sum -= s[i];
            i++;
        }
    }
    return counts;
  }

Simple isn't it? But it fails for an EDGE case. Can guess the Edge Case?

The Edge Case

Well the edge case is, in the code we have initialized sum as the first element of the array and as soon as we enter the loop we increment the sum with the second element of the array. This means we never consider the case where $m == 1$.

Actual Solution

We can solve this by initially considering NO any elements. We will start considering elements only after we start loop. So the only changes to be made are

int j = 0; // instead of j = 1;

and,
int sum = 0; // instead of sum = s[i]

  static int solve(int n, int[] s, int d, int m) {
    int i = 0, j = 0;
    int sum = 0;
    int counts = 0;
    for(; j < s.length; j++) {
        sum += s[j];
        
        if (sum > d) {
            sum -= s[i];
            i++;
        } else if (j - i == m - 1) {
            if (sum == d) counts++;
            sum -= s[i];
            i++;
        }
    }
    return counts;

}

Complexity

The solution solves the problem in one pass without using extra memory. So the time complexity is $\cal{O(n)}$ and the space complexity is $\cal{O(1)}$.

---

---

---

Shuffling Algorithm - Knuth Algorithm

You must be familiar how we shuffle a deck of card before start of any game. Its easy in real life to shuffle the deck of cards with hand.

How about in the online games? How would we shuffle a deck of card?

Shuffling should be done such that all the cards must be distributed uniformly i.e. every card should be distributed across the positions with equal probability. For the case of n items, all the items should be distributed with the probability of ${1 \over N}$.

Algorithm

1. We start by initializing $position = 0$.
2. Randomly pick an item from the array, range of the selection being $[position, N]$, where N = size of the array.
3. Swap the position of this random item with the item in the location $position$.
4. Increase $position$ by 1 and repeat from step 2 until $position == N$

Following this algorithm, it can be guaranteed that that each of the items in the array is uniformly distributed across the array with the probability of ${1 \over n}$.

$\def\specialFrac#1#2{\frac{x + #1}{y + #2}}$
• Probability of first item = $1 \over N$
• Probability of second item = $\textrm{probability of not being selected for first time} \times \textrm{probability of getting selected out of (N-1) items}$ = $\frac {N-1}{N} \times \frac {1}{N-1}$ = $\frac {1}{N}$
• Probability of third item = $\textrm{probability of not being selected for first time} \times \textrm{probability of not being selected for second time} \times$ $\textrm{probability of getting selected out of (N-2) items}$ = $\frac {N-1}{N} \times \frac {N-2}{N-1} \times \frac {1}{N-2}$ = $\frac {1}{N}$
• and so on...

So we can see that the probability of $\frac{1}{N}$ can be guaranteed for each of the items in the arra.

Implementation

	import java.util.Random;
	/**
	* This is a Shuffler class that can be used to shuffle given input array
	* uniformly
	*
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class Shuffler {
	private Random random;
	/**
	* Constructor to Shuffler instance.
	* initializes the variable random
	*
	*/
	public Shuffler() {
	random = new Random();
	} // Shuffler
	//----------------------------------------------------------------------------
	/**
	* returns random number between two given range
	* @param lo lower limit of the range
	* @param hi upper limit of the range
	*/
	private int getRandom(int lo, int hi) {
	return random.nextInt(hi - lo + 1) + lo;
	} // getRandom
	//----------------------------------------------------------------------------
	/**
	* swaps two items in the given array
	* @param nums input array in which swapping will be done
	* @param i first index to swap
	* @param j second index to swap
	*/
	private void swap(int[] nums, int i, int j) {
	int temp = nums[i];
	nums[i] = nums[j];
	nums[j] = temp;
	} // swap
	//----------------------------------------------------------------------------
	/**
	* methods that shuffles the given array
	* @param nums array to shuffle
	*/
	public void shuffle(int[] nums) {
	for (int i = 0; i < nums.length - 1 ; i++ ) {
	int rand = getRandom(i, nums.length-1);
	swap(nums, i, rand);
	}
	} // shuffle
	//----------------------------------------------------------------------------
	/**
	* driver method
	*/
	public static void main(String[] args) {
	int[] nums = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	Shuffler shuffler = new Shuffler();
	shuffler.shuffle(nums);
	for (int item : nums) {
	System.out.print(item + " ");
	}
	} // main
	//----------------------------------------------------------------------------
	} // Shuffler

view raw Shuffler.java hosted with ❤ by GitHub

Complexity

The algorithm shuffles the array in one pass and in place. So, the overall time complexity is $\cal{O(n)}$ and space complexity is $\cal{O(1)}$.

---

---

---

java.sql.SQLException: Operation not allowed after ResultSet closed

I faced this problem recently. As a part of closing some resources, I was closing resources in the finally block.

  ResultSet resultSet; // class variable

  ...
  ...
  Statement st = null;
  try {
    st = conn.createStatement();
    resultSet = st.getGeneratedKeys();
  } catch (Exception e) {
    throw e;
  } finally {
    try {
      if (st != null) st.close();
    } catch (SQLException e) {
      throw e;
    }
  }

      

As soon as I did this, I started to get the exception when I tried resultSet.hasNext();

java.sql.SQLException: Operation not allowed after ResultSet closed

My initial guess was I might have executed resultSet.close() somewhere. But it was not the case.

Problem

The actual problem is, ResultSet instance also saves underlying Statement. So, when the underlying Statment is closed (as done in the FINALLY block above), ResultSet is also closed. This causes the problem.

JavaDoc has clearly mentioned this.

When a Statement object is closed, its current ResultSet object, if one exists, is also closed.

Solution

So to fix the problem, you obviously cannot close the Statement instance untill you are done with ResultSet. Once you are done with ResultSet, you can close both ResultSet and Statement.

---

---

---

Count Number of Words in the given input String

Task Description

Given an input string, you need to get the number of words or list of words delimited by prefefined list of delimiter characters.

Simple Solution (Incorrect Solution)

I had come across this problem for the first time when I had just joined by Undergraduate Program. Then I was just learning how to code. So when I was given this problem for the first time, the solution I came up with was to traverse the entire string and count the number of delimiters. It would give correct word count for a normal sentence where we would expect only one delimiter in between each word and no leading or trailing spaces in the string.

Correct Solution

Idea

The problem in the simple solution discussed above is that there could be contigous sequence of delimiters in between the words. So the idea is to increase the word count only when we encounter a Non-Delimiter character right after a Delimiter character.

Edge Case

The edge case in this solution is, if there are no delimiters in the beginning of the string, then we will be missing the first word because we are increasing word count only after we encounter a delimiter character. This can be easily solved by assuming that we have encountered delimiters in the beginning.

Psuedo-Code

  boolean delimiter = true // assume we  have already encountered delimiters in the beginning to consider first word if there are leading delimiters
  int count = 0
  for i = 0 to input.length - 1
    char current = input.charAt(i)
    if current == delimiter:
      delimiter = true
    else 
      if delimiter: // non delimiter found after delimiters, increase word count
        count++
      delimiter = false

  return count

      

Similar logic can applied to actually get the list of words in the input string.

Implementation

Following the complete implemenation for the task. The method count() returns the number of words in the string and getWords() returns the list of the words.

The implementation has also pre-defined a list of delimiters based on which the input string will be splitted into words. Delimiters can be added or removed.

	/* File: WordCounter.java
	* Created: 5/14/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	import java.util.ArrayList;
	import java.util.HashSet;
	import java.util.List;
	import java.util.Set;
	/**
	* Utility Class to capture the words in the given input string delimited
	* by pre-defined delimiters
	*
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class WordCounter {
	private static Set<Character> delimiters = new HashSet<>();
	static {
	delimiters.add(' ');
	delimiters.add('\'');
	delimiters.add('!');
	delimiters.add('-');
	delimiters.add('(');
	delimiters.add(')');
	delimiters.add('{');
	delimiters.add('}');
	delimiters.add('[');
	delimiters.add(']');
	delimiters.add('?');
	delimiters.add('/');
	delimiters.add('\\');
	delimiters.add(',');
	}
	//---------------------------------------------------------------------------------------------
	/**
	* driver method
	* @param args
	*/
	public static void main(String[] args) {
	System.out.println(count("I am lord,voldemort")); // 4
	System.out.println(getWords("I am lord,voldemort")); // 4
	System.out.println(count("I am lord voldemort ")); // 4
	System.out.println(getWords("I am lord voldemort ")); // 4
	System.out.println(count(" I am lord voldemort")); // 4
	System.out.println(getWords(" I am lord voldemort")); // 4
	System.out.println(count(" I am lord voldemort ")); // 4
	System.out.println(getWords(" I am lord voldemort ")); // 4
	System.out.println(count(" Lord Voldemort! is my past, my present and my future!!!! ")); // 10
	System.out.println(getWords(" Lord Voldemort! is my past, my present and my future!!!! ")); // 4
	} // main
	//---------------------------------------------------------------------------------------------
	/**
	* Counts the number of words in the given input string
	* @param input input string
	* @return number of words in the input
	*/
	public static int count(String input) {
	boolean delimiter = true;
	int count = 0;
	for (int i = 0; i < input.length(); i++) {
	if (delimiters.contains(input.charAt(i))) { // delimiter encountered
	delimiter = true;
	} else {
	if (delimiter) { // first non delimiter encountered after sequence of delimiters, increase word count
	count++;
	}
	delimiter = false;
	}
	}
	return count;
	} // count
	//---------------------------------------------------------------------------------------------
	/**
	* Gets the list words in the input string
	* @param input input string
	* @return List of words in the input
	*/
	public static List<String> getWords(String input) {
	List<String> result = new ArrayList<>();
	boolean delimiter = true;
	//int count = 0;
	int wordStart = 0;
	for (int i = 0; i < input.length(); i++) {
	if (delimiters.contains(input.charAt(i))) { // delimiter encountered
	if (!delimiter) { // first delimiter after sequence of non delimiters, capture word
	result.add(input.substring(wordStart, i));
	}
	delimiter = true;
	} else {
	if (delimiter) {
	wordStart = i;
	//count++;
	}
	delimiter = false;
	}
	}
	if (!delimiter) {
	result.add(input.substring(wordStart));
	}
	return result;
	} // getWords
	//---------------------------------------------------------------------------------------------
	} // WordCounter

view raw WordCounter.java hosted with ❤ by GitHub

Complexity

We are traversing the string only once. For each character, we check if it is delimiter or not by comparing with a HashSet - this operation is contant time ${\cal O}(1)$ operation. Then we just set a boolean value and increase count if needed. Both of these are also constant time operations. $\therefore$ the overall time complexity of this solution is ${\cal O}(n)$, n being the length of the input string. Space complexity of the solution is obviously ${\cal O}(1)$.

---

---

---

Detect Loop in Linked List And Identify the Start of Loop

Task Description

Detect if a given linked list has a loop. If it has a loop, find the starting node of the loop.

Solution 1 : Simple Solution

When I first came across this problem, the solution that I thought of was to traverse through all the nodes and for every node, check if we have already encountered this node. If we ecnounter a node which has already been visited before, then the linked list has a loop. We can efficiently check if the node has already been visited by maitaining a HashSet of already visited nodes. The starting node of the loop will the first repeated node encountered.

If the linked list does not have a loop, then the traversal of the list will terminate without encountering any repeated node.

Implementation

	//-----------------------------------------------------------------------------------
	/**
	* Detects a loop in a given LinkedList
	* Based upon keeping track of already visited Nodes
	* @param head head of the LinkedList
	* @return start of loop if it exists, otherwise null
	*/
	public Node detectLoop(Node head) {
	Set<Node> visitedNodes = new HashSet<Node>();
	Node node = head;
	while (node != null) {
	if (visitedNodes.contains(node)) { // loop detected. node is the start of the loop
	return node;
	} else {
	visitedNodes.add(node);
	node = node.next;
	}
	}
	return null; // no loop
	} // detectLoop
	//------------------------------------------------------------------------------------

view raw DetectLoopInLinkedList.java hosted with ❤ by GitHub

Complexity

In this method, we traverse through all the nodes only once except the first repeated node if it exists. The repeated node will be traversed twice. Checking for a repeated node using HashSet is a constant time operation. $\therefore$ The Time Complexity of this method is ${\cal O}(n)$ time.

But we are saving each traversed node into a HashSet. $\therefore$ The Space Complexity of this method is also ${\cal O}(n)$ time.

Solution 2: Efficient Solution (Floyd's Method)

Floyd gave a more efficient method than discussed above. This method is efficient in terms of the space used. Time Complexity remains ${\cal O}(n)$ while the Space Complexity is constant time ${\cal O}(1)$.

Principle

Floyd's method is based upon a principle that if two pointers - one moving at the speed of one node at a time and another at twice the speed of the first, are circulating in a loop, then they will always meet at a node.

At any time, if Faster Pointer is just behind the Slower Pointer, then in the next step, they will meet.

At any time, if the Faster Pointer is just aheadd of the Slower Pointer, this position is possible only if they have met in the previous step.

Detecting the Loop

	Node faster = head;
	Node slower = head;
	// detect loop
	while (faster != null && faster.next != null) {
	faster = faster.next.next;
	slower = slower.next;
	if (faster == slower) { // loop detected
	break;
	}
	}
	if (faster != slower) return null; // loop not detected

view raw DetectLoopInLinkedList.java hosted with ❤ by GitHub

Mathematics - Identify the Start of Loop

Let, when the two pointers intersect,

$\ \ \ \ \ \ m = length\ of\ the\ non-loop\ branch$
$\ \ \ \ \ \ n = length\ of\ the\ loop$
$\ \ \ \ \ \ k = length\ from\ starting\ point\ of\ the\ loop\ to\ the\ point\ of\ intersection$

$\ \ \ \ \ \ x = number\ of\ complete\ loops\ made\ by\ the\ slower\ pointer$
$\ \ \ \ \ \ y = number\ of\ complete\ loops\ made\ by\ the\ faster\ pointer$

Now,
$\ \ \ \ \ \ distance\ traveled\ by\ faster\ pointer\ (F) = m + k + yn$
$\ \ \ \ \ \ distance\ traveled\ by\ slower\ pointer\ (S) = m + k + xn$

Since, faster pointer has moving at double the speed of slower pointer,
$\ \ \ \ \ \ \ \ \ F = 2S$
$\ \ \ \ \ \ => m + k + yn = 2(m + k + xn)$
$\ \ \ \ \ \ => m + k + yn = 2(m + k) + 2xn$
$\ \ \ \ \ \ => m + k = yn - 2xn$
$\ \ \ \ \ \ => m + k = n(y - 2x)$
$\ \ \ \ \ \ => \because faster\ pointer\ is\ moving\ at\ double\ speed,\ (y - 2x) >= 1\ and\ is\ ALWAYS\ an\ Integer.$
$\ \ \ \ \ \ => m + k = certain\ number\ of\ COMPLETE\ loop\ cycles$

So, we can conclude that,

1. If Two Pointers (move at the same speed) start moving at the same time, one start from beginning of the linked list and another start from beginning of the loop, by the time the first Pointer travels $m + k$ nodes, the second Pointer will make certain number of complete loop and reach the beginning the loop again.
2. If the first pointer moves only $m$ nodes, then the second pointer will complete some loop and travel $n- k$ nodes.
3. If the second pointer starts from the point of intersection instead of beginning of the loop, both of the pointer will meet at the beginning of the loop. This is our REQUIRED start of the loop.

Compute Start of the Loop

So based upon the theory above, we can find the start of the loop by following way:

1. When the two pointers meet (the loop is detected), keep one pointer at the same location and move the other to the beginning of the linked list.
2. Now move the two pointers at the same speed - one node at a time.
3. When the two pointers meet, the meeting point will be the beginning of the loop.

	// detect start of loop
	faster = head;
	while (faster != slower) {
	faster = faster.next;
	slower = slower.next;
	}
	return faster;

view raw DetectLoopInLinkedList.java hosted with ❤ by GitHub

Complete Implementation

	/* File: DetectLoopInLinkedList.java
	* Created: 2018-05-09
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart
	*/
	import java.util.HashSet;
	import java.util.Set;
	/**
	* Detect Loop in a Linked List
	*
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class DetectLoopInLinkedList {
	public static void main(String[] args) {
	DetectLoopInLinkedList detectLoopInLinkedList = new DetectLoopInLinkedList();
	int i = 1;
	Node head = detectLoopInLinkedList.new Node(i++);
	Node tail = head;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++); // 11
	tail = tail.next;
	Node loopBegin = tail;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	// No Loop
	Node loopStart1 = detectLoopInLinkedList.detectLoop(head);
	Node loopStart2 = detectLoopInLinkedList.detectLoopFloydMethod(head);
	System.out.println(loopStart1 == null && loopStart2 == null ? "SUCCESS: Loop Not Found" : "Failure");
	// Crate Loop at 11
	tail = tail.next;
	tail.next = loopBegin;
	loopStart1 = detectLoopInLinkedList.detectLoop(head);
	loopStart2 = detectLoopInLinkedList.detectLoopFloydMethod(head);
	System.out.println(loopStart1 == loopStart2 ? "SUCCESS: Loop Start Found: " + loopStart1.value : "Failure");
	} // main
	//-----------------------------------------------------------------------------------
	/**
	* Detects a loop in a given LinkedList
	* Based upon keeping track of already visited Nodes
	* @param head head of the LinkedList
	* @return start of loop if it exists, otherwise null
	*/
	public Node detectLoop(Node head) {
	Set<Node> visitedNodes = new HashSet<Node>();
	Node node = head;
	while (node != null) {
	if (visitedNodes.contains(node)) { // loop detected. node is the start of the loop
	return node;
	} else {
	visitedNodes.add(node);
	node = node.next;
	}
	}
	return null; // no loop
	} // detectLoop
	//------------------------------------------------------------------------------------
	/**
	* Detect Loop in a LinkedList using Floyd's Method
	* @param head Head of the LinkedList
	* @return start of loop if it exists, otherwise null
	*/
	public Node detectLoopFloydMethod(Node head) {
	Node faster = head;
	Node slower = head;
	// detect loop
	while (faster != null && faster.next != null) {
	faster = faster.next.next;
	slower = slower.next;
	if (faster == slower) { // loop detected
	break;
	}
	}
	if (faster != slower) return null; // loop not detected
	// detect start of loop
	faster = head;
	while (faster != slower) {
	faster = faster.next;
	slower = slower.next;
	}
	return faster;
	} // detectLoopFloydMethod
	//------------------------------------------------------------------------------------
	/**
	* Class to represent Linked List Node
	*/
	public class Node {
	Node next;
	int value;
	public Node(int value) {
	this.value = value;
	} // Node
	} // Node
	} // DetectLoopInLinkedList

view raw DetectLoopInLinkedList.java hosted with ❤ by GitHub

Time Complexity

Time complexity is ${\cal O}(n)$ and the Space complexity is ${\cal O}(1)$.

---

---

---