Arrays

Single Array

1. Quick sort
• Recursive quickSort(array, start, end) whenever start < end
• Do partition in each recursion
• Select the last item as pivot, scan array from left to right side and move the item to front whenever the item is less than pivot, finally swap the pivot. 
• Move from both sides to center, and swap it when left side it greater than right side, until both pointers meets.
2. Quick sort with given comparison [nuts & bolts problem]
   

   Given:
   nuts = ['ab','bc','dd','gg'], bolts = ['AB','GG', 'DD', 'BC'].
   
   Return:
   nuts = ['ab','bc','dd','gg'], bolts = ['AB','BC','DD','GG'].

   private void qsort(String[] nuts, String[] bolts, NBComparator compare, 
                          int l, int u) {
           if (l >= u) return;
           // find the partition index for nuts with bolts[l]
           int part_inx = partition(nuts, bolts[l], compare, l, u);
           // partition bolts with nuts[part_inx]
           partition(bolts, nuts[part_inx], compare, l, u);
           // qsort recursively
           qsort(nuts, bolts, compare, l, part_inx - 1);
           qsort(nuts, bolts, compare, part_inx + 1, u);
       }
   
       private int partition(String[] str, String pivot, NBComparator compare, 
                             int l, int u) {
           //
           int m = l;
           for (int i = l + 1; i <= u; i++) {
               if (compare.cmp(str[i], pivot) == -1 || 
                   compare.cmp(pivot, str[i]) == 1) {
                   //
                   m++;
                   swap(str, i, m);
               } else if (compare.cmp(str[i], pivot) == 0 || 
                          compare.cmp(pivot, str[i]) == 0) {
                   // swap nuts[l]/bolts[l] with pivot
                   swap(str, i, l);
                   i--;
               }
           }
           // move pivot to proper index
           swap(str, m, l);
   
           return m;
       }

3. Binary search
• Sort it first with quick sort.
• Recursive binary(array, start, end) until the result is found in the center.
4. Maximum separation
• Create another array to keep the ordered result based on the passing array. 
• eg: try to find maximum j-i,  a[i] < a[j], the passing array is [1, 3, 6, 9, 2], the new ordered array will be [1, 1, 1, 9, 2]
• Use another iteration to find the maximum length of same item.
5. Rotation 
• 3 steps rotation - O(1) space and O(n) time complexity
• Divide to two parts
• Rotate first part
• Rotate second part
• Rotate whole
6. Interleaving array [-1, -2, -3, 4, 5, 6] >> [-1, 5, -2, 4, -3, 6]
• check the negative and positive numbers first to decide which one should be first.
• Then replace them necessarily by using while.
7. Assign candy to children, to make sure each child has more candy than his neighbors
• first scan from left to right, add 1 to right if right > left
• then scan from right to left, add 1 to left if left > right
8. Maximum difference / gap
1. TODO...
9. Sum of K items 
1. Sum of 2 items
• O(n) by putting items in a map
2. Sum of 3 items
• Iterate items as current pointer
• Find another two from rest of items, use two pointers to scan from both ends to center
3. Sum of K items
• lookingList - the list of items matching the result
• k - number of item required
• remain - the mount to reach the result
• index - the start index
  

  public recursion(array[], lookingList, k, remain, index) {
   if (k == lookingList.size()) {
    if (remain == 0) {
     // Done 
     find the result here
    }
    return;
    }
  
    for (int i = index; i < array.length; i++) {
     // append 
     lookingList.add(array[i]);
     // Recursion
     recursion(array, lookingList, k, remain-array[i], i+1);
     // Remove the last one
     lookingList.remove(lookingList.size() - 1);
    }
  }

Two Arrays

1. Best match / mini difference between two arrays
• Sort the two arrays first
• Compare array A[i] and B[j] then to increase i or j respectively, until the best value is found.
2. Merge two arrays
• Increase the array to size = i+j-1
• Add data to new array from right side to left
3. Find Kth largest item in two array
• use exclusion, remove k/2 items every time util k=0 or k=1
  

  double helper(int A[], int m, int B[], int n, int k){
      // find the kth largest element
      if(m > n)
          return helper(B, n, A, m, k);//make sure that the second one is the bigger array;
      if(m == 0)
          return B[k - 1];
      if(k == 1){
          return min(A[0], B[0]);
      }
      int pa = min(k / 2, m); // assign k / 2 to each of the array and cut the smaller one
      int pb = k - pa;
      if (A[pa-1] <= B[pb-1])
          return helper(A + pa, m - pa, B, n, k - pa);
      return helper(A, m, B + pb, n - pb, k - pb);
  }

4. TODO