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