Sparse Matrix Transposition

Sparse matrix is very useful in some scientific computing, such as calculating the similarity between two web pages or clustering multiple web pages. The vector representation tends to be sparse.

There are many ways to represent sparse matrix, one of them is called COO, coordinate list which is list of tuples storing row index, column index and its value; See wiki page for COO: https://en.wikipedia.org/wiki/Sparse_matrix#Coordinate_list_.28COO.29

Now we need to transpose a sparse matrix with COO list to another COO list. Below is the code with comments containing the detailed explanation of the algorithm.

Sparse Matrix Multiplication

The sparse matrix multiplication algorithm can be seen here:
http://mathforum.org/library/drmath/view/51903.html

and at stackoverflow site too
http://stackoverflow.com/questions/15693584/fast-sparse-matrix-multiplication

The key to the linear algorithm is to find all non-zero entries in one the sparse matrix and then loop through them, update the impacted entries in the final result matrix.

Here is the code: 

palindrome permutation

This is a leetcode problem.

Write an efficient function that checks whether any permutation of an input string is a palindrome. Examples:
 "civic" should return true
 "ivicc" should return true
 "civil" should return false
 "livci" should return false

In a palindrome string, all characters appears symmetrically, except the middle character if the string length is odd. The key observation is that to count the appearances of each characters in the string, if all counts are even, or there is only one characters appears odd times, then the word is palindrome. And we use an array to store the counts for each character in the string. This kind of simple counting array is more space effective than using hash map to store character and its count. Here is the code.

The beauty of recursion

There are several programming models or techniques are powerful, yet simple and beautiful to solve problems. Recursion is one of them, others include dynamic programming, sliding windows, binary search.

Today I use recursion to solve two problems are permutation and combination of list of characters. For example, permutation of a, b, c are abc, acb, bac, bca, cab, cba. combinations are a, ab, abc, ac, b, bc, c.

Let's talk about permutation first, to generate them, image we have 3 balls in a bag with labels of a, b, c, we first one ball of 3 in the bag, then another ball out of 2 balls left, then last ball left in the bag. When there is no balls left in the bag, we are done, which is our recursion termination condition. So how we make sure we don't take the same ball twice in a permutation, we can mark it and unmark it once a permutation is generated. Here is the code:


Now let's talk about combination, which is a bit complicated than permutation. For the first position, we have possibilities of a, b, or c. And if we have a in the first position, we can have b or c; if we have b in the first position, we can only have c followed after; if we have c, nothing can follow. And every time we put a character in the string, we have one new combination. So we have
a
ab
abc
-->recursion terminated
remove c => ab
-->recursion terminated
remove c => a
ac
-->recursion terminated
remove c => a
-->recursion terminated
remove a=> ''
b
bc
c

Here is the code:

find all possible words based on phone numbers

This is a classic code problem:

http://www.geeksforgeeks.org/find-possible-words-phone-digits/

This can be done beautifully in a recursion approach. The key here is to loop through all digits in the phone number from left to right, set the corresponding char in the word based on the phone keyboard, the recursion will terminate when the last digit is passed.


Another approach is to do it iterativelly. The key here is to find a way to calculate next word from a current word. for example, if the current word is ADG, then next word is ADH, next after that is ADI, AEG.

Products of all numbers in the array

This is google coding interview question:

Given an array of numbers, replace each number with the

product of all the numbers in the array except the number itself *without* using division

https://www.glassdoor.com/Interview/Given-an-array-of-numbers-replace-each-number-with-the-product-of-all-the-numbers-in-the-array-except-the-number-itself-w-QTN_9132.htm

The key to this solution is construct the accessory arrays which assists the solution. Here are the code 


Recursive way


Iterative way:

Minimum Size Subarray Sum

This is a leetCode problem: http://www.programcreek.com/2014/05/leetcode-minimum-size-subarray-sum-java/

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length of 2 under the problem constraint.

We can solve this by a sliding window, aka inch worm algorithm. Essentially we grow this sliding window to the right if the sum is smaller than the s, once sum >= s, then we update the minimal length of the window and then start to shrink the window from the left until sum < s. Here is the code:

minimum path sum of a number triangle

This is from leetcode: http://www.programcreek.com/2013/01/leetcode-triangle-java/

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). 

The key observation here is that viewing this triangle as a tree, for any given subtree, the minimum path sum is the minimum of all of its subtrees plus the number at the root. At the leaf level, the minimum path sum is the value at the leaves.

If we use dynamic programming, keep track of the minimum path sum at lower level, and then going up to calculate the min path sum at higher level.




Further observation of the dynamic programming solution is that we don't need a 2D table, in stead we can use an array and keep on updating it when going up.

power(a, n) in iteration way

Given a, n, calculate a^n in non-recursive way.

First of all, let's write down how we solve it in recursive fashion.

Here a and n are all integers and n>=0, and assume the result is in the range of integers.

public int power(int a, int n) {
   if(n==0)
      return 1;
    if(n==1)
       return a;
 
    int l = power(a, n/2);
    int result = l*l;
    if(n%2==1)
        result *=a;
    return result;
}


