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

[iOS] - Semaphore to control access to shared resource

1. DispatchSemaphore is initialized with maximum number of threads to access the shared resource.
2. It provides methods wait()/signal() to lock/unlock resource
3. If the resource access is locked in a lower priority thread by semaphore, it freezes and releases the resource until finish it although the higher priority thread is there, this is called Priority Inversion or Priority Inheritance.

• Multiple Semaphore access resource wait for each other can cause deadlock

[iOS] - Core Data Notes

1. Core data is a framework to manage you data graph, not a database. It support data being saved as XML, binary, SQLite and Memory.
2. One app could have multiple data stores, because for some cases, some data need to store in memory, some need to store in SQLite, etc.
3. Managed object can't be passed crossing thread, but you can do it by using its ManagedObjectID.
4. MOC(Managed Object Context) - the data change is only propagated from child to parent and not the other round, and not propagated between siblings.
5. Multiple thread (concurrency) supports - main queue and private queue in background thread, you have to use perform related methods to save the change if it's in a private queue.
6. Merge types: as the data may be reading and writing in multiple thread, you should choose data merge type for data propagating. Types includes: trump memory, trump object, override, discard.
7. Memory and performance
1. Specify the fields only that you desire.
2. Result limitation.
3. Decrease fault overhead by using batch faulting and prefetching.
4. Check and manage you data in memory like using reset method, etc.
   https://developer.apple.com/library/archive/documentation/Cocoa/Conceptual/CoreData/Performance.html#//apple_ref/doc/uid/TP40001075-CH25-SW1