Find the Minimun Vertex Cover for a Tree

Problem: Given a tree, find its minimum vertex cover. Wait, what is a vertex cover? Given a undirected graph G(V,E),  a vertex cover is a subset of V such that for any egde e in E, at least one of e's two endpoints should be in this subset (vertex cover).

Solution: The minimum vertex cover for a general graph is a NP-hard problem. However, for a tree, there is a linear solution. The idea here is to do DFS search plus post-order traversal. If we encounter a leaf node and the edge connecting this leaf node with its parent, we know in order to construct a vertex cover, we must include at least one of the node (the leaf node, or its parent). Here we can use a greedy approach. We can see selecting the leaf doesn't give us any extra benefit, while selecting the parent can give us some benefit, since the parent must be also connected to other nodes. By selecting the parent node, we can further "cover" some extra edges. With this strategy in mind, our algorithm is as follow:

• we do a DFS search. When a DFS call on a child node returns, we check if the child and the parent are both unselected. If yes, we select the parent node.
• After all the DFS finishes (we traverse the tree), those selected nodes form the minimum vertex cover. The cost is O(N).

The pseudo code is as follow:

void min_vertex_cover(TreeNode *root)
{
   if(isLeaf(root)) return; 

   for(int i=0; i<root->num_of_children; i++)
   { 
        min_vertex_cover(root->children[i]);

        if(!root->selected && !root->children[i]->selected)
               root->selected = true;
         
   }
}

Find the Greatest Common Divisor (GCD)

Problem: Given two non-negative integer a and b, find the greatest common divisor.

Solution: A very efficient algorithm is Euclid’s algorithm.  The main idea here is GCD(a, b) =  GCD(b, a mod b). Therefore, the code is straightforward:

int GCD(int a, int b)
{
   if(b==0) return a;
  
   return GCD(b, a mod b);
}

The Diameter of a Binary Tree

Problem: Given a binary tree, there is a path connecting any two nodes u,v in the tree. Among all the possible paths, the longest path is considered as the diameter of the binary tree. Find out this path.

Solution: We can use recursion to solve this problem. We need to be careful than this longest path can just reside in one of the sub-tree of the root. The code for this algorithm is as follow:

