Dynamic programming

• Order/Validate data frame overlaps [Solve problems like plane/airport traffic ]
1. Order data frame according some rule
2. Create data points for each start/end of data frame
3. Order data points
4. Check with stack, push to stack when it's a start point, pop from stack when it's end point, you can check the number of points in the stack to do your business.
• 
  

Stack

The cases we usually need to consider to use stack:

• We need to compare successive data items, use the peek method to get previous one to compare with current one, then pop up the peek or insert current one the the stack.
• Usually need to return a consequence which the length is different from the one passed.

1. Math
• iterate the array
• push to stack when it's a number
• otherwise pop two items to calculate
  

  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

2. dfd

String

1. Isomorphic String - use a map to mapping each letters in the strings
   

   Given "egg", "add", return true.
   Given "foo", "bar", return false.
   Given "paper", "title", return true.

2. Todo...

Range merge or exclusive

To check the intersections between interval [a,b] and [c,d], there are four cases (equal not shown in the figures):

    a____b
c____d

a____b
     c____d

a_______b
    c___d

   a___b
c_______d

But we can simplify these into 2 cases when check the smaller (smaller start point) interval with the bigger interval.

Peaks and Valleys

1. Sort the array into an alternating sequence of peaks and valleys
• Compare closed 3 items and swap them necessarily
  

  for (int i = 1; i < array.length; i+= 2) {
   int biggestIndex = maxIndex(array, i-1, i, i+1); 
   if (i != biggestIndex) {
     swap(array, i, biggestIndex); 
   } 
  }

2. TODO

Matrix

1. If we need to update matrix, please don't update it first then find the next ones need to update. What we should do is to find all the items need to update and do it once.
2. Find sub matrix
1. It's O(n3) time complexity, O(n2)for space complexity, the outmost iteration is for getting all the possible sub matrixes. 
2. In each sub matrix, use an array to store the sum(or other rule) of each row/column, and result is also putting in a map or other data structure for future use.
3. Minimum/Maximum triangle path sum
• Create an array that the length is equal to triangle's level, to store the sum from root to the node.
  

  if (j == i) {
   // First
   m[j] = m[j-1] + cur.get(j);
  } else if (j == 0) { 
   // Last
   m[j] = m[0] + cur.get(0);
  } else {
   // Others
   m[j] = Math.min(m[j-1], m[j]) + cur.get(j);
  }

• After it's finished, find the max/min value in the array.
4. Search in ordered matrix
• Start from top right, the trace for searching 9 is [20 > 10 > 5 > 6 > 9]
  

  1    5    10   20
  2    6    11   30
  7    9    12   40
  8    15   31   41

5. TODO..

Palindrome

1. Generate shortest palindrome
1. Start check from center to both sides, the center could be one or two items.
2. In each check method, if it could expand to one end, the palindrome is found. We just need to reverse the rest of string and add to the other side.
2. Check if it's a palindrome
• User two pointer scan from both sides to center, until two pointers meet
• Or start from center to both side, we need to check the number of characters is old or even

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