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.

---

---

---