Amazon Interesting Finds

Amazon Interesting Finds:
https://www.amazon.com/stream

My Box:
https://www.amazon.com/stream?pf_rd_m=ATVPDKIKX0DER&tag=ra0a0-20&ascsubtag=ptr-DSS-1-9-15041960899627Z&ref_=ptr_DSS_1_9_15041960899627Z

http://dev-dsk-siyangl-2c-fd2771de.us-west-2.amazon.com:9080/stream

Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
For example:
Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".

My Thinking: This question only allows to add characters in the front. The resulting palindrome  might not be the optimal result.

For example "aabcb" should return "bcbaabcb" instead of "aabcbaa".

But this is a misleading. Solve for the optimal result will give you two cases. One is adding in the front, the other is adding in the back. We just pick the first one as the result.

Back to the question. Longest Palindromic Substring already gives a way to get the longest palindrome substring for each character position. Based on the array, we can extend the longest palindrome substring and get the optimal palindrome. But that might not be adding in the front. It doesn't matter. We should extend the longest palindrome that is nearest to position 0.

For example, "aabcb"->"#a#a#b#c#b#"
                                        12321214121
character 'c' has the longest palindrome coverage 4, but it's coverage does not cover position 0.

The largest coverage covering position 0 is the '#' between two 'a'. That's where we should extend from.

 public class Solution {  
   public String shortestPalindrome(String s) {  
     // preprocessing  
     if(s == null || s.length()==0) return s;  
     s = preProcess(s);  
       
     // get longest palindrome substring  
     int[] range = new int[s.length()];  
     int pivot = 0;  
     range[0] = 1;  
     for(int i = 1;i < s.length();i++){  
       if(range[pivot]+pivot > i){  
         if(range[pivot] + pivot > range[2*pivot-i] + i)  
           range[i] = range[2*pivot-i];  
         else  
           range[i] = range[pivot]+pivot-i;  
       }  
         
       while(range[i]+i < s.length() && i-range[i] >= 0 && s.charAt(i+range[i])==s.charAt(i-range[i])) range[i]++;  
   
       if(range[pivot]+pivot < range[i]+i) pivot = i;  
     }  
       
     // extend based on the longest palindrome substring  
     while(pivot-(range[pivot]-1)!=0) pivot--;  
     s = reverse(s.substring(pivot+range[pivot], s.length())) + s;  
       
     // postprocessing  
     return postProcess(s);  
       
   }  
     
   private String reverse(String s){  
     return new StringBuilder(s).reverse().toString();  
   }  
     
   private String postProcess(String s){  
     StringBuilder rslt = new StringBuilder();  
     for(int i = 0;i < s.length();i++)  
       if(s.charAt(i)!='#') rslt.append(s.charAt(i));  
     return rslt.toString();  
   }  
     
   private String preProcess(String s){  
     StringBuilder rslt = new StringBuilder();  
     for(int i = 0;i < s.length();i++){  
       if(i==0) rslt.append("#");  
       rslt.append(s.charAt(i));  
       rslt.append("#");  
     }  
     return rslt.toString();  
   }  
 }  

House Robber II

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Refer from House Robber I
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

My Thinkings:

The only difference is it's a circle now instead of a straight line. The last one cant be robbed if the first one has been robbed. If I am going to use the same Dynamic Programming Process, maintaining an array to store current optimized robbery status, I can tell if the first house has been robbed or not from if(opt[1] == 0). However, I cant control the robber not to rob house 1 since opt[1] will always equal to the value in the first house.

That seems to stop me from considering it a DP process. Then I came up with a more mathematics thought-- each time spin the house value by one step, calling DP solution on each new array. Now, I realize how stupid I am. In this way, I still didn't solve the circling thing-- how to include both cases, with the first robbed and with the first one save. And since every house is in a circle, it really doesn't matter where is the starting point if your algorithm is a correct one.

Then I turned to DFS. Since a lot of DP problem can be rewrote in a cached DFS(memorized DFS). It took me some time and finally I gave up this idea since I dont know what to cache.

The final result is easy. It is always like that. I realize I just need to change the initial condition and  run DP twice.

 public class Solution {  
   public int rob(int[] nums) {  
     return Math.max(circle_rob(nums, true), circle_rob(nums, false));  
   }  
     
   private int circle_rob(int[] nums, boolean robFirst){  
     // edge case  
     if(nums == null || nums.length == 0) return 0;  
       
     int[] opt = new int[nums.length+1];  
       
     // initial condition  
     opt[0] = 0;  
     opt[1] = robFirst?nums[0]:0;  
       
     // iteration  
     for(int i = 2;i < opt.length;i++){  
       if(i!=opt.length-1){   
         // normal case  
         opt[i] = Math.max(opt[i-2] + nums[i-1], opt[i-1]);  
       }else{  
         // last robbery  
         opt[i] = robFirst?opt[i-1]:Math.max(opt[i-2]+nums[i-1],opt[i-1]);  
       }  
     }  
       
     return opt[opt.length-1];  
   
   }  
     
     
 }  

Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true 

