Logging your stuffs, and prepared for rollback

Today, the reality of research teaches me a lesson...
Few weeks ago, I began to split the data into a number of fragments, and distributed them on different machines. Yesterday, I finished the code which could combine the separated data into one and perform the final step. It seems pretty good, but it is not... As it has been so long since the date I setup the first step, some critical configurations I made has became blurred. I suppose to remember those simple numbers which parsed into my programs, but it has been to late to correct me.
I lost about 20% of the data, which may need another few weeks to recover.
So, I suggest that, every one should keep a simple log, to record some crucial information you may need in the future, such as what/when/how you have done. Even it is not exact you need, it could help you to remember at least.

How to create a program to handle HUGE data?[0]

In the past few weeks, I was working on a project that need a program to "handle" millions of files. The verb, "handle", here means to download millions of html files from remote server, parse the html to find interested URLs and texts,  download images pointed by the URLs and organize all the files in a 3-level hierarchy.
In the following posts, I will discuss what I have suffered during the development, what I have applied to the system, and what I want to do but have not done yet. All the topics which gonna be covered can be classified into two categories, design philosophy and  design pattern.

... to be continued...

还是彪哥适合我

Leon是很酷，Bourne是很帅......
但这显然不是我风格，还是彪哥适合我
一起支持彪哥，学习彪哥！
为大家带来快乐！

这是彪哥网：http://www.biaoge.org

Maximal matching of bipartite graph

Bipartite graph is such a graph, whose nodes could be divided into two sets, X and Y. Any node in either X or Y does not connect to the other node in the same set. Any edges connect one node in X and one node in Y. Given a bipartite graph, G, M is a subset of the edges in G. If any two edges do not connect to the same node, we call M is a match. In addition, if M contains the maximal number of edges, M is a maximal match.
There are mainly two methods to find maximal matching, max flow algorithm and Hungarian algorithm. Hungarian algorithm use the idea behind max flow algorithm, but simplified the max flow algorithm based on the properties of bipartite matching and improve the performance.
Before we read those algorithm, another definition need to be clarified, augmenting path. If P is the path that connects two unmatched nodes, and the nodes in M and not M appear alternately, then we call P is a augmenting path on M. Then we could generalize 4 conclusions as follows:

• The length of P must be odd; the first edge and the last edge should not belongs to M;
• All the odd number edges are not in M, and all the even number edges are in M;
• A bigger match M` could be found by “invert” P. Here, “invert” means put all odd number edges into M, and remove all even number edges in P from M. So there must be one more match.
• M is the maximal match, if and only if, there is not augmenting path in G;

So the key to solve the max flow algorithm is finding the augmenting path. The basic steps are as follows:

Initialize the Maximal Match, MM, as null;
while( augmenting path exists )
{
    Add the augmenting path into MM;
    
}

The main idea of the algorithm above is keeping searching augmenting paths, which could increase the number of matching. In matching problem, augmenting path looks like a zigzag. If the first edge of a graph does not in match, its second edge should be in, and so on. If we could invert the selection of matches, we could find one more match legally.
Further Properties:

• Minimal covering: find the minimal set of node, m, and make each edge connects to an arbitrary node in m. So,

            minimal covering = the maximal matching

• The minimal path covering = |N| – maximal match.

Use minimal number of unoverlapping edges cover all the nodes in the graph, G. We could build up a bipartite model. All the nodes are divided into two sets, X and Y. If there is a edge i->j, then we add edge(i->j`). If the maximal match is m, then the result is n-m;

• Max independent set = (node number) – (bipartite maximal  match)

In a graph which have N nodes, we select m nodes, and each pair of the m nodes are not connected. Then find the maximal m. If G satisfies bipartite, then we could use bipartite matching to find result, as the minimal path covering = |N| – maximal match

Running on linked list :)

As a widely used data structure in both academia and industrial, linked list is a critical concept, which often appears in technical interview. In this blog, I will not show the basic implementation of LL. You may found it in your textbooks. However, few advanced questions in bird view are presented. By analyzing those questions, I hope you could build up a scene that how to manipulate linked list and some properties of LL.
Question 1: find the last K node of a given linked list;
Suppose you have a singly linked list L, please return the last K node in the list.
Solution: this problem is trivial. We could define two pointers, p1 and p2. We move p1 to the K-th node in the list and then move both pointers to the end node concurrently. Once p1 reaches the end, p2 points to the last K-th node.
Question 2: How to detect two linked lists merge or not;
Suppose you have two singly linked list, L1 and L2. Return true if those two lists merge at a arbitrary node; otherwise, return false.
Solution: This question is also trivial. If two lists merge, the end node must be the same. If we go through those two lists and end at the some node, we return true. Otherwise, they do not merge.
The method mentioned above need an assumption, there is no loop in both lists. If there is a loop, the method above will not work. If we could detect whether a loop is in the list, we could have the following generic algorithm to determine the return value.
detect loop
if no loop in both list, compare the end node;
if there are loops, check the node in one loop. If it is also in other loop, then they merge; otherwise, then do not.
Question 3: How to detect loops in a linked list;
Give you a singly LL, detect whether there is a loop in it.
Solution: the answer to this problem is really interesting. We could define two pointer, Fast and Slow. Fast pointer moves two nodes per time and Slow move one step each time. If there is a loop, those two pointers will meet in a position in the loop. In order to make the correctness easier, we assume that the length of the linked is upper bounded. We move the pointers until touch the upper bounder, which could guarantee we wont stop before enter the loop.
If we move this question a little further, how to find the beginning of the loop? Suppose the LL looks as follows:

