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