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