Naive Thinking: Similar to Implement Trie(prefix-tree) . But pattern '.' was included. For addWord() method, '.' doesn't affect the process since its not necessary to combine '.ad' and 'bad'. It's okay to leave both in the tree. While for search() method, when '.' appear in the word, we need to search all child nodes. when '.' appear in the node, we need to search this node also. So I apply a DFS approach to do search().

 public class WordDictionary {  
     
   LetterNode head = new LetterNode('*');  
   
   // Adds a word into the data structure.  
   public void addWord(String word) {  
     LetterNode cur = head;  
     for(int i = 0;i < word.length();i++){  
       if(cur.next.containsKey(word.charAt(i))){  
         cur = cur.next.get(word.charAt(i));  
       }else{  
         LetterNode son = new LetterNode(word.charAt(i));  
         cur.next.put(word.charAt(i), son);  
         cur = son;  
       }  
     }  
     cur.isEnd = true;  
   }  
   
   // Returns if the word is in the data structure. A word could  
   // contain the dot character '.' to represent any one letter.  
   public boolean search(String word) {  
     // DFS  
     return search(head, word, 0);  
   }  
     
   private boolean search(LetterNode node, String word, int layer){  
     LetterNode son = null, dot = null;  
     // ending case  
     if(node == null) return false;  
     if(layer == word.length()) return node.isEnd;  
       
     // general case  
     if(word.charAt(layer)=='.'){   
       // Go though all next nodes when '.' appear  
       Iterator iter = node.next.entrySet().iterator();  
       while(iter.hasNext()){  
         Map.Entry pair = (Map.Entry)iter.next();  
         if(search((LetterNode)pair.getValue(), word, layer+1))  
           return true;  
       }  
     }else{  
       // Go though target character nodes and '.' nodes  
       if(node.next.containsKey(word.charAt(layer)))  
         son = node.next.get(word.charAt(layer));  
       if(node.next.containsKey('.'))  
         dot = node.next.get('.');  
       if(son!=null || dot!=null)  
         return search(son, word, layer+1) || search(dot, word, layer+1);  
     }  
         
     return false;  
   }  
     
   class LetterNode{  
     Map<Character, LetterNode> next;  
     char letter;  
     boolean isEnd;  
     LetterNode(char c){  
       this.letter = c;  
       this.next = new HashMap<Character, LetterNode>();  
       this.isEnd = false;  
     }  
   }  
 }  
   
 // Your WordDictionary object will be instantiated and called as such:  
 // WordDictionary wordDictionary = new WordDictionary();  
 // wordDictionary.addWord("word");  
 // wordDictionary.search("pattern");  

Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].


Naive Thinking: Everything the same with Course Schedule I . Return the order of topological sort instead of whether can it be passed. Use an arraylist to store the order first. And then check if the size meets the number of courses. Then copy the arraylist to output array.

 public class Solution {  
   public int[] findOrder(int numCourses, int[][] prerequisites) {  
       
     // initilization  
     int[] rslt = new int[0];  
     List<Integer> order = new ArrayList<Integer>();  
     Queue<Integer> zero_pre_courses = new LinkedList<Integer>();  
     List<Course> courses = new ArrayList<Course>();  
     for(int i = 0;i < numCourses;i++) courses.add(new Course(i));  
       
     // read in prerequisite infomation  
     for(int i = 0;i < prerequisites.length;i++){  
       courses.get(prerequisites[i][0]).prerequisite.add(prerequisites[i][1]);  
       courses.get(prerequisites[i][1]).advanced.add(prerequisites[i][0]);  
     }  
       
     // group zero_prerequisite courses  
     for(int i = 0;i < numCourses;i++)  
       if(courses.get(i).prerequisite.isEmpty()) zero_pre_courses.add(i);  
       
     // topological sort  
     while(!zero_pre_courses.isEmpty()){  
       int curNum = zero_pre_courses.poll();  
       order.add(curNum);  
       Iterator<Integer> iter = courses.get(curNum).advanced.iterator();  
       while(iter.hasNext()){  
         int advNum = iter.next();  
         courses.get(advNum).prerequisite.remove(curNum);  
         if(courses.get(advNum).prerequisite.isEmpty()) zero_pre_courses.add(advNum);  
       }  
     }  
       
     // generate result  
     if(order.size() == numCourses){  
       rslt = new int[numCourses];  
       for(int i = 0;i < numCourses;i++)  
         rslt[i] = order.get(i);  
     }  
       
     return rslt;  
   }  
     
   class Course{  
     Set<Integer> prerequisite;  
     Set<Integer> advanced;  
     int label;  
     Course(int l){  
       this.label = l;  
       this.prerequisite = new HashSet<Integer>();  
       this.advanced = new HashSet<Integer>();  
     }  
   }  
 }  