Let's solve it in iterative way. For example, n = 4, we starts with a, calculate a^2 by a*a, then a^4 by a^2 multiples itself and return that as final result. try n = 9, we starts with a, a^2, a^4, a^8, then return a^8 * a as final result. Let's write down the formula:

a^9 = a^(0b1001) = a^8 * a.
a^4 = a^(0b100)   =  a^4
a^10=a^(0b1010) = a^8 * a^2

Essentially we represent n as binary, go through this binary number from lower bits to higher bits, then if the i-th bit is 1, then a^i is part of result.

//n>=0
public int power(int a, int n){
    if(n==0)
        return 1;
    int result = 1;
    while(n>0){
       if(n&1==1)//test the least bit
            result = result * a;
       //move to higher bit at position i
       n = n>>1;
       //calculate the a^i
      a = a * a;
   }
 return result;
}

Longest Continuous Ones of a String contains 0 or 1 - inch worm algorithm

Given a string consisted of only 0 or 1, and a number N.

We have N times to flip 0 to 1 in array. Find the longest continuous 1 after we flipped the N zero elements. Rotation is allowed.

For example, 100100111000, n=2, the best flip is 100111111000, return 6

10001101101, n=2, the best flip is 10001111111, return 8(rotation is allowed)

The following algorithm is more like a inch worm walking on a line, it tries to go forward as it can, then shrink from the tail, then move forward again.

/**
     * we first concatenate string to itself
     *
     * then use a sliding window, keep track of number of 0s in the window
     * grow the right side of window if not exceed max 0s allowed
     * otherwise shrink the left side to reduce the 0s
     *
     * the algorithm stops when left side reach the length of original string
     *
     */
    public static int maxContinuous1sWithRotation(String s, int maxFlips){
        int p1=0, p2=0, len = s.length(), num0=0, max=0;
        while(p1<len && p2-p1<len){
            if(s.charAt(p2%len) == '0'){
                num0++;
            }
           
            /*
             * if num0 reaches maxFlips+1
             * we need to shrink the sliding window from left
             * until we reaches a 0 and reduce the counter
             */
            if(num0 > maxFlips){               
                while(p1<len && s.charAt(p1)=='1')
                    p1++;
                p1++; num0--;
            }
           
            /*
             * we keep on growing the sliding window
             * to the right and update the max
             */
            p2++;
            max = Math.max(max, p2-p1);       
        }
        return max;
    }

Longest palindrome starting from left side

This problem is from Li Peng's blog: http://www.allenlipeng47.com/PersonalPage/index/view/202/nkey

Given a string, find the longest length of palindrome starting from the left.
For example:
abaeab, the longest from left is aba, so return 3.
abcbaef, the longest from left is abcba, so return 5.
ababa, the longest from left is ababa, so return 5.

One solution is to start a pointer p from right,  check if substring between index 0 and p is palindrome, if found, return it substring, if not, move pointer to the left and continue search.
Time complexity is O(n^2), since p goes from n-1 to 0, each palindrome check takes about n.

A linear solution is using KMP algorithm. First of all, we generate the reverse string of the original string:

abaeab -> baeaba

Now we are going to do pattern match between these two strings, we treat original string as the pattern, the reverse string as the text to be matched, however the difference here is that when we reach the end of reverse string, we find the long palindrome!

Failure table for string abaeba
  a  b  a  e  b  a
 -1 0  0  0  0  0

First try: failed and move to next
 baeaba
 abaeab

baeaba: failed and move to next
  abaeab

......

baeaba
      abaeab

Found!

We are going to use KMP algorithm to help us to do the pattern matching so our algorithm can be run in linear time.

The first operation is to build the KMP failure function.

public static int[] buildTable(char[] digits){
        int[] table = new int[digits.length+1];
        table[0] = -1;
        int i = 1, j = -1;
        while(i<digits.length){
            while(j>=0 && digits[i]!=digits[j])
                j = table[j];
            i++;
            j++;
            table[i] = j;       
        }
        return table;
    }

Once we have the failure function, we can skip some characters in the pattern based on the failure function, and the while loop will exit when we reach the end of the text itself.

public static String longestPalindromeFromLeft(String s){
        char[] pattern = s.toCharArray();
        char[] text = new StringBuilder(s).reverse().toString().toCharArray();
       
        int[] table = buildTable(pattern);
       
        int j = 0, i = 0;
        while(i<text.length){
            while(j>=0  && text[i]!=pattern[j])
                j = table[j];
            i++;
            j++;
        }
       
        return s.substring(0, j);
    }
   

find insert position in a sorted list

One of the JDK's array utility function binary is to not only find the target, but also return the insertion position if the target is not found.
For its javadoc, look at this link:
http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch%28int[],%20int%29

Here is the two implementation.

The first solution is to narrow down the search window to size of 2. And second solution is to narrow down search window to size of 1.

    public static int findInsertPos(int[] sorted, int target){
        int left = 0, right = sorted.length -1 ;
        while(right - left > 1){
            int mid = (right + left) >>> 1;
            if(sorted[mid]<target)
                left = mid + 1 ;
            else
                right = mid;
        }
       
        if(sorted[left] == target)
            return left;
        if(sorted[right] == target)
            return right;
        if(sorted[left] > target)
            return left;
        return sorted[right]>target?right:right+1;
    }
   
    public static int findInsertPos2(int[] sorted, int target){
        int left = 0, right = sorted.length ;
        while(right > left){
            int mid = (right + left) >>> 1;
            if(sorted[mid] == target)
                return mid;
            if(sorted[mid]<target)
                left = mid + 1 ;
            else
                right = mid;
        }
        if(left == sorted.length || sorted[left] >= target)
            return left;
        return left+1;
    }

