Binary numbers and shift operators

int x = 4;

Integer.toBinaryString(x) : 10;

int x = 4 (100) >> 1: right shift 1 position, 2 (10);

int x = 4 (100) << 1: left shift 1 position, 8 (1000);

~       Unary bitwise complement
<<      Signed left shift
>>      Signed right shift
>>>     Unsigned right shift
&       Bitwise AND
^       Bitwise exclusive OR
|       Bitwise inclusive OR

Quicksort!

The algorithm is very easy to understand. I used C++ due to the lack of updated Java complier on our cluster.

Be careful on the boundaries of each recursion.

      

    void qsort (int col, int left, int right)
          {
              int i = left, j = right;
              vector tmp;
              double pivot = output[(left + right)/2][col];
  
              //sort
              while (i <= j)
              {
                 while (output[i][col] < pivot && i < right)
                 {
                     i++;
                 }
                 while (output[j][col] > pivot && j > left)
                 {
                     j--;
                 }
 
                 if(i <= j)
                 {
                     tmp = output[i];
                     output[i] = output[j];
                     output[j] = tmp;
                     if(i < right)
                         i++;
                     if(j > left)
                         j--;
                 }
              }
             if (left < j)
             {
                 qsort(col,left,j);
             }
             if (i < right)
             {
                 qsort(col,i,right);

             }
         }

Reverse Linked List

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Label the m-th node(label) and the node before m-th node (prelabel). Insert nodes afterwards till the n-th node one by one between prelabel and label. 

prelabel: 1
label: 2
1 -> 3 -> 2 -> 4 -> 5
1 -> 4 -> 3 -> 2 -> 5

public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null)
            return null;
        if (m == n)
            return head;
            
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        int index = 1;
        ListNode prelabel = dummy;
        for (index = 1; index < m; index++)
        {
            prelabel = head;
            head = head.next;
            if (head == null)
                return null;
        }
        ListNode prev = head;
        ListNode label = head;
        head = head.next;
        //index ++;
        for (index = m + 1; index <= n; index++)
        {
            label.next = head.next;
            prelabel.next = head;
            head.next = prev;
            prev = head;
            head = label.next;
        }
        return dummy.next;
    }
}

Algorithm questions will nearly always be from the following list by someone

• String manipulation such as:
  • Reverse String
  • string.split(" ")
  • StringBuilder.append
  • remove the last " "
  • Count how many times each letter appears in a given String
  • charAt(i)
• LinkedList questions such as:
  • How to remove a node, pay close attention to edge cases such as removing the head
  • How to reverse a linkedList (make the Tail the Head)
• Binary Tree questions such as:
  • In-order traversal
  • If there is a BTree balancing question you won't need to implement it, just understand that a completely unbalanced Binary Tree is simply a Linked List.
  • Understand that searching a balanced Binary Tree is O(log n) compared to a Linked List or a completely unbalanced Binary Tree which is O(n).

Time complexity of different data structures

Arrays

• Inserting: O(1) for all the positions, since it is done with indexes
• Deleting: O(n) if we have to find the element, O(1) if we know position of the element
• Searching: O(n) if array is unsorted and O(log n) if array is sorted and something like a binary search is used.

Linked List:

• Inserting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
• Deleting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
• Searching: O(n)

Doubly-Linked List:

• Inserting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
• Deleting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
• Searching: O(n)

Stack:

• Push: O(1)
• Pop: O(1)
• Top: O(1)
• Search (Something like lookup, as a special operation): O(n) (I guess so)

Queue/Deque/Circular Queue:

• Insert: O(1)
• Remove: O(1)
• Size: O(1)

Binary Search Tree:

• Insert, delete and search: Average case: O(log n), Worst Case: O(n)

Heap/PriorityQueue (min/max):

• findMin/findMax: O(1)
• insert: O(log n)
• deleteMin/Max: O(log n)
• lookup, delete (if at all provided): O(n), we will have to scan all the elements as they are not ordered like BST

HashMap/Hashtable/HashSet:

• Insert/Delete: O(1) amortized
• Re-size/hash: O(n)
• Contains: O(1)

Special thanks to Stackoverflow!

The catch block in JAVA

The exception handler actually exists in most of the language, interestingly I have never found it when I write C++.

http://docs.oracle.com/javase/tutorial/essential/exceptions/catch.html