Minimum Size Subarray Sum

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 under the problem constraint.

More practice: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Naive Thinking: It seems this question is a typical two-pointer question. My idea is to keep a right boundary pointer and a left boundary pointer, keep sum up everything between two boundaries and move left boundary pointer and right pointer accordingly. One thing to be notice is that the left pointer needs to be checked if it can be moved forward each times right pointer finish its extension.

Run time is O(n).

 public class Solution {  
   public int minSubArrayLen(int s, int[] nums) {  
     int left = 0;  
     int right = 0;  
     int sum = 0;  
     int leng = 0;  
     int min_leng = nums.length+1;  
     while(right < nums.length){  
       // extend right boundary  
       while(sum < s && right < nums.length){  
         sum += nums[right++];  
         leng++;  
       }  
       if(sum >= s && leng < min_leng) min_leng = leng;  
         
       // extend left boundary  
       do{  
         sum -= nums[left++];  
         leng--;  
         if(sum >= s && leng < min_leng) min_leng = leng;  
       }while(sum >= s && left < right);  
     }  
     return min_leng==nums.length+1?0:min_leng;  
   }  
 }  

The interesting part is the O(nlogn) run time solution. Even the run time is not efficient, it is still great practice to think it differently.

Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.

 class TrieNode {  
   // Initialize your data structure here.  
   public TrieNode() {  
       
   }  
 }  
   
 public class Trie {  
   private TrieNode root;  
   
   public Trie() {  
     root = new TrieNode();  
   }  
   
   // Inserts a word into the trie.  
   public void insert(String word) {  
       
   }  
   
   // Returns if the word is in the trie.  
   public boolean search(String word) {  
       
   }  
   
   // Returns if there is any word in the trie  
   // that starts with the given prefix.  
   public boolean startsWith(String prefix) {  
       
   }  
 }  
   
 // Your Trie object will be instantiated and called as such:  
 // Trie trie = new Trie();  
 // trie.insert("somestring");  
 // trie.search("key");  

Naive Thinking: At first I didn't know Trie. Here is the definition from Wikipedia.  https://en.wikipedia.org/?title=Trie

The structure was given. Only need to fill in the methods. The structure tell me that each node is described as TrieNode. And the whole trie is just referred by its root. Thus, a TrieNode should contain children TrieNode attributes in order to have access to every TrieNode in the tree via root TrieNode.

The search() method and startwith() method differs in that the last character must be an ending TrieNode in search() while startwith() doesn't have to be.

Below is my implementation. I use HashMap to maintain children TrieNode relationship.

 class TrieNode {  
   // Initialize your data structure here.  
   public String data;  
   public Map<Character, TrieNode> children;  
   public boolean isEnd;  
   public TrieNode() {  
     data = new String();  
     children = new HashMap<Character, TrieNode>();  
     isEnd = false;  
   }  
     
   public TrieNode(String s){  
     data = s;  
     children = new HashMap<Character, TrieNode>();  
     isEnd = false;  
   }  
 }  
   
 public class Trie {  
   private TrieNode root;  
   
   public Trie() {  
     root = new TrieNode();  
   }  
   
   // Inserts a word into the trie.  
   public void insert(String word) {  
     TrieNode cur = root;  
     for(int i = 0;i < word.length();i++){  
       if(cur.children.containsKey(word.charAt(i))){  
         cur = cur.children.get(word.charAt(i));  
       }else{  
         String s = root.data + word.charAt(i);  
         TrieNode child = new TrieNode(s);  
         cur.children.put(word.charAt(i), child);  
         cur = child;  
       }  
     }  
     cur.isEnd = true;  
   }  
   
   // Returns if the word is in the trie.  
   public boolean search(String word) {  
     TrieNode cur = root;  
     for(int i = 0;i < word.length();i++){  
       if(cur.children.containsKey(word.charAt(i)))  
         cur = cur.children.get(word.charAt(i));  
       else  
         return false;  
     }  
     return cur.isEnd;  
   }  
   
   // Returns if there is any word in the trie  
   // that starts with the given prefix.  
   public boolean startsWith(String prefix) {  
     TrieNode cur = root;  
     for(int i = 0;i < prefix.length();i++){  
       if(cur.children.containsKey(prefix.charAt(i)))  
         cur = cur.children.get(prefix.charAt(i));  
       else  
         return false;  
     }  
     return true;  
   }  
 }  
   
   

Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Naive Thinking: The description leads to a topological sort solution. But to execute a topological sort is not easy. If I directly use the 2D array on each iteration, I need to go though all 2D vectors. That's definitely not a good run time. The input 2D array needs to be preprocessed before implementing topological sort on it. After several trial, I find out that use a extra Course object with both prerequisite and advanced course attributes sounds.

 public class Solution {  
   public boolean canFinish(int numCourses, int[][] prerequisites) {  
     boolean exit = true;  
     List<Course> courses = new ArrayList<Course>();  
     Queue<Course> zero_pre_courses = new LinkedList<Course>();  
       
     // initialize courses list  
     for(int i = 0;i < numCourses;i++) courses.add(new Course(i));  
       
     // read in course prerequisite relationship  
     for(int i = 0;i < prerequisites.length;i++){  
       courses.get(prerequisites[i][0]).advanced.add(prerequisites[i][1]);  
       courses.get(prerequisites[i][1]).prerequisite.add(prerequisites[i][0]);  
     }  
       
     // group all zero prerequisite courses  
     for(int i = 0;i < numCourses;i++)  
       if(courses.get(i).prerequisite.isEmpty()) zero_pre_courses.add(courses.get(i));  
       
     // topological sort  
     while(!zero_pre_courses.isEmpty()){  
       Course course = zero_pre_courses.poll();  
       Iterator<Integer> iter = course.advanced.iterator();  
       while(iter.hasNext()){  
         int advancedCourseLabel = (int)iter.next();  
         Course advancedCourse = courses.get(advancedCourseLabel);  
         advancedCourse.prerequisite.remove(course.label);  
         if(advancedCourse.prerequisite.isEmpty()) zero_pre_courses.add(advancedCourse);  
       }  
       course.label = -1; // set label to -1 as the course is took  
     }  
       
     // check if all courses are took  
     for(int i = 0;i < numCourses;i++)  
       if(courses.get(i).label!=-1) exit = false;  
       
     return exit;  
       
   }  
   class Course{  
     Set<Integer> prerequisite;  
     Set<Integer> advanced;  
     int label;  
     Course(int l){  
       label = l;  
       prerequisite = new HashSet<Integer>();  
       advanced = new HashSet<Integer>();  
     }  
   }  
 }  

Reverse Linked List

Reverse a singly linked list.

Hint: A linked list can be reversed either iteratively or recursively. Could you implement both?

Naive Thinking: At first, I thought it cannot be done in O(1) space, so I use a stack and go through the linked-list once pushing one by one into stack. And then pop from the stack one by one. Not surprisingly, I got memory limit exceed. That's probably a sign that I used extra space. So I begin to think about using O(1) space. Just pointing each Node's next pointer to its previous one. In such a process, I need to always note down its next Node first or I will lost the remaining Nodes.

Iteratively:

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   // iteratively  
   public ListNode reverseList(ListNode head) {  
     ListNode pre = null, cur = head, next = null;  
     while(cur!=null){  
       next = cur.next;  
       cur.next = pre;  
       pre = cur;  
       cur = next;  
     }  
     return pre;  
   }  
 }  

Recursively:

 public class Solution {  
   // recursively  
   public ListNode reverseList(ListNode head) {  
     return reverseList(null, head);  
   }  
   private ListNode reverseList(ListNode pre, ListNode cur){  
     // ending case  
     if(cur==null) return pre;  
     // general case  
     ListNode next = cur.next;  
     cur.next = pre;  
     return reverseList(cur, next);  
   }  
 }  

Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example,
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

Naive Way: Use a HashMap to note down the mapping. Also use .containsKey and .containsValue function to check duplicates. The point being easily ignored is the value also needs to be uniquely mapped. No two characters can map to the same value.

 public class Solution {  
   public boolean isIsomorphic(String s, String t) {  
     Map<Character, Character> map = new HashMap<Character, Character>();  
     for(int i = 0;i < s.length();i++){  
       if(map.containsKey(s.charAt(i))){  
         if(t.charAt(i)!=map.get(s.charAt(i))) return false;  
       }else{  
         if(map.containsValue(t.charAt(i))) return false;  
         map.put(s.charAt(i), t.charAt(i));  
       }  
     }  
     return true;  
   }  
 }  

Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5


Naive Way: It is the most common way of manipulating linked list. But as for linked list, null pointer will always be a problem.

As usual, I use a fake head pointer to make my code more smooth.

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public ListNode removeElements(ListNode head, int val) {  
     ListNode fake = new ListNode(0);  
     ListNode pre = fake;  
     fake.next = head;  
     while(pre.next!=null){  
       ListNode cur = pre.next;  
       if(cur.val==val)  
         pre.next = cur.next; // remove the node  
       else  
         pre = cur;  
     }  
     return fake.next;  
   }  
 }  

Happy Number

Write an algorithm to determine if a number is "happy".
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example: 19 is a happy number

• 1² + 9² = 82
• 8² + 2² = 68
• 6² + 8² = 100
• 1² + 0² + 0² = 1

Naive Way: The statement is describing a recursive process. So it is obvious that the question want me to write a recursive method. The logic has been stated and clear. Base case (ending condition) is either n=1 or n has been visited. And since I need to mark whether a number has been visited, a hashset is required.

 public class Solution {  
   Set<Integer> visited = new HashSet<Integer>();  
   public boolean isHappy(int n) {  
     // base case  
     if(n==1) return true;  
     // visited  
     if(visited.contains(n)) return false;  
     // main processing  
     int sum = 0;  
     visited.add(n);  
     while(n!=0){  
       int lastDigit = n % 10;  
       sum += lastDigit * lastDigit;  
       n /= 10;  
     }  
     return isHappy(sum);  
   }  
 }  

Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4.

Naive Way: My first thought was to use "&" operation going though all numbers between m and n inclusively. That gets a TLE. I later wrote some test cases and find out that "&" operation is hard to keep even one bit when there is a gap between n and m.
For example: 4-8: 0100, 0101, 0110, 0111, 1000. result is 0000.
It turns out that m and n need to have same highest bit, otherwise the result will be 0.

I tried many times and finally find out that a method use only bit shift operation will do the trick. Any ">" or "<" compare condition will possibly ruin he algorithm because 0x80000000 is a negative number.

My method is a recursive one. The idea is keep finding highest bit of m, check if n has a higher bit. And let the recursive call do the rest bits.

 public class Solution {  
   public int rangeBitwiseAnd(int m, int n) {  
     return rangeBitwiseAnd(m,n,0x80000000);  
   }  
     
   private int rangeBitwiseAnd(int m, int n, int shift){  
       
     // edge case  
     if(m==0) return 0;  
       
     // find highest bit of m  
     while((shift & m) == 0){  
       if((shift & n) != 0) return 0;  
       shift >>>= 1;  
     }  
       
     return shift + rangeBitwiseAnd(m - shift, n - shift, shift);  
   }  
 }  

Improved Way: After viewing the Discuss, I find there are tons of lot better solutions.

One is from applewolf, who find out that keep comparing from lower bits to higher bits can do the trick.

 int rangeBitwiseAnd(int m, int n) {  
   return (n > m) ? (rangeBitwiseAnd(m/2, n/2) << 1) : m;  
 }  

Another is from haw64, who find out that the result of AND operation is just left most consecutive common part of n and m (just two numbers, no need of numbers in between).

 public int rangeBitwiseAnd(int m, int n) {  
     int count = 0;  
     while(m != n){  
       m >>= 1;  
       n >>= 1;  
       count++;  
     }  
     return m<<=count;  
   }  

Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:

11110
11010
11000
00000

Answer: 1
Example 2:

11000
11000
00100
00011

Answer: 3

Naive Way: Use DFS to go though all grid cells. Use a hashset to keep visited grid cells. Run time is O(n^2). And space is O(n^2).

 public class Solution {  
   public int numIslands(char[][] grid) {  
     Set<List<Integer>> visited = new HashSet<List<Integer>>();  
     int num = 0;  
     for(int i = 0;i < grid.length;i++)  
       for(int j = 0;j < grid[0].length;j++)  
         num+=dfs(grid,i,j,visited);  
     return num;  
   }  
   private int dfs(char[][] grid, int x, int y, Set<List<Integer>> visited){  
     // edge case  
     if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) return 0;  
     // island  
     if(grid[x][y] == '1'){  
       List<Integer> list = new ArrayList<Integer>();  
       list.add(x);  
       list.add(y);  
       if(!visited.contains(list)){  
         visited.add(list);  
         dfs(grid, x-1, y, visited);  
         dfs(grid, x+1, y, visited);  
         dfs(grid, x, y-1, visited);  
         dfs(grid, x, y+1, visited);  
         return 1;  
       }  
     }  
     return 0;  
   }  
 }  

I saw a algorithm in Discuss use the original grid to store visited grid cells. Thus reduce space used to O(1).

Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].


Naive Way: Use a level-order traversal and always note down the last TreeNode value in the result.

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public List<Integer> rightSideView(TreeNode root) {  
     List<Integer> list = new ArrayList<Integer>();  
     List<TreeNode> cur_layer = new ArrayList<TreeNode>();  
     // edge case  
     if(root==null) return list;  
     // initialize current layer  
     cur_layer.add(root);  
     // level-order traversal  
     while(!cur_layer.isEmpty()){  
       list.add(cur_layer.get(cur_layer.size()-1).val);  
       List<TreeNode> next_layer = new ArrayList<TreeNode>();  
       for(TreeNode node: cur_layer){  
         if(node.left!=null) next_layer.add(node.left);  
         if(node.right!=null) next_layer.add(node.right);  
       }  
       cur_layer = next_layer;  
     }  
     return list;  
   }  
 }  

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Naive Thinking: First thought was to use DP. The logic is as follows:
opt[i] // the maximum amount of money one rob without alerting the police.
// base case
opt[0] = 0
opt[1] = num[0]
// iteration
opt[i] = max(opt[i-1], opt[i-2]+num[i-1])

 public class Solution {  
   public int rob(int[] num) {  
     if(num == null || num.length == 0) return 0;  
     int opt[] = new int[num.length+1];  
     // base case  
     opt[0] = 0;  
     opt[1] = num[0];  
     // iteration  
     for(int i = 2;i <= num.length;i++)  
       opt[i] = Math.max(opt[i-1], opt[i-2] + num[i-1]);  
     return opt[num.length];  
   }  
 }  

From the structure of the code. It is easy to see the O(N) space could be constrained to O(1).

 public class Solution {  
   public int rob(int[] num) {  
     if(num == null || num.length == 0) return 0;  
     // base case  
     int pre = 0;  
     int cur = num[0];  
     // iteration  
     for(int i = 2;i <= num.length;i++){  
       int temp = cur;  
       cur = Math.max(cur, pre + num[i-1]);  
       pre = temp;  
     }  
     return cur;  
   }  
 }  

Word Search

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.


Naive Way: First came up with a DFS method. Need a hashset for each path to store visited positions.

 public class Solution {  
   class Node{  
     int x,y;  
     Node(int x, int y){  
       this.x = x;  
       this.y = y;  
     }  
     @Override  
     public boolean equals(Object other){  
       if (!(other instanceof Node))  
         return false;  
       Node n = (Node)other;  
       return this.x==n.x && this.y==n.y;  
     }  
     @Override  
     public int hashCode(){  
       return x << 16 | y;  
     }  
   }  
   public boolean exist(char[][] board, String word) {  
     for(int i = 0;i < board.length;i++)  
       for(int j = 0;j < board[i].length;j++){  
           Node node = new Node(i,j);  
           Stack<Node> stack = new Stack<Node>();  
           Set<Node> set = new HashSet<Node>();  
           stack.add(node);  
           set.add(node);  
           if(dfs(board, node, word, 0, stack, set))  
             return true;  
         }  
     return false;  
   }  
   private boolean dfs(char[][] board, Node node, String word, int index, Stack<Node> stack, Set<Node> set){  
     /* ending cases */  
     // find a path  
     if(index == word.length()) return true;  
     // invalid node  
     if(node.x < 0 || node.x >= board.length || node.y < 0 || node.y >= board[0].length) return false;  
     // not match  
     if(board[node.x][node.y] != word.charAt(index)) return false;  
     // recusive case  
     Node up = new Node(node.x-1, node.y);  
     if(!set.contains(up)){  
       stack.push(up);  
       set.add(up);  
       if(dfs(board, up, word, index+1, stack, set)) return true;  
       stack.pop();  
       set.remove(up);  
     }  
     Node down = new Node(node.x+1, node.y);  
     if(!set.contains(down)){  
       stack.push(down);  
       set.add(down);  
       if(dfs(board, down, word, index+1, stack, set)) return true;  
       stack.pop();  
       set.remove(down);  
     }  
     Node left = new Node(node.x, node.y-1);  
     if(!set.contains(left)){  
       stack.push(left);  
       set.add(left);  
       if(dfs(board, left, word, index+1, stack, set)) return true;  
       stack.pop();  
       set.remove(left);  
     }  
     Node right = new Node(node.x, node.y+1);  
     if(!set.contains(right)){  
       stack.push(right);  
       set.add(right);  
       if(dfs(board, right, word, index+1, stack, set)) return true;  
       stack.pop();  
       set.remove(right);  
     }  
     return false;  
   }  
 }  

And then, I think I am bring too much extra stuff to a simple problem. Better use a 2D array to record used cell.

 public class Solution {  
   public boolean exist(char[][] board, String word) {  
     // edge case  
     if(board == null || board.length == 0) return false;  
     if(word.length() > board.length*board[0].length) return false;  
     boolean[][] used = new boolean[board.length][board[0].length];  
     for(int i = 0;i < board.length;i++){  
       for(int j = 0;j < board[0].length;j++){  
         used[i][j] = true;  
         if(dfs(board, i, j, word, 0, used)) return true;  
         used[i][j] = false;  
       }  
     }  
     return false;  
   }  
   private boolean dfs(char[][] board, int x, int y, String word, int index, boolean[][] used){  
     // ending case  
     if(index==word.length()) return true;  
     if(board[x][y]!=word.charAt(index)) return false;  
     // recursive call  
     if(x-1 >= 0 && !used[x-1][y]){  
       used[x-1][y] = true;  
       if(dfs(board,x-1,y,word,index+1,used)) return true;  
       used[x-1][y] = false;  
     }  
     if(x+1 < board.length && !used[x+1][y]){  
       used[x+1][y] = true;  
       if(dfs(board,x+1,y,word,index+1,used)) return true;  
       used[x+1][y] = false;  
     }  
     if(y-1 >= 0 && !used[x][y-1]){  
       used[x][y-1] = true;  
       if(dfs(board,x,y-1,word,index+1,used)) return true;  
       used[x][y-1] = false;  
     }  
     if(y+1 < board[0].length && !used[x][y+1]){  
       used[x][y+1] = true;  
       if(dfs(board,x,y+1,word,index+1,used)) return true;  
       used[x][y+1] = false;  
     }  
     return false;  
   }  
 }  

but this code get TLE for the longest "aaa.."" string case. And then I saw others' code and found a modified, much more elegant way.

 public class Solution {  
   public boolean exist(char[][] board, String word) {  
     // edge case  
     if(word == null || board == null || board.length == 0) return false;  
     if(word.length() > board.length*board[0].length) return false;  
     boolean[][] used = new boolean[board.length][board[0].length];  
     for(int i = 0;i < board.length;i++)  
       for(int j = 0;j < board[0].length;j++)  
         if(dfs(board, i, j, word, 0, used)) return true;  
     return false;  
   }  
   private boolean dfs(char[][] board, int x, int y, String word, int index, boolean[][] used){  
     // ending case  
     if(index==word.length()) return true;  
     if(x < 0 || x >= board.length || y < 0 || y >= board[0].length) return false;  
     if(used[x][y] || board[x][y]!=word.charAt(index)) return false;  
     // recursive call  
     used[x][y] = true;  
     if(dfs(board,x-1,y,word,index+1,used)) return true;  
     if(dfs(board,x+1,y,word,index+1,used)) return true;  
     if(dfs(board,x,y-1,word,index+1,used)) return true;  
     if(dfs(board,x,y+1,word,index+1,used)) return true;  
     used[x][y] = false;  
     return false;  
   }  
 }  

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
] 

Naive Way: A recursive method is straightforward. Need to convey current index, n, current k as parameter to recursive function. It is a DFS idea.

 public class Solution {  
   public List<List<Integer>> combine(int n, int k) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     dfs(new Stack<Integer>(), 1, n, k, rslt);  
     return rslt;  
   }  
   private void dfs(Stack<Integer> path, int index, int n, int k, List<List<Integer>> rslt){  
     // ending case  
     if(k==0){  
       List<Integer> list = new ArrayList<Integer>(path);  
       rslt.add(list);  
       return;  
     }  
     // recursion case  
     for(int i = index;i <= n;i++){  
       path.push(i);  
       dfs(path, i+1, n, k-1, rslt);  
       path.pop();  
     }  
   }  
 }  

An iterative method correspondingly.

 public class Solution {  
   public List<List<Integer>> combine(int n, int k) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Deque<List<Integer>> gross = new ArrayDeque<List<Integer>>();  
     // edge case   
     if(k==0) return rslt;  
     // initialize the rslt  
     for(int i = 1;i <= n-k+1;i++){  
       List<Integer> list = new ArrayList<Integer>();  
       list.add(i);  
       gross.offerLast(list);  
     }  
     // iteration on k  
     int ind = 1;  
     while(ind++ < k){  
       int length = gross.size();  
       for(int i = 0;i < length;i++){  
         List<Integer> list = gross.pollFirst();  
         int num = list.get(list.size()-1);  
         for(int j = num+1;j <= n;j++){  
           List<Integer> new_list = new ArrayList<Integer>(list);  
           new_list.add(j);  
           gross.offerLast(new_list);  
         }  
       }  
     }  
     // add to result  
     while(!gross.isEmpty()) rslt.add(gross.pollFirst());  
     return rslt;  
   }  
 }  

Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".
Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Naive Way: In order to find a minimum window, there must be a way to represent the pattern (which is T) here and current accumulate characters set. A map is suitable to deal with that. Map each character to # of its appearance. And then, need to find a way to keep track of every possible position when a match was found and you need to delete the first character from current accumulate char set. A queue is suitable to do that.

A case when S = "bba" and T="ab" leads to  this line.

  while(isMatch(pattern, cur)){ /* Important Code! */  

One shortcoming is isMatch() funciton takes O(T) time.

 public class Solution {  
   public String minWindow(String S, String T) {  
     Map<Character, Integer> pattern = new HashMap<Character, Integer>();  
     Map<Character, Integer> cur = new HashMap<Character, Integer>();  
     Queue<Integer> queue = new LinkedList<Integer>();  
     int min = Integer.MAX_VALUE;  
     int begin = 0, end = 0;  
     // fill in pattern by T  
     for(int i = 0;i < T.length();i++) addToMap(pattern, T.charAt(i));  
     // initialize current set  
     for(int i = 0;i < T.length();i++) cur.put(T.charAt(i), 0);  
     // go through S to match the pattern by minimum length  
     for(int i = 0;i < S.length();i++){  
       if(pattern.containsKey(S.charAt(i))){  
         queue.add(i);  
         addToMap(cur, S.charAt(i));  
         // check if pattern is matched  
         while(isMatch(pattern, cur)){ /* Important Code! */  
           if(i - queue.peek() < min){  
             min = i - queue.peek();  
             begin = queue.peek();  
             end = i+1;  
           }  
           cur.put(S.charAt(queue.peek()), cur.get(S.charAt(queue.peek()))-1);  
           queue.poll();  
         }  
       }  
     }  
     return end > begin?S.substring(begin, end):"";  
   }  
   private void addToMap(Map<Character, Integer> map, Character c){  
     if(map.containsKey(c))  
       map.put(c, map.get(c)+1);  
     else  
       map.put(c,1);  
   }  
   private boolean isMatch(Map<Character, Integer> p, Map<Character, Integer> cur){  
     for(Map.Entry<Character, Integer> entry: p.entrySet())  
       if(cur.get((char)entry.getKey()) < (int)entry.getValue()) return false;  
     return true;  
   }  
 }  

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Naive Way: There lies a linear approach O(n+m).

 public class Solution {  
   public boolean searchMatrix(int[][] matrix, int target) {  
     // edge case  
     if(matrix==null || matrix.length==0) return false;  
     // general case  
     int i = 0, j = matrix[0].length-1;  
     while(i < matrix.length && j >= 0){  
       if(matrix[i][j] == target) return true;  
       if(matrix[i][j] > target) j--;  
       else i++;  
     }  
     return false;  
   }  
 }  

The idea is to start from upper right. If current number is larger than target, that means you cannot find target in current row. So turn to next row. If current number is smaller than target, that means the target must lie in current row.

Improved Way: Could use a binary search approach to search current row/column. Speed up the approach to O(logn + logm) = O(log(nm))

 public class Solution {  
   public boolean searchMatrix(int[][] matrix, int target) {  
     // edge case  
     if(matrix==null || matrix.length==0) return false;  
     // general case  
     int row = binarySearch(matrix, target);  
     if(row==-1) return false;  
     int col = binarySearch(matrix[row], target);  
     return col!=-1;  
   }  
   private int binarySearch(int[][] matrix, int target){  
     int low = 0, high = matrix.length-1;  
     while(low <= high){  
       int middle = (low+high)/2;  
       if(matrix[middle][0] <= target && middle==matrix.length-1) return middle;  
       if(matrix[middle][0] <= target && matrix[middle+1][0] > target) return middle;  
       if(matrix[middle][0] > target) high = middle-1;  
       else low = middle+1;  
     }  
     return low;  
   }  
   private int binarySearch(int[] array, int target){  
     int low = 0, high = array.length-1;  
     while(low <= high){  
       int middle = (low+high)/2;  
       if(array[middle] == target) return middle;  
       if(array[middle] > target) high = middle-1;  
       else low = middle+1;  
     }  
     return -1;  
   }  
 }