tertiary search - find left open and left close in a sorted list

In a typical binary search, we search the half based on the comparison result between middle point and target until there is nothing to search, we return the index if middle number is equal to target, if not found, we return -1.

In proximity search which tries to find the number with smallest index which is larger or equal to target, we use ternary search, which narrows down the search range to two numbers.

Here is the algorithm:

/*
     * find left-most number which is larger or equal to target
     */
    public static int leftOpen(int[] sorted, int target){
        int left = 0, right = sorted.length -1 ;
        while(right - left > 1){
            int mid = (right + left) >>> 1;
            if(sorted[mid]<target)
                left = mid + 1 ;
            else
                right = mid;
        }
       
        return sorted[left]>=target?left:right;
    }

    /*
     * find left-most number which is larger than target
     */
    public static int leftClose(int[] sorted, int target){
        int left = 0, right = sorted.length -1 ;
        while(right - left > 1){
            int mid = (right + left) >>> 1;
            if(sorted[mid]<=target)
                left = mid + 1;
            else
                right = mid;
        }
       
        return sorted[left]>target?left:right;
    }

max gap problem and pigoen hole principle

Source: http://allenlipeng47.com/PersonalPage/index/view/199/nkey

Given a unsorted array with n elements. How can we find the largest gap between consecutive numbers of sorted version in O(n)?
For example, we have a unsorted array
9 19 13 12 33 41 22
the sorted version is
9 12 13 19 22 33 41
the output of the algorithm should be 33-22 = 11
  
One way to do it is to using counting sort or radix sort if the integer range is known and small compared to size of array. 

Another way to do it is to using pigeon hole principle, divide up the k numbers to k+2 equal-size buckets, so at least there will be some empty buckets, and we know the max gap will be larger than the size of buckets and coming from the difference between the min and max of each bucket.

Here is the link to the algorithm:
maximum-gap-program

 /*
     * maximum gap algorithm using pigeon hole principle
     * without losing generality, assume the numbers are integers
     *
     * note the interval is left inclusive and right exclusive
     *    
        if the numbers can not be evenly divided up between min and max
         then we may need one extra interval.
         and pigeon hole principle still holds
    */
    public static int maxGap(int[] nums){
        int min = nums[0], max = nums[0];
        for(int k : nums){
            min = Math.min(min, k);
            max = Math.max(max, k);
        }
       
        int size = nums.length;
        int interval = (max-min)/(size-1);
        /*
         * we will create either n-1 or n pigeon holes
         */
        int count = size-1;
        if(interval*count+ min <=max)
            count++;
       
        Integer[] mins = new Integer[count];
        Integer[] maxs = new Integer[count];
        mins[0] = min; maxs[count-1] = max;
       
        for(int k : nums){
            int index = (k-min)/interval;
            mins[index] = mins[index] == null ? k : (Math.min(k, mins[index]));
            maxs[index] = maxs[index] == null ? k : (Math.max(k, maxs[index]));
        }
       
        int maxGap = maxs[0] - mins[0];
        int pre = maxs[0];
        for(int i = 1; i<count; i++){
            if(mins[i]==null)
                continue;
            maxGap = Math.max(mins[i] - pre, maxGap);
            maxGap = Math.max(maxs[i]-mins[i], maxGap);
            pre = maxs[i];
        }
       
        return maxGap;
    }

minimum consecutive sub-string of S containing T

The problem is described from my friend Peng Li's blog:
http://allenlipeng47.com/PersonalPage/index/view/198/nkey

Given a random string S and another string T with unique elements,. find the minimum consecutive sub-string of S such that it contains all the elements in T
example:
S='adobecodebanc'
T='abc'
answer='banc"

We need a sliding window algorithm to solve this problem. The window data structure needs to tell us few things: 1)  are all characters in T found in the window? 2) how many times of each character found in the window appears so far? 3) if all characters are found in the window, can we shrink the window? 

To answer question 1 and 2, we can maintain a hashMap, its key is the character found, the value is the numbers of times the character appears in the window. 
To answer question 3, we need to maintain a data structure which can 1) represent the sliding window; 2) shrink the window if the number of first character in the window is more than once. We will use a Queue to do that, a double-ended queue actually in the below implementation. 

public static String miniSubstr(String s, String t){
        Deque<Item> q = new ArrayDeque<Item>();
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        int p=0, min=Integer.MAX_VALUE;
        String result = null;   
        while(p<s.length()){
            char c = s.charAt(p);
            if(t.indexOf(c)>-1){
                //update the sliding window
                q.add(new Item(c, p));   
                //update the counter map
                if(!map.containsKey(c))
                    map.put(c, 1);
                else
                    map.put(c, map.get(c)+1);   
                //shrink the sliding window if char in the head of q appears more than once
                while(true){
                    Item item = q.peek();
                    Integer num = map.get(item.c);
                    if(num>1){
                        q.removeFirst();
                        map.put(item.c, num-1);
                    }else
                        break;
                }
            }
           
            //when we find all characters, then we update result
            if(map.size() == t.length()){
                int current =  q.peekLast().p - q.peekFirst().p;
                if(current<min){
                    min = current;
                    result = s.substring(q.peekFirst().p, q.peekLast().p+1);
                }
            }
           
            p++;
        }       
        return result;
    }
   
    static class Item{
        char c;
        int p;
        Item(char c, int t){
            this.c = c; this.p = t;
        }
    }

