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]);
   }
}

Efficient Way to Calculate Fibonacci Number

Problem: To give a O(logN) solution to Fibonacci function.

Solution: Solving Fibonacci with recursive function is easy. It is also not difficult to have an iterative solution with O(N) time complexity. Then can we do it even better? A solution based on matrix multiplication can help us achieve that.

• Basically we have a 2*2 matrix A = {[1,1], [1,0]} ({[first row], [second row]}). we can see that a[0][0] =1 = fibo(2). Then A*A = {[2,1],[1,1]} and a[0][0] = fibo(3) = 2. Basically we will have A^n = {[fibo(n+1), fibo(n)], [fibo(n), fibo(n-1)]}. 
• Then calculating Fibonacci number basically boils down to calculate the power of A. You may think this still takes O(N). However, we can calculate power efficiently (see this link) such that only O(logN) is needed.

More to mention: Actually there is a formula that generates Fibonacci numbers based on the golden ratio. However it evolves floating operations which may not as efficient as the matrix solution.

Find the Maximums in a Sliding Window

Problem: Given an array of integers and a window that has a size w, slide the window from the left side of the array to the right side, report the maximums in the sliding window during the sliding. For example, a[] = {3,1,5,2,1,4,-3, -2 , 6} and the w = 3. Then at the very beginning, we have [3,1,5] in the sliding window and then the maximum in the window is 5. If we slide the window one step towards the right, we have [1,5,2] in the sliding window and the maximum in the window is still 5. You need to get all these maximums. For this example, the maximum array is {5,5,5,4,4,4,6}.

Solution:  It is easy to know naive approaches will take O(wN), since after each sliding operation, we need O(w) time to find the maximum. To improve, you can use skip list. Basically, you have a sorted linked list to represent the integers in the window. Then you build skip list on top of it. For every slide operation, we need to do an insertion and a deletion. Therefore, the complexity will be O(Nlogw). However, a smarter solution from www.leetcode.com can achieve O(N). The details are as follow:

• Have a double-ended queue (which you can both manipulate the head and the tail. For initialization, add the indices of the first w integers to the queue. While adding indices, we must guarantee the integers to which those indices in the queue point keep a descending order. Therefore, if the index to be added points to an integer that is bigger than some integers to which some indices already in the queue point, we need to remove all "those" indices first.   For the example we showed previously, a[] = {3,1,5,2,1,4,-3, -2 , 6},  after adding the first integer, the state of the queue will be [0], which means a[0] is in the queue; After adding the second integer,   the state of the queue will be [0,1], which means a[0], a[1] are in the queue. Since a[0] > a[1], this guarantee a valid descending order. However, when adding the third integer, we need to pop put both "0" and "1", since a[2] is bigger than either a[0] or a[1]. Then after adding the third integer,   the state of the queue will be [2], which means only a[2] is in the queue.
• Since it is a sliding window, we also need to retire indices that point to the integers which are out of the window. We can do this by checking the indices in the queue and the current location of the window. If some index is out of bound, we need to remove them.
• The size of the queue will always not be bigger than w. For every integer in a[], it will be inserted in the queue and deleted from the queue for at most once. Therefore, the complexity is O(N). 

 You can find the code for this algorithm in  www.leetcode.com.

Find the Unique Element that Appears k Times in an Array

Problem: Let's first come with some special cases of this problem. Then we can generalize. Given an integer array, only one integer appears 2 times, all the other integers appears 3 times in the array. Find out that integer. For example, for a[] = [2,3,2,4,4,2,3,4], the output should be "3".

Solution: Definitely with hash table or sorting, the problem can be easily solved. What if those approaches are not allowed? Fortunately, we can still use bit operation to solve this problem.

• We need some counters to store the bits that just appear once, the bits that appear twice.
• If some bit appear three times, we need to reset those counters.
• Then at the end, the counter that stores the bits that appear twice will be the answer

Sample code is as follow:

def foo(list):
        # three counters which are used to store
        # the bits that appear 1 time, 2 times and 
        # three times, respectively
        ones = 0
        twos = 0
        threes = 0

        for x in list:
                # which bits had appeared for 3 times?
                # and later we need to reset those
                # bits if they also appear in the 
                # counter "ones" and "twos".
                threes = twos & x
                twos ^= (ones & x)
                twos &= ~threes
                ones ^= x
                ones &= (~threes & ~twos)

        # here we just need to return the counter 
        # "twos". If we need the unique element
        # that appears once (assuming the rest
        # all appear 3 times, just return "ones"
        # instead. 
        return twos

A more general problem: What if we change the problem. Now the problem is given an integer array, only one integer appears k times, all the other integers appears m times in the array (k<m). Find out that integer.

Solution: We can use similar strategy (as shown in above code snippet) to solve the problem.

• Basically, we need m counters (or a counter array). 
• We have counters[m] = counter[m-1] & x.
• counter[i] ^=  counter[i-1] & x and  counter[i] &= (~ counters[m] & ~counters[m-1] & ... &  ~counters[i+1] )

Find the Largest Container in a Histogram

Problem: Given a histogram, pick two bars in the histogram as the left and right sides of a container. X axis is consider as the bottom. Then we have a container which can hold water. Find the container that can hold the largest volume of water. The container must be placed horizontally (you can't rotate container).

Solution: We can still use DP to solve this problem in O(n). Basically, there are two factors decides the volume of the container: 1) the minimum of the two sides 2) how wide the container is. If the highest bars are just at the left and right end of the histogram, we know that by picking these two bars we can have the largest container. If the bars at the left and right end are not the two highest, we need to explore further to look at other combinations. Based on these observations, what we need is actually an increasing sequence from left to right and  also an increasing sequence from left to right. The details of the algorithm is as follow:

