About American Flag Sort

American Flag Sort is an extension of Dutch Flag Problem which divides an array into three group. American Flag Sort further divides an array into multiple buckets based on certain order. For example, 256 buckets based on ASCII value. Essentially, it is a in-place radix sort. It is favored for sorting integers and strings givens its speed and space advantage.

• The algorithm needs two passes. First scan the array, so that we know the number of the the objects that will be stored in each bucket.
• Then we know the start location of each bucket. Scan the array for the second time, put the object to the corresponding bucket and update the bucket cursor.
• If sorting strings, may need to apply the same algorithm to sort objects within each bucket.

0-1 Knapsack Problem

Problem:  Given a knapsack that can hold at most W weight items, also given a list of items with their weight wi and value vi (no items share the same weight), try to find a valid assignment which achieve the highest value in the knapsack (can't  be over-weighted at the same time).

Solution: We can use DP to solve this problem. However, one-dimension DP is not enough. If we only record state s[0], s[1], ... s[W], the later state may not be able to reuse previous states. Instead, we need a two-dimension DP here:

• First sort the items based on their weights
• The status we want to calculate is s[i, w], which means if the total weight is w and we can only use up To the ith item (based on weight and non-descending), the optimal maximum value we can get.
•  s[0, w] = 0 and  s[i, 0] = 0. 
• For  s[i, w], if wi > w,  s[i, w] =  s[i-1, w]; otherwise,  s[i, w] = max ( s[i-1, w], s[i-1, w-wi] + vi).

Multi-Processor Scheduling Problem

Problem: Give a multi-processor machine with n processors and m jobs, how to make a scheduling that has the shortest finish time. Each job may take different amount of time to process.

Solution: There are also some variants to this problem, like putting m integers to n buckets. The solution to this problem can be based on some heuristics and is called LPT algorithm. Attention: this is a greedy approach which is a sub-optimal solution, not an optimal solution.

• Basically we first sort the job based on their process time.
• Choose the job with the longest process time among the current unprocessed jobs and put it into a machine which has the earliest finish time so far.
• Repeat the above steps until all jobs are assigned.
• The complexity is O(m*logm+m*logn+n).

Find 4 Elements in An Array that Sum to A Target Value

Problem: Given an array and a target value, find 4 elements in the array that sum to this target value.

Solution: Here introduce an O(n^2) algorithm. Only briefly explain the idea:

• Calculate the sums of all pairs in the array and form a new array. Each element in the new array is a struct that stores the sum and the two elements who make the sum. Sort the array by the sum. The cost is  O(n^2) till now (may need radix sort).
• The problem is converted to find 2 elements in the new array that sum to the target value. The cost for this operation is the length of the new array, which is also O(n^2). So total cost is O(n^2).

Some Problem Solved by Suffix Tree

Problem 1: Find the longest common substring among k strings.

Solution: If we use DP, it takes O(n1*n2*...nk). With suffix tree, it takes O(n1+n2+...nk). Basically, we build the suffix tree for n1 first, then add n2 to this tree, then n3... All the strings share the same generalized suffix tree. We need to track if each node (path) is shared by all the string or not. When the building is done, the longest common substring will be found.


Problem 2: Find the longest repeated substring in a string.

Solution: First, build the suffix tree for this string. Then find the deepest internal node, from the root to that node is the substring we are looking for. The "deepest" is decided by the number of characters.

Serialize a Binary Tree

We know with pre-order and mid-order we can decide a binary tree. Besides, tree have array representation. However, to have better space efficiency, we can just store a binary tree according to its pre-order, but with null node also stored!

Find Two Substrings with Longest Distance from Two Strings

Problem: Given two strings s1 and s2, s1' and s2' are two substrings of s1 and s2, respectively. Find the s1' and s2' with longest distance. Distance is defined as \sum_i| s1' [i] -s2' [i]|.

Solution: Obviously,  s1' and s2' should be of equal length. Here give a O(n*m) algorithm where n and m are the length of  s1 and s2,  respectively.

• Calculate c[i][j] = |s1[i]-s2[j]|, then we have a matrix.
• Swipe the matrix with a diagonal line. For example, s1 = "35645",  s2 ="2475", we have matrix c as follow:
  1 1 4 2
  3 1 2 0
  4 2 1 1
  2 0 3 1
  3 1 2 0
• First we scan "2", then "4 0",  then "1 2 1". You calculate the sum of the numbers in the line. Later you will find the maximum is "3 2 3 0" or "3 2 3", which stands for the distance of "5645" and "2475".