Permutation sequence

This is from leetcode:

The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the kth permutation sequence. (Note: Given n will be between 1 and 9 inclusive.)

The best way to approach the problem is to divide and conquer:
let's start with numbers 1, 2, 3, 4, and we can divide the sequences into 4 groups each starts with 1, 2, 3, 4, the number of sequences in each are 3!,  k/3! will decide which group the kth sequence belongs to, saying k=9, k/3! = 1, so kth sequence belongs with group starts with 2.

now we have 1,3,4 and we should look for k%3!=9%6=3th sequence in this set

And we can use recursion to do divide and conquer work.

public static List<Integer> permutationByRank(int n, int k){
       //prepare the set
       List<Integer> list = new ArrayList<Integer>();
        for(int i=1; i<=n; i++)
            list.add(i);
        //calculate the group size
        int size = factor(n-1);
        return permuByRankUtil(list, k-1, size);
    }
   
    /*
     * here k starts at 0 to n!-1 for easy computing purpose
     */
    public static List<Integer> permuByRankUtil(List<Integer> nums, int k, int f){
        int size = nums.size();
        //base case
        if(size==1)
            return nums;
        else{
            //decide group index
            int index = k/f;
            int first = nums.remove(index);
            List<Integer> re = permuByRankUtil(nums, k%f, f/(size-1));
            re.add(0, first);
            return re;
        }
    }

find all palidrome partitions for a string

This problem is from LeetCode:
http://www.programcreek.com/2013/03/leetcode-palindrome-partitioning-java/

      Given a string s, partition s such that every substring of the partition is a palindrome.
    
     we can think all possible palindromic substrings form a graph.
     each palindromic substring is the node
     two nodes connect each other when one's starting index is equal to
     the other ending index. There are multiple roots in this graph but only one leaf.     
     roots are the palidrome substrings starting at index 0
     leaf are the node with starting index equals to string's length
     a path from root to leaf is one palindrome partition
    
     
    public static void findAllPali(String s){
        dfs(s, 0, new ArrayList<String>());
    }
 
  public static void dfs(String s, int start, List<String> current){
        //reach leaf level, then we find the palidrome partition
        if(start==s.length()){
            System.out.println(current);
            return;
        }
        for(int j=start+1;j<=s.length();j++){
            //depth first search
            //find one node
            if(isPali(s, start, j-1)){
                /*
                 * before we go down this branch
                 * we make copy of the path
                 * then pass it down
                 */
                List<String> copy = new ArrayList<String>(current);
                copy.add(s.substring(start, j));
                dfs(s, j, copy);
            }
        }
    }
   
   
    public static boolean isPali(String s, int i, int j){
        while(i<j){
            if(s.charAt(i)!=s.charAt(j))
                return false;
            i++;j--;
        }
        return true;
    }

all permutations of list of characters

Given a list of unique characters, generate or print out all permutations of characters.
For example:
input: [a, b, c]
output:
[a, b, c]
[b, a, c]
[c, b, a]
[a, c, b]
[b, c, a]
[c, a, b]

One of the permutation algorithm is done by swapping,
We have a list of permutations, which initially contains the input characters only.
Then we have two loops, outer loop (i) goes through index 0 to len-2, inner loop (j) goes from index i+1 to len-1, and for each current permutation, we generate one new by swap characters at i and j.


public static void permuIteratively(char[] chars){
        assert chars!=null && chars.length>0;
       
        List<char[]> result = new ArrayList<char[]>();
        result.add(chars);
        int len = chars.length;
       
        /*
         * the algorithm is doing swapping with two loops
         * i: 0..len-2
         *   j: i+1..len-1
         *    for each string in the result list
         *     swap characters at i and j
         *     add swapping result string to the result
         *    
         * since we can't change the list which iterating through list
         * so we have to make a temp copy of the result and add swapping result
         * into temp list   
         *
         */
       
        for(int i=0; i<len-1; i++){
            //make a copy of result
            List<char[]> temp = new ArrayList<char[]>(result);
            for(int j=i+1;j<len;j++){   
                //loop through result and swap i and j
                for(char[] item : result){
                    char[] copy = Arrays.copyOf(item, item.length);
                    char tempC = copy[i];
                    copy[i] = copy[j];
                    copy[j] = tempC;
                    temp.add(copy);
                }           
            }
            result = temp;
        }
       
        for(char[] i : result){
            System.out.println(Arrays.toString(i));
        }
    }


Once we find a way do it in iteratively, it is not difficutlt to switch to recursive way .