The speed of those two pointers are 2 and 1. when they meet, if the total length of Slow moved is S, the Fast should have moved 2S. In addition, Fast moved n loops more. If the length of loop is r, we have nr = S. S can be replaced by a + x, the distance between loop enter point and meet point. So we have:

a + x = nr =  ( n - 1 )r + L -  a
Then:
a = ( n - 1 )r + ( L - a - x )

( L-a-x ) is the length between the meet point and the next loop enter point. So, if release another two pointers, Slow, at first node and meet point, they must meet at enter point of the loop, as ( n –1 )r will be cancelled by the loop.

Question 4: There is a straight track on the ground. Two robots randomly placed on the track. You need to deploy program on both robots. By executing the same program, they must collide each other.( This is a real interview question from Microsoft Advanced Technology Center in China )
There are four instructions in the instruction set:

• go left
• go right
• check. Return true if the other robot visited current position, otherwise, return false;
• jump, jump to any position in the program;

Solution: This question is easier than the Question 3. We could write a program like follows:

start:

if(at the position other robots have not reached)

    move_right

if(at the position other robots have reached)

    move_right

    move_right

goto start

The idea of this algorithm is initiative. If one robot found the other one is in front of it( the position visited by the other robot ), it runs faster to catch up.

Dynamic programming

Dynamic programming, or DP for short, can be applied on the problems that could be divided into sub problems. The solution of the entire problem can be found by “combing” the solutions of its sub problem. The main steps of DP can be generalized as follows:

• define the solution;
• recursively define the solutions from sub solution;
• calculate the solution, from bottom to the top;
• generate a solution based on the sub-solutions.

There are two key points needed to be clarified, before applying DP. The first is optimal substructure and the other one is overlapping sub problems.

• Optimal substructure, means the substructures of a solution must be also optimal;
• Overlapping sub problem, means the sub problems, when we recursively decompose the problem, may not be always new problems. For example, some problems may need to be calculated many times. If we could store the result of it, then we could just lookup the result, instead of recalculating. In another world, DP is a method which uses space to reduce time.

Now, let us check a typical DP problem, longest common subsequence(LCS). If you do not know LCS, please Google it.

Suppose there are two string, Xm={x1, x2, x3, …, xm} and Yn={y1, y2, y3, …, yn}. Zk={z1, z2, z3, …, zk} is the X`s, or Y`s, LCS. The elements in LCS need to be in the same order, but not continuous.

Then we could find three properties as follows:

• if x_m-1 == y_n-1, then z_k-1 = x_m-1 == y_n-1, and z_k-1 is a LCS of X_m-1 and Y_n-1;
• if x_m-1 != y_n-1, and z_k-1 != x_m-1, Z is the LCS of x_m-1 and Y;
• if x_m-1 != y_n-1, and z_k-1 != y_n-1, Z is the LCS of y_n-1 and X;

A recursive solution could be obtained as follows. Suppose c[m][n] denotes the length of the LSC of X[1:m] and Y[1:n].

          / 0, if i<0 and j<0; // case 1 
c[i][j] = | c[i-1][j-1]+1, if i, j >=0 and xi==yj; // case 2 
          \ max( c[i][j-1]m c[i-1][j] ), if i, j>=0 and xi!=yj; // case 3

After we execute the function above recursively, we could found the length of LCS at c[m][n]. If we want extract the LCS, we need to define anther matrix, D, to store the direction of how each state transited, and define 3 three directions.

• If D[i][j] holds direction 1, denoted as , we move next position at D[i-1][j-1];
  
• If D[i][j] holds direction 2, denoted as , we move next position at D[i-1][j];
  
• If D[i][j] holds direction 3, denoted as ,we move next position at D[i][j-1];

Those three directions correspond to the conditions in the case 2 and 3 in the function. A trace back function as followed could be used to print the LCS. Suppose b is one string, X is the direction map and (i, j) is the index of X.

胤祉如是，吾似胤祉

胤祉经办的古今图书集成可谓千秋功业，虽大悦龙心一时，但终究不会成为夺嫡的筹码！你全心全意的讨好康熙，但康熙真的会不考虑其他因素么？所以没底线的讨好没有什么前途，还是自丰羽翼，待帝位交接之时舍我其谁，这才是帝王之道！不然，你跟个乞食的狗有什么分别？史书上可是没有乞讨到帝位的！