int height(TreeNode * root)
{
   if(!root) return 0;
   
   return 1+max(height(root->left), height(root->right));


int Diameter(TreeNode *root)
{
   if(!root) return 0;

   int h_left = height(root->left);
   int h_right = height(root->right);
   
   return max(1+h_left+h_right, max(Diameter(root->left), Diameter(root->right)));

}

Memorization might be used to avoid repeated calculation.

Construct All Possible Binary Trees with N Nodes

Problem: Enumerate all possible binary trees with n nodes. For example, if n=1, there just one tree; if n=2, there are two trees:

         *             or            *
           \                          /
            *                      *

Solution: The key is to understand what can uniquely denote a tree (or serialize a tree). A good way to serialize a tree is to record the pre-order traversal of a binary tree plus the nil virtual leaf information. If we denote an actual node as "1", the nil virtual leaf as "0". The sequence "10100" will stand for the following tree:


                  *          
               /      \                    
             nil       *
                      /    \
                   nil    nil

The way to decide the nil leaf is to check the children of a node. If a node is a leaf in the tree, it will have two nil virtual leaves, since a leaf won't have any children.  Similarly, we can know the sequence "11000" will stand for the following tree:


                  *          
                 /  \                
               *    nil
              /  \
           nil  nil

Therefore,  our target is to enumerate all possible sequences. There are several constraints on the sequences:

• For a n node tree, the length of the sequence will be 2n+1 with n "1" and n+1 "0".
• For any position i in the sequence s and i != 2n,  the number of "1" should always be no smaller than the number of "0" in the sub-sequence s[0, i].

The related code is as follow:

// rebuild the tree from a sequence such as "11000"
TreeNode * rebuild_tree(int s[], int n)
{

    TreeNode *root = create_node();
    stack<TreeNode *> stk;
    stk.push(root);
    
    for(int i=1; i<s.size(); i++)
    {
       if(s[i])
       {
         
         TreeNode *node = create_node();
         if(s[i-1]) 
         {
           stk.top()->left = node;           
         }
         else
         {
           stk.top()->right = node;
           stk.pop();          
         }
         stk.push(node);
       }
       else 
       {
         if(!s[i-1]) stk.pop();
       }
    
    }
    
    return root;

}

//print all possible trees
void output_all_possible_trees(int *seq, int n, int num1, int num0)
{
     
     if((num1 + num0) == 2*n)
     {
        seq[2*n] = 0;
        TreeNode *root = rebuild_tree(seq, 2*n+1);
        print_tree(root);
        return;
     }
        
    if(num1 >= num0 && num1 < n)
    {
        seq[num1+num0] = 1;
        output_all_possible_trees(seq, n, num1+1, num0); 
    }       
    
    if(num0 < num1 && num1 <=n)
    {
        seq[num1+num0] = 0;
        output_all_possible_trees(seq, n, num1, num0+1);  
    
    }
   
}

Something about Heapsort

Heapsort has two pleasant properties

1. an average and worst-case O(N*LogN) complexity
2. in place algorithm, no extra space is needed.

Heapsort has two steps:

1. first make a max heap (or min heap), this operation takes O(N)
2. pop the root of the heap, swap it with the last element in the heap (the last leaf), do heapify on the elements rangeing from 1 to N-1. Basically, we build a new max (min) heap on the elements rangeing from 1 to N-1
3. repeat the step 2

Strassen’s Method

Strassen’s method is a good  algorithm used in matrix multiplication. Naive approach usually takes O(N^3) to do matrix multiplication, while Strassen’s method costs O(N^2.8). Basically its recursion formula is like T(N) = 7*T(N/2) + N^2.

N Disks and K Pegs -- General Problem of Hanoi Tower.

Problem:  Most people must be aware of the Tower of Hanoi problem that has N disks and 3 pegs. Basic Hanoi problem can be solved either by iterative or recursive approach. However, here we discuss a more general problem. Given N disks and K pegs, also given a start state (e.g., the peg that a particular disc is on) and an end state, try to find the optimal solution (i.e., minimum moves) to move the disks such that we can go from the start state to the end state. Here we still need to follow the similar rule in Hanoi: larger disk should be below smaller disk.

For example, assume we have 4 pegs, and the start state is: pegs[1] = [3,2] (which means disk 3 and disk 2 are on peg 1), pegs[2] = 4, pegs[3] = 1, pegs[4] = []; the end state is pegs[1] = [1], pegs[2] = [3], pegs[3] = [],  pegs[4] = [4,2]. The optimal solution is 2->4, 1-> 4, 1->2, 3->1 ( here "2->4" means move the top of peg 2 to peg 4), totally 4 moves.

Solution: if the N and K are not too large, we can use DFS to solve this problem. Basically, the total space will be K^N, but we are able to prune out some unfeasible paths.

• Basically, we try all the possible moves in a DFS way. If we reach the end state, we stop and return. Meanwhile, we need to remember how many moves it takes to the end and store it in current_min.
• If from the start state, we have already made current_min moves, we don't need to go further, since we can't get a result better than  current_min.
• We need to have a hash table to remember the state we have seen before. If we found we revisited a state, try to compare the moves that we have made now and the previous number of moves to reach that state. If now we take less move to revisit the state, we go forward. Otherwise, we can just return.

The pseudo code is as follow:

// the counter for the number of moves from the 
// start state 
int cnt = 0
// the current minimum moves to the end state
int current_min = INT_MAX
// a hash table to remember the visited states
hash_table ht;

void dfs()
{
  if(cnt >= current_min) return;
  // get the current state of disks   
  string stat = get_state()
 
  // if stat is not in hashtable
  if(!ht.has_key(stat))
  {
    ht[stat] = cnt;  
  }
  else
  {
     // if we take more moves to 
     // visit this state, we just
     // return
     if(ht[stat] <= cnt) return;
     ht[stat] = cnt;
  }   

  // if we reach the end state
  if(stat == end_state)
  {
     if(current_min > cnt)
     current_min = cnt;
     return;
  }
  
  for(int i=0; i<K; i++)
  {
     current_disk = peg[i].top();
     // iterate all the possible moves
     // current_disk can make
     for move in possible_move_set
     {
        make the move;
        cnt++;
        dfs();
        rewind the move;
        cnt--;
     }
  }

}

String Permutation without Duplication

Problem: This is a classic problem. Given a string "abc",  you need to output all the permutations. They are "abc", "acb", "bac", "bca", "cab" and "cba".  While for input that contains duplicate characters, you need to output all unique permutations. For example, input is "abb", then output should be "abb", "bab" and "bba".

Solution: For strings without duplicate characters, the solution is not difficult. To avoid duplication, definitely you can use a hashtable to memorize the permutations that you had outputted.  Considering that hashtable may cost a lot of space, some other solutions are desired. However, many solutions on the web actually are incorrect. Here gives a correct solution by using a bit vector (or counting array).

• The key thing is that if now I am gonna swap a character c to position i, I must guarantee previously there is no c that has been swapped to  position i. This is the important constraint to avoid duplicate.
• Then we can use an array to track this. If the string only contains characters that range from 'a' to 'z', then we only need an array of the length 26. The code is as follow:

void permutation(string &s, int idx)
{

     if(idx == s.size())
    {
        cout << s << endl;
        return;
    }

    char a[26] = {0};

    for(int i = idx; i < s.size(); i++)
    {
        
        if(a[s[i] - 'a'] == 1) continue;

        a[s[i] - 'a'] = 1;

        swap(s[idx], s[i]);
        permutation(s, idx+1);
        swap(s[idx], s[i]);
   }
}

Output a set's all sub sets

Problem: Given a set, output all its subsets. For example, for set (a,b,c), we need to output (), (a), (b), (c), (a,b), (a, c), (b,c), (a,b,c).

Solution: iterative approach is not difficult. Here give a recursive approach:

void _print(const vector<int>& set)
{
    i; i<< set[i] << " ";
    cout << endl;
}


void print_set(const vector <int>&set, int i, vector<int>& output)
{
   if(i >= set.size()) _print(output);
   else {
     output.push_back(set[i]);
     print_set(set, i+1, output);
　　　// code to handle duplicates
     int tmp = output.back();
     output.pop_back();
     
     if(output.size()>0 && tmp== output.back()) return;
          
     print_set(set, i+1, output);
   }
}

int main()
{
    vector<int> set,output;
    set.push_back(1);
    set.push_back(2);
    set.push_back(3);
    set.push_back(4);

    print_set(set, 0, output);
}

Find the Kth Smallest Element of Two Sorted Arrays

Problem: given two sorted arrays, find the Kth smallest element.

Solution: if we have two pointer scanning from the heads of two arrays, we can have an O(K) algorithm. Here we give the main idea of an O(logm + logn) algorithm, where m and n are the length of the two arrays, respectively.

1. We pick the ith and jth elements from two arrays. We make i+j = K-1. Then if Ai > Bj && Ai < Bj+1, Ai is the Kth smallest element. The other way is the same (Ai < Bj).
2. If the previous condition doesn't hold, which means Ai < Bj && Ai < Bj+1. Then the Kth smallest element cannot be within A0 to Ai and Bj+1 to Bn-1. Then we remove them and only need to look for the K-i-1th smallest element in the sub-arrays left.

Find the Median of Two Sorted Arrays

Problem: given two sorted arrays, find the median.

Solution: Assume the length of the two arrays are m and n. When m+n is even, the median is the average of two numbers. The neat solution has a time complexity of O(log(m+n)). Basically, we need to leverage binary search. The details of this algorithm is very complex due to many corner cases to handle. The following just gives the main idea.

1. get the median of two arrays Ai and Bj, where i = m/2 and j = n/2. If  Ai <= Bj, the median will be between Ai and Bj.
2. therefore, we can discard A0 to Ai-1 and Bj+1 to Bn-1. However, we cannot do this in a naive way. To reduce to an equivalent sub-problem, we need to discard the same number of elements from each array. Then we keep comparing the middle elements of the sub-arrays. To discard the same number of elements, we just need to get Min(i, n-j-1).

Besides, we can also use the techniques in Find the Kth Smallest Element of Two Sorted Arrays.

More: a more general problem is to find the median for K sorted arrays. There are two ways:

1. Guess a number, search each array to see how many elements are smaller than this number. Then we can have a total number. If this total is smaller than half, we guess a bigger number; otherwise, we guess a smaller number. Try to repeat binary search until our goal is met.
2. The second approach is to first find the medians of all the arrays. Then we can know the bounds of these medians (low_m, high_m). For each array, throw the elements that are out of the bounds. Make sure the elements thrown at the two ends of the array should be the same number. Then repeat until our goal is met.

Get the Kth Permutation

Problem: Given an array of N numbers {1,2...N},  get the Kth permutation. For example, when N = 3, the first permutation is "123", the second is "132", the sixth is "321".

Solution: With STL, we can use next_permutation(). Just call it K-1 times. However, next_permutation()'s complexity is not constant. A better way is to use recursion:

String Find(string a, int k)
{
   if(len(a)==1 or k==0) return a;

   int N = len(a);
   
   int i = k/factorial(N-1);
   int j = k%factorial(N-1);

   return a[i] + find(a.substring(0,i) + a.substring(i+1), j);
}

Segment Tree and Interval Tree

To build a Segment Tree, first sort all the end points of the segments, than adding -infinity and +infinity. For n segments, we then partition (-infinity, +infinity) into 2n+1 segments. These 2n+1 segments serve as elementary intervals. From them (considering them as leafs),  we can build a balanced binary tree. Then we add the n segments into the tree. Each node represents an interval. Non-leaf nodes represent the interval which is the union of their children. When adding a segment, we store the information of that segment in all nodes where the nodes' intervals are within the segment's interval. Besides, the nodes' parents' interval are not within the segment's interval.

• building cost is O(nlogn), space cost is O(nlogn), the cost to find all segments that contain a point (stabbing query) is O(k+logn)
• can also solve box overlap problem, Klee's measure problem.
• For multi-level segment tree, first build a base segment tree on one axis. Then build small segment tree on each node of the base tree, only for the segments stored on that node.
• For more details, please check http://www.cnblogs.com/TenosDoIt/p/3453089.html (in Chinese).

To build an Interval Tree, it is a little bit similar. First sort all the end points of the intervals and find the median points. Every node in the interval tree is associated with a point. And the node contains all the intervals that cover the point. The left child (sub-tree) of the node contains all the intervals whose upper bounds are smaller than the node's point. Similarly, we can define the right child.

• building cost is O(nlogn), space cost is O(n), the cost to find all intervals that overlap with an interval   (range query) is O(k+logn). 
• The result is a ternary tree with each node storing:
  • A center point
  • A pointer to another node containing all intervals completely to the left of the center point
  • A pointer to another node containing all intervals completely to the right of the center point
  • All intervals overlapping the center point sorted by their beginning point
  • All intervals overlapping the center point sorted by their ending point
• If we need to do a range query with interval tree, see we want to find the set of r that overlap with interval q. We first to sort all the start/end points of intervals, then find those have either start/end inside q. Second, we need select one point in q, do the query on the interval tree to find all the intervals that have the point. At the end, we need to merge results and do the dedup.

See Also: Klee's measure problem

Print all the combination from a candidate set that sum to a target value

Problem: Given a target set of integers (may contain negative integers) and a target value, print all the combinations that sum to the target value. Each element can only be used once in a combination. For the same combination, only print once.

• Example:  candidate set [-1, 3, 2, 1, 5], target value 4. Then we can have 1+3, -1+2+3

Solution: Recursion is used to solve this problem. Also first sort the candidate set.

• Assume we have a prev_sum (the sum of the previous integers we had added up) and current integer we want to add, if prev_sum + current integer > target value, we return.
• if prev_sum + current integer = target value, we print out the combination and also return. No need to explore further, since the candidate set is sorted.
• if prev_sum + current integer < target value, we take the current integer, update prev_sum, and also update an array that is used to track the combination, then we make a recursive function call
• an array, int index[] is used to track the integers we had used.  The advantage of this array is simplicity. Definitely we can use STL vectors.
• If the target value is negative, taking the above approach naively will have some problem (see chunjie's comment below). There are different ways to handle this case. One way used below is to convert the target value into positive and also convert the whole set of integers by multiplying with a "-1".

The related code is as follow:

void print_comb(int index[], int n, vector<int> set, int negative)
{
   for(int i =0; i<=n; i++)
     cout << (negative * set[index[i]]) << ((i<n)?'+':' ');
     cout << endl;
}

//assume a sorted list
void _print_all_combine_n(int target, int negative, int n_prev, int index[], vector<int> set, int pos, int n)
{

   for(int i = pos; i < set.size(); i++)
   {
     if(n_prev + set[i] == target) 
      {
         index[n] = i;
         print_comb(index, n, set, negative);
         return;
      }
      
      // we don't need to look at later cases, since they are not possible
      if(n_prev + set[i] > target)        
            return;

      // skip duplicate numbers before advancing, since we only use each number once
      int m = i+1;
      while(set[m] == set[i] && m < set.size())
           m++;
      i = m-1;

      if(n_prev + set[i] < target)
      {
         index[n] = i;
         print_all_combine_n(target, n_prev+set[i], index, set, i+1, n+1);

      }

   }

}

//assume a sorted list
void print_all_combine_n(int target)
{

   int index[10000];
   index[0] = 0;
   vector<int> set(myints, myints + sizeof(myints) / sizeof(int) );
   
   int negative = 1;

   if(target < 0) 
   {
      for(int i=0; i<set.size(); i++)
         set[i] = (-1)*set[i];

      negative = -1;
   }

   sort(set.begin(), set.end());

   print_all_combine_n(target * negative, negative, 0, index, set, 0, 0);
}

int main()
{

   int myints[] = {10, 1, 2, 7, 6, 1, 5, -3};

   
   print_all_combine_n(8);

}

NXN Boggle Game

Problem: Solve the boggle game with 5X5 square. Each cell in the square is a letter (from A-Z).  The interior cells can have 8 directions (including diagonal)  as next move, the border cells have 5 or 3 directions. Start from any cell, just go with the possible directions, you will have a path. The path can only contain a cell once (you can't visit the cell you had visited). If the path represents a valid English word, output it:

Solution: Use recursion to solve this problem. Also a trie is used.

• Globally, we have a hash table for all valid words (paths) and a trie to store the dictionary
• Start from each cell, we have current_word (the path we had visited), all the visited paths (can be implemented as a hash table or a matrix).
• Start from that cell, we append the cell to the current_word. If current_word is not a visited path, we update visited path, otherwise we return.  If the path is over the maximum length (N*N), we return.
• Then check if current_word is in trie (we can have a recursive checking method), if not, we return. The use of trie here can save us time from exploring some invalid path (not a word). 
• If current_word is a valid word, we update the global hash table.
• Then we explore the all possible directions and make those recursive calls.
• For each cell (as the starting cell), we repeat the above process.