Wednesday, September 17, 2014

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

Tuesday, September 16, 2014

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);

             }
         }

Sunday, September 14, 2014

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->NULLm = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note: Given mn 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

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

Linked List:

  • InsertingO(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
  • DeletingO(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
  • SearchingO(n)

Doubly-Linked List:

  • InsertingO(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
  • DeletingO(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
  • SearchingO(n)

Stack:

  • PushO(1)
  • PopO(1)
  • TopO(1)
  • Search (Something like lookup, as a special operation): O(n) (I guess so)

Queue/Deque/Circular Queue:

  • InsertO(1)
  • RemoveO(1)
  • SizeO(1)

Binary Search Tree:

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

Heap/PriorityQueue (min/max):

  • findMin/findMaxO(1)
  • insertO(log n)
  • deleteMin/MaxO(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/DeleteO(1) amortized
  • Re-size/hashO(n)
  • ContainsO(1)
Special thanks to Stackoverflow!

Saturday, September 13, 2014

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