• First model the histogram as an array h[i]. For example, h[] = {3, 1, 4, 7, 5, 2, 6}. 
• Then find the two increasing sequences. The one from left to right is left[] = {3, 4, 7} and the one from right to left is right[] = {6, 7}.
• begin with the first elements in left[] and right[], calculate the volume of the container formed by these two bars, use max_v to store this volume (which is 3*5=15). 
• Then select the smaller one of the two bars, make one advancement in the array which the smaller bar is from. For our example, between left[0] and right[0], left[0] is the smaller one. Therefore we advance to left[1], which is "4". Then we calculate the volume of the container formed by left[1] and right[0]. The volume is 4*3=12, which is smaller than the previous value 15, so we just keep the old value. 
• Then we repeat the previous step, just advance the array which the smaller bar is from. We will get   left[2] and right[0]. The corresponding volume is 6*2 = 12, which is still smaller than 15.
• Then we need to advance in right[], we will find right[1] and left[2] refer to the same bar. Since at this time, both left[] and right[] have been exhausted, our algorithm just abort.
• One more thing, when two bars  left[i]  == right[j], we need to advance both arrays and inspect   left[i+1] and right[j+1] next.

Make Best Use of the Conference Room

Problem: Given a conference room and a number of presentations with start and end time ( e.g., [4, 9], [5, 10]), try to make an arrangement which allows the conference room to be used for maximum time. Overlapping presentations can't be in the same arrangement.

Solution: We can have a O(nlogn) solution by using DP.  The details are as follows:

• Sort the presentations by their end time. Thus we will have a sorted array end[N].   N is the number of the presentations.
• Have an array Max_arr[N].  Max_arr[i] stands for if we take end[i] as the close time for the conference room, the maximum time the room can be used. It is easy to know that  Max_arr[0] = the duration of the presentation that ends at  end[0]. We need to find out Max_arr[N-1].
• To calculate Max_arr[i], we first get the start time si of the presentation that ends at end[i]. Then we do binary search in end[0] ... end[i-1] for si. Basically we need to find a j such that  end[j] < si &&  end[j+1] > si. Therefore,  Max_arr[i] = max(Max_arr[i-1],  Max_arr[j] + end[i] -  si ).