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

Helpe Links

iOS

1. Core Data Concurrency Debugging 
   https://oleb.net/blog/2014/06/core-data-concurrency-debugging/
2. 
   

Make the framework bitcodable

In the project build settings:

ENABLE_BITCODE = YES

BITCODE_GENERATION_MODE = bitcode

In the Podfile

...

use_frameworks!

target 'ProjectName' do

    pod 'PodName'

    target 'ProjectName Tests' do

        inherit! :search_paths

        pod 'PodName'

    end

    

    post_install do |installer|

        installer.pods_project.targets.each do |target|

            target.build_configurations.each do |config|

                config.build_settings['ENABLE_BITCODE'] = 'YES'

                config.build_settings['BITCODE_GENERATION_MODE'] = 'bitcode'

            end

        end

    end

end

[iOS] - Method Swizzling

Method swizzling is the process of changing the implementation of an existing selector. It’s a technique made possible by the fact that method invocations in Objective-C can be changed at runtime, by changing how selectors are mapped to underlying functions in a class’s dispatch table.

For example, let’s say we wanted to track how many times each view controller is presented to a user in an iOS app:

Each view controller could add tracking code to its own implementation of viewDidAppear:, but that would make for a ton of duplicated boilerplate code. Subclassing would be another possibility, but it would require subclassing UIViewController, UITableViewController, UINavigationController, and every other view controller class—an approach that would also suffer from code duplication.

Fortunately, there is another way: method swizzling from a category. Here’s how to do it:

#import <objc/runtime.h>

@implementation UIViewController (Tracking)

+ (void)load {
    static dispatch_once_t onceToken;
    dispatch_once(&onceToken, ^{
        Class class = [self class];

        SEL originalSelector = @selector(viewWillAppear:);
        SEL swizzledSelector = @selector(xxx_viewWillAppear:);

        Method originalMethod = class_getInstanceMethod(class, originalSelector);
        Method swizzledMethod = class_getInstanceMethod(class, swizzledSelector);

        // When swizzling a class method, use the following:
        // Class class = object_getClass((id)self);
        // ...
        // Method originalMethod = class_getClassMethod(class, originalSelector);
        // Method swizzledMethod = class_getClassMethod(class, swizzledSelector);

        BOOL didAddMethod =
            class_addMethod(class,
                originalSelector,
                method_getImplementation(swizzledMethod),
                method_getTypeEncoding(swizzledMethod));

        if (didAddMethod) {
            class_replaceMethod(class,
                swizzledSelector,
                method_getImplementation(originalMethod),
                method_getTypeEncoding(originalMethod));
        } else {
            method_exchangeImplementations(originalMethod, swizzledMethod);
        }
    });
}

#pragma mark - Method Swizzling

- (void)xxx_viewWillAppear:(BOOL)animated {
    [self xxx_viewWillAppear:animated];
    NSLog(@"viewWillAppear: %@", self);
}

@end

In computer science, pointer swizzling is the conversion of references based on name or position to direct pointer references. While the origins of Objective-C’s usage of the term are not entirely known, it’s understandable why it was co-opted, since method swizzling involves changing the reference of a function pointer by its selector.

Now, when any instance of UIViewController, or one of its subclasses invokes viewWillAppear:, a log statement will print out.

Injecting behavior into the view controller lifecycle, responder events, view drawing, or the Foundation networking stack are all good examples of how method swizzling can be used to great effect. There are a number of other occasions when swizzling would be an appropriate technique, and they become increasingly apparent the more seasoned an Objective-C developer becomes.

Regardless of why or where one chooses to use swizzling, the how remains absolute:

+load vs. +initialize

Swizzling should always be done in +load.

There are two methods that are automatically invoked by the Objective-C runtime for each class. +load is sent when the class is initially loaded, while +initialize is called just before the application calls its first method on that class or an instance of that class. Both are optional, and are executed only if the method is implemented.

Because method swizzling affects global state, it is important to minimize the possibility of race conditions. +load is guaranteed to be loaded during class initialization, which provides a modicum of consistency for changing system-wide behavior. By contrast, +initialize provides no such guarantee of when it will be executed—in fact, it may never be called, if that class is never messaged directly by the app.

dispatch_once

Swizzling should always be done in a dispatch_once.

Again, because swizzling changes global state, we need to take every precaution available to us in the runtime. Atomicity is one such precaution, as is a guarantee that code will be executed exactly once, even across different threads. Grand Central Dispatch’s dispatch_once provides both of these desirable behaviors, and should be considered as much a standard practice for swizzling as they are for initializing singletons.

Selectors, Methods, & Implementations

In Objective-C, selectors, methods, and implementations refer to particular aspects of the runtime, although in normal conversation, these terms are often used interchangeably to generally refer to the process of message sending.

Here is how each is described in Apple’s Objective-C Runtime Reference:

• Selector (typedef struct objc_selector *SEL): Selectors are used to represent the name of a method at runtime. A method selector is a C string that has been registered (or “mapped”) with the Objective-C runtime. Selectors generated by the compiler are automatically mapped by the runtime when the class is loaded .
• Method (typedef struct objc_method *Method): An opaque type that represents a method in a class definition.
• Implementation (typedef id (*IMP)(id, SEL, ...)): This data type is a pointer to the start of the function that implements the method. This function uses standard C calling conventions as implemented for the current CPU architecture. The first argument is a pointer to self (that is, the memory for the particular instance of this class, or, for a class method, a pointer to the metaclass). The second argument is the method selector. The method arguments follow.

The best way to understand the relationship between these concepts is as follows: a class (Class) maintains a dispatch table to resolve messages sent at runtime; each entry in the table is a method (Method), which keys a particular name, the selector (SEL), to an implementation (IMP), which is a pointer to an underlying C function.

To swizzle a method is to change a class’s dispatch table in order to resolve messages from an existing selector to a different implementation, while aliasing the original method implementation to a new selector.

Invoking _cmd

It may appear that the following code will result in an infinite loop:

- (void)xxx_viewWillAppear:(BOOL)animated {
    [self xxx_viewWillAppear:animated];
    NSLog(@"viewWillAppear: %@", NSStringFromClass([self class]));
}

Surprisingly, it won’t. In the process of swizzling, xxx_viewWillAppear: has been reassigned to the original implementation of UIViewController -viewWillAppear:. It’s good programmer instinct for calling a method on self in its own implementation to raise a red flag, but in this case, it makes sense if we remember what’s really going on. However, if we were to call viewWillAppear: in this method, it would cause an infinite loop, since the implementation of this method will be swizzled to the viewWillAppear: selector at runtime.