public static void permu(char[] chars){
        List<char[]> l = new ArrayList<char[]>();
        l.add(chars);
        permuRec(chars, 0, l);
    }
    public static void permuRec(char[] chars, int index, List<char[]> current){
        /*
         * termination condition
         */
        if(index==chars.length-1){
            for(char[] i : current){
                System.out.println(Arrays.toString(i));
            }
            return;
        }
       
        //make a copy of result
        List<char[]> temp = new ArrayList<char[]>(current);
        //then we grow the result by swapping
        for(int j=index+1;j<chars.length;j++){
            for(char[] item : current){
                char[] copy = Arrays.copyOf(item, item.length);
                char tempC = copy[index];
                copy[index] = copy[j];
                copy[j] = tempC;
                temp.add(copy);
            }
        }
        //continue on next index
        permuRec(chars, index+1, temp);
    }
   

Another way to do it is to by reduction. Basically we divide and conquer,  find the permutations for substring start at i+1 first, then insert the character at i into all positions for each permutation from the subpromblem.

/**
     * we solve this by reduction, for string s,
     * first find the permutation of its substring from i+1
     * then for each permutation, insert the character at i
     * into all positions
     *
     * @param chars
     */
    public static void permutationByDP(char[] chars){
        System.out.println(permutationByReduRec(chars, 0));
    }
   
    public static List<List<Character>> permutationByReduRec(char[] chars, int index){
        /*
         * permutations are represented by list of characters
         */
        List<List<Character>> result = new ArrayList<List<Character>>();
        if(index == chars.length-1){
            /**
             * base case is the string only has one character
             */
            List<Character> list = new ArrayList<Character>();
            list.add(chars[index]);           
            result.add(list);
        }
        else{
            /*
             * we build the permutation by its substring index+1 first
             */
            List<List<Character>> list = permutationByReduRec(chars, index+1);
            char insert = chars[index];
            for(List<Character> item : list){
                /*
                 * then we insert char at index to all possible positions in the item
                 */
                for(int i=0; i<=item.size(); i++){
                    List<Character> copy = new ArrayList<Character>(item);
                    copy.add(i, insert);
                    result.add(copy);
                }

            }
        }
        return result;       
    }
   

generate super set of characters

Given a set of unique characters, generate its superset. example: a, b, c, its superset are:

[[], [c], [b], [c, b], [a], [c, a], [b, a], [c, b, a]]

There are two ways to solve this problem,

one is by recursion, basically we generate a set for a, then append b to each element, which itself is a set too, in the set, adding back to the set; then append c to each element in the new set and adding back to the set.
{}
{}, {a}
{b}, {a,b}, {}, {a}
{b,c{,{a,b,c},{c},{a,c},{b},{a,b},{},{a}

private static List<List<Character>> getSuperSetRec(char[] chars, int index){
        if(index == chars.length){
            List<List<Character>> list = new ArrayList<List<Character>>();
            List<Character> l = Collections.emptyList();
            list.add(l);
            return list;
        }
        else{
            List<List<Character>> list = getSuperSetRec(chars, index+1);
            List<List<Character>> res = new ArrayList<List<Character>>(list);
            for(List<Character> l : list){
                List<Character> temp = new ArrayList<Character>(l);
                temp.add(chars[index]);
                res.add(temp);
            }
            return res;
        }
    }

the second approach is very interesting. We use binary number to present each subset, 1 at any position of the binary number means the character at that position exists in the subset, e.g. 1 1 1 corresponding to {a,b,c}, 1 0 0 corresponding to {a}, so we can use 2^3 numbers to represent each subset, the problem becomes to find on every position of the binary number if it is 1 or 0.

public static void printSuperSetIteratively(char[] chars){
        int size = chars.length;
        int superSetSize = (int)Math.pow(2, size);
        List<List<Character>> list2 = new ArrayList<List<Character>>();
        for(int i=0; i<superSetSize; i++){
          
            List<Character> list = new ArrayList<Character>();
            for(int j=0; j<size; j++){
                if((i&1<<j)>0){
                    list.add(chars[j]);
                }
            }
            list2.add(list);
        }
      
        System.out.println(list2);
    }

Maximum Volume of Trapped Rain Water

I got this quiz from friend Peng Li, you can read his blog from here: http://allenlipeng47.com/PersonalPage/index/view/186/nkey.

The problem can also be found at geeksforgeeks site: http://www.geeksforgeeks.org/trapping-rain-water/

There are two approaches to solve this problem.

The first approach is to find the dividers which can trap water between them. For a bar becomes a divider, it needs to 1) no shorter than any bars on its left side up to previous divider; 2) no shorter than any bars on its right up to next divider; Essentially the dividers are local max; And the first and last bars are dividers. And if bar i is divider, then its next divider on its right meets one of the conditions
 1) taller than bar i;
 2) shorter than bar i but taller than any one else on the right.

/*
     * http://www.geeksforgeeks.org/trapping-rain-water/
     *
     * the key here is to find the dividers which can trap water between them
     * the characteristic of the dividers are they are taller than the levels between them
     *
     * and note the first and last levels are always the dividers
     */
    public static int maxTrapWater(int[] levels){
        int len = levels.length;
        /*
         * an array for each index i, it contains the index of element
         * which is larger than current levels at index i
         */
        int[] nextLarger = new int[len];
        /*
         * there is no element on the right, so set it to len
         */      
        nextLarger[len-1] = len;
        /*
         * go from right to left, for each element in the array
         * find the closest element on the right which is bigger
         * if there is none, then set its value to len
         */
        for(int i=len-2; i>=0; i--){
            int p = i+1;
            while(p<len && levels[i]>=levels[p])
                p = nextLarger[p];
            nextLarger[i] = p;
        }
      
        boolean[] isDivider = new boolean[len];
        isDivider[0] = true;
        isDivider[len-1] = true;
        int p = 0;
        while(p<len){
            int next = nextLarger[p];
            if(next == len){//levels[p] is the tallest compared to any level on the right
                isDivider[p] = true;
                p++;
            }else{
                if(isDivider[p])//levels[p] is divider, level[next] taller than that, then it is divider too
                    isDivider[next] = true;
                p = next;
            }
        }
      
        /*
         * go through dividers to calculate the water volume between them
         */
        int pre = levels[0];  
        int preIndex = 0;
        int sum = 0;
        for(int i=1; i<len; i++){
            if(isDivider[i]){
                sum += Math.min(levels[i], pre) * (i-preIndex-1);
                preIndex = i;
                pre = levels[i];
            }else
                sum -= levels[i];
        }
      
        return sum;

    }

The second approach is simpler, take any bar i, if the maximum height of bars on its right is iR and the maximum height of bars on its left is iL, then the water on top of bar i is Math.min(iR, iL) - i.

public static int maxTrapWater2(int[] levels){
        int len = levels.length;
       
        int[] leftMax = new int[len];
        leftMax[0] = levels[0];
       
        int[] rightMax = new int[len];
        rightMax[len-1] = levels[len-1];
       
        for(int i=1; i<len; i++)
            leftMax[i] = Math.max(levels[i], leftMax[i-1]);
       
        for(int i = len-2; i>=0; i--)
            rightMax[i] = Math.max(levels[i], rightMax[i+1]);
       
        int sum = 0;
        for(int i=0; i<len; i++){
            sum += Math.min(leftMax[i], rightMax[i]) - levels[i];
        }
       
        return sum;
    }


Test cases:

@Test
    public void maxTrapWater2(){
        assertEquals(2, ArrayQ.maxTrapWater2(new int[]{2,0,2}));
        assertEquals(2, ArrayQ.maxTrapWater(new int[]{2,0,2}));
       
        assertEquals(5, ArrayQ.maxTrapWater2(new int[]{2,0,1,0,3}));
        assertEquals(5, ArrayQ.maxTrapWater(new int[]{2,0,1,0,3}));
    }

Print boundary nodes of binary tree

This is from LeetCode:

Print all edge nodes of a complete binary tree anti-clockwise.
That is all the left most nodes starting at root, then the leaves left to right and finally all the rightmost nodes.
In other words, print the boundary of the tree.
Variant: Print the same for a tree that is not complete.

The key to solve this problem is to understand recursion and how we use it. Recursion can be done by bottom-up or top-down fashion. Bottom-up approach is to build up the stack until hitting the bottom then start to present the result, top-down approach is to present the result along the way to bottom and terminate at the bottom.

Here is the code. The comments explain what each method tries to accomplish.

    public static class Tree {
        int v;
        Tree left;
        Tree right;
        public Tree(int v){
            this.v = v;
        }
        public Tree(int v, Tree left, Tree right){
            this.v = v;
            this.left = left;
            this.right = right;
        }
    }
  
    public static void printBoundary(Tree root){
        //print left-most from top to bottom
        Tree curr = root;
        printLeftMost(curr);
        //print leaves from left to right
        printLeavesLeftRight(root);
        //print right-most from bottom to top
        printRightMost(root, root);
    }
  
    /**
     * print the right most nodes bottom up
     * and skip the first and last
     * @param root
     * @param first
     */
    public static void printRightMost(Tree root, Tree top){
        if(root.right!=null)
            printRightMost(root.right, top);
        else if(root.left!=null)
            printRightMost(root.left, top);
        if(root!=top && root.left!=null && root.right!=null)
            System.out.println(root.v);
    }
    /**
     * print leaves from left to right
     * and skip the left most leaf
     * and return the last one
     * @param root
     * @param start
     * @return
     */
    public static void printLeavesLeftRight(Tree root){
        if(root==null)
            return;
        printLeavesLeftRight(root.left);
        if(root.left==null && root.right==null){
            System.out.println(root.v);
        }
        printLeavesLeftRight(root.right);
    }
    /**
     * print left most nodes from top to bottom
     * and skip/return the last one
     * @param root
     * @return
     */
    public static void printLeftMost(Tree root){
        if(root.left==null && root.right==null)  
            return;
        System.out.println(root.v);
        if(root.left!=null)
            printLeftMost(root.left);
        else
            printLeftMost(root.right);
    }

Break compound word into multiple words

A compound word is a word which can be broken into multiple words. For example: appletree can be broken to apple and tree. Note a single word is not compound word, and a compound word may be broken into words in different ways, for example, autopay can be broken into au, to, pay, Or auto, pay.

Here we use woomom as example, and assume we have a helper function isWord(String w) which can tell us if any string is word or not.

    /*
     * woomom = woo + mom Or woom + om
     */
    static boolean isWord(String w){
        return w.equals("woom") || w.equals("woo") || w.equals("om") || w.equals("mom");
    }
   
    public static String printCompoundWord(String w){
        return printCompoundWordRec(w, 0, 0);
    }
   
    public static String printCompoundWordRec(String w, int start, int found){
        if(start == w.length()){
            return found>1?"":null;
        }
       
        for(int i=start+1; i<=w.length(); i++){
            if(isWord(w.substring(start, i))){
                String s  = printCompoundWordRec(w, i, found+1);
                if(s!=null){
                    String re = w.substring(start, i) + "-" + s;
                    if(found==0){
                        System.out.println(re);
                    }else
                        return re;
                   
                }
            }
        }
       
        return null;
    }

Here is iterative approach to check if word is compound word.

Find values at kth row are 0 and kth column in a 2D mattrix are 1

This question comes from geekforgeek: http://www.geeksforgeeks.org/find-k-such-that-all-elements-in-kth-row-are-0-and-kth-column-are-1-in-a-boolean-matrix/

Given a square boolean matrix mat[n][n], find k such that all elements in k’th row are 0 and all elements in k’th column are 1. The value of mat[k][k] can be anything (either 0 or 1).  If no such k exists, return -1. Do it in O(n) time.

Note there is only one such k can satisfy the rules.

Simple way is to do that is to find a kth row that all values are 0s except the kth element. Then check the kth column if all values are 1s except the kth element. This requires us to check all of the element. Time complexity: O(n*n)

Another way to travel from top-left corner, we start with 0th row:
go right if the element is 0, if we reach the end of row, then that means: 1) this rth row is potential candidate; 2) the columns/rows from r+1 to n-1 are not candidate; And we check kth row/col values.
go down if the element is 1, for the current row is no longer qualifies.

Since we either go right or go down, then time complexity is O(n)

     public static int findKthRow(int[][] mat){
        int n = mat.length;
        int row = 0;
        while(row<n-1){
            int col = row + 1;
            //move from left to right at current row
            while(col<n && mat[row][col] == 0){
                col++;
            }
           
            /*
             * if we reach the last column of current row, then
             *    this row is candidate and
             *    rest of rows are not candidates
             * otherwise
             *     we go down one row below   
             */       
            if(col == n){
                //check if this row is qualified
                return checkKthRowCol(mat, row)?row:-1;
            }else{
                row++;
            }
        }
       
        return checkKthRowCol(mat, row)?row:-1;
    }
   
    private static boolean checkKthRowCol(int[][] mat, int k){
        int n = mat.length;
        for(int i = 0; i<n; i++){
            if(i==k)
                continue;
            else{
                if(mat[k][i]==1 || mat[i][k]==0)
                    return false;
            }
        }
        return true;
    }

a simple regular expression implementation

Implement a simple regular expression based string match. 

. - any character
* - match 0 or more times of previous character

/**
     *
     * @param target
     * @param regex
     * @return
     */
    public static boolean isMatch(String target, String regex){
        assert !target.isEmpty() && !regex.isEmpty();
        int p1 = 0;
        int p2 = 0;
        int len1 = target.length();
        int len2 = regex.length();
        char pre = '\0', c1, c2 = '\0';
       
        while(p1<len1 && p2<len2){
            c1 = target.charAt(p1);
            c2 = regex.charAt(p2);
           
            if(c2 == '.'){
                p1++;p2++;
                pre = '.';
            }else if(c2 == '*'){               
                if(pre == '\0'){
                    return false;
                }
                else if(pre == '.' || pre == c1){
                    p1++;
                }else{
                    p2++;
                    pre = '\0';
                }
            }else{
                if(c1 == c2){
                    pre = c1;
                    p1++; p2++;
                }else{
                    if(p2+1<len2 && regex.charAt(p2+1) == '*'){
                        p2++;p2++;
                    }else
                        return false;
                }
                   
            }
        }
       
        if(p1 == len1)
            return true;
        else
            return false;
    }

Least recently used cache (LRU) implementation

One of the leetcode questions is to implement a least recently used cache. Basically a cache has to combine two kinds of data structures: a hash table so we can get/set item and a linked list so we can maintain the order of entries.

In JDK there is LinkedHashMap, which does the above, its implement a special Map.Entry class which only has key and value, but also maintain pointer to the next and previous Map.Entry.

Here are couple of my implementations:

1. Use LinkedHapMap directly:

public class SimpleLRUCache {
    private int capacity;
    LinkedHashMap<Object, Object> map;
   
    public SimpleLRUCache(final int capacity){
        this.capacity = capacity;
      
        map = new LinkedHashMap<Object, Object>(12, 0.76f, true){
            protected boolean removeEldestEntry(Map.Entry<Object,Object> eldest){
                return this.size() == capacity;              
            }
        };
      
    }
}

2. Use HashMap and LinkedList:

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    public static class Node{
Object key;
Object value;
Node pre;
Node next;
}

Map<Object, Node> map;

int capacity;

//head points to the oldest entry
Node head;
Node tail;

public LRUCache (int c){
this.capacity = c;
this.map = new HashMap<Object, Node>();
}

public Object get(Object key){
if(map.containsKey(key)){
Node n = map.get(key);
remove(n);
addLast(n);
return n.value;
}else
return null;

}

public void set(Object key, Object value){
if(map.containsKey(key)){
Node n = map.get(key);
remove(n);
addLast(n);
return;
}

if(map.size() == this.capacity){
map.remove(head.key);
remove(head);
}

Node n = new Node();
n.key = key;
n.value = value;

addLast(n);

map.put(key, n);

}

public void addLast(Node n){
if(head==null){
head = n;
tail = n;
}else{
tail.next = n;
n.pre = tail;
tail = n;
}
}


public void remove(Node n){
if(n.pre == null){
head = n.next;

}else{
n.pre.next = n.next;
}

if(n.next == null){
tail = n.pre;
}else
n.next.pre = n.pre;

//set the pointer so n can be gc'd
n.pre = n.next = null;
}
}

3. Synchronized LRU

import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

/*
 * a thread-safe LRUCache implementation using lock
 *
 * note only most important methods are implemented
 */
public class SynchronizedLRUCache<K, V> implements Map<K,V> {

    private final Map<K, V> cache;
   
    public SynchronizedLRUCache(final int maxSize, final int initSize, final float lf){  
        this.cache = new LinkedHashMap<K ,V>(initSize, lf){
            private static final long serialVersionUID = -1218440011343946609L;

            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> oldest){
                return size() > maxSize;
            }
        };
    }
   
    public SynchronizedLRUCache(final int maxSize, final int initSize){  
        this(maxSize, initSize, 0.75f);
    }
   
    public SynchronizedLRUCache(final int maxSize){  
        this(maxSize, 1<<4, 0.75f);
    }
   

    public int size() {
        synchronized(cache){
            return cache.size();
        }      
    }

   
    public boolean isEmpty() {
        synchronized(cache){
            return cache.isEmpty();
        }
    }

   
    public boolean containsKey(Object key) {
        synchronized(cache){
            return cache.containsKey(key);
        }
    }

   
    public V put(K key, V value) {
        synchronized(cache){
            return cache.put(key, value);
        }
    }
   
   
    public V get(Object key) {
        synchronized(cache){
            return cache.get(key);
        }
    }
   
   
    public void putAll(Map<? extends K, ? extends V> m) {
        synchronized(cache){
            cache.putAll(m);
        }
      
    }
   
   
    public boolean containsValue(Object value) {
        // TODO Auto-generated method stub
        return false;
    }
   

    public V remove(Object key) {
        // TODO Auto-generated method stub
        return null;
    }  

   
    public void clear() {
        // TODO Auto-generated method stub
      
    }

   
    public Set<K> keySet() {
        // TODO Auto-generated method stub
        return null;
    }

   
    public Collection<V> values() {
        // TODO Auto-generated method stub
        return null;
    }

   
    public Set<java.util.Map.Entry<K, V>> entrySet() {
        // TODO Auto-generated method stub
        return null;
    }

   

}

String tokenizer

Given a function which will tell if a string is word or not, and given a string, break it into multiple words. For example: "usaway" can be broken into "us away" or "usa way".

If we think each index of characters in the string is a node in a direct graph, then there is edge from node i to j if substring from index i to j is a word. Start from node at index 0, if we can find a path to node at index of last character, then we find a way to tokenize the string.  To do this we can use depth first search. 

The following is the code. Note if there are multiple ways to break a string into words, then the method will only return one way. 

public static String tokenize(String s){

String[] result = new String[1];

result[0] = "";

dfs(s, 0, result);

return result[0];

}

private static boolean dfs(String s, int index, String[] result){

if(index == s.length())

return true;

for(int i=index+1; i<=s.length(); i++){

String substring = s.substring(index, i);

if(isWord(substring) && dfs(s, i, result)){

result[0] =  substring + " " + result[0];

return true;

}

}

return false;

}

The second tokenize method will return a list. Each item in the return list is a list of indices which form a path from index at 0 to the last index of the string. 

public List<List<Integer>> tokenize2(String input){

/*

* map character index position to the next character index position if they are part of the solution

*/

Map<Integer, List<Integer>> store = new TreeMap<Integer, List<Integer>>();

dfs(input, store, 0);

List<List<Integer>> result = new ArrayList<List<Integer>>();

List<Integer> list = new ArrayList<Integer>();

list.add(0);

result.add(list);

boolean flag = true;

while(flag){

flag = false;

List<List<Integer>> copy = new ArrayList<List<Integer>>();

for(List<Integer> li : result){

int k = li.get(li.size()-1);

if(store.containsKey(k)){

flag = true;

for(int n : store.get(k)){

List<Integer> temp = new ArrayList<Integer>(li);

temp.add(n);

copy.add(temp);

}

}else

copy.add(li);

}

result = copy;

}

return result;

}

private Integer dfs(String s, Map<Integer, List<Integer>> store, int from){

int len = s.length();

if(from == len-1)//we find the leaf node

return from;

for(int i=from+1; i<len-1; i++){

if(isWord(s, from, i)){

Integer ret = dfs(s, store, i);

if(!store.containsKey(from)){

List<Integer> list = new ArrayList<Integer>();

store.put(from, list);

}

//the edge from-ret form the path which is the solution

store.get(from).add(ret);

return ret==null?null:from;

}

}

return null;

}