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