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

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

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

---

---

---

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.

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

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.

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

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.

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.

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.

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.

Complete Implementation

---

---

---

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:

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.

---

---

---

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

---

---

---

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

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:

---

---

---

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

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

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

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

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

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

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.

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

---

---

---

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

---

---

---

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

---

---

---

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

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

---

---

---

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

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)}$.

---

---

---