OA1

longestPalindrome.java

/*
 * newStr
 * Returns a special processed string that:
 * 1. has one additional "&" marking beginning and "$" marking ending, 
 * 	  and by doing this we don't need to do additional bound bound checking of the string in our next steps
 * 2. has "#" between each letter in this string
 * It is safe to do this step because the string input contains only lower case letters
 * 
 * @author 	Xiang Li <[email protected]>
 * @param 	s	the string to be processed
 * @return 	the processed string
 */
static String newStr(String s)
{
	int n = s.length();
	if(n==0) return "&$";
	String newstr = "^";
	for(int i=0;i<n;++i)
	{
		newstr+="#"+s.substring(i,i+1);
	}
	newstr+="#$";
	return newstr;
}

/*
 * 	 * longestPalindrome
	 * Returns longest palindromic substring in string s
	 * 
	 * @author	Xiang Li <[email protected]>
	 * @param	s	the string that contains a longest palindromic substring
	 * @return	the longest palindromic substring of s
	 * 
	 * 
	 * Time: O(N)
	 * DP Function:
	 * p[i] is half of the length of the longest palindrome substring centered at position i
	 * cent is the center position of the longest palindrome substring in string s
	 * rightbound is the rightbound of the longest palindrom substring in string s (centered at cent)
	 * p[i] = p[2*cent - i]		if(rightbound - i > p[2*cent-i]), 
	 * 							i.e. the longest palindrome substring centered at i is contained in 
	 * 							the longest palindrome substring centered at cent
	 * 
	 * 		= rightbound - i 	otherwise  
	 * 
 */
static String longestPalindrome(String s)
{
	//STEP 1: Set up new string processed in order to check palindrome
	String newstr = newStr(s);
	char[] arr = newstr.toCharArray(); //the char array of the string
	int n = arr.length;
	//the array p[i] stores the length of the half part of the longest palindrome substring centered at position i
	//p[i] = rightbound of the longest palindrome string - center position i
	int[] p = new int[n]; 
	
	
	int palLen=0;//palLen is the current length of the half part of the palindrome substring
	int rightBound=0;//rightBound is the rightmost position of the palindrome substring
	int j;//j is the symmetric position of i 
	
	//STEP 2: DP process to find all p[i]
	for(int i=1;i<n-1;++i)
	{
		j = 2*palLen-i; //find symmetric position of i
		
		//DP function
		if(rightBound>i)
			p[i] = Math.min(rightBound-i, p[j]);
		else
			p[i] = 0;
		
		//expand the palindrome centered at position i
		while(arr[i+1+p[i]] == arr[i-1-p[i]])
			p[i]++;
		
		//if we find a new rightbound (the expansion is beyond current rightbound)
		if(i+p[i]>rightBound)
		{
			//record new length and rightbound of the longest palindrome so far
			palLen = i;			
			rightBound = p[i]+i;
		}
		
	}
	
	//STEP 3: Find the center position and the length of the longest palindrome substring
	int maxPalLen = 0;
	int centerIdx = 0;
	for(int i=1;i<n-1;++i)
	{
		if(p[i]>maxPalLen)
		{
			maxPalLen = p[i];
			centerIdx = i;
		}
	}
	
	int leftBound = (centerIdx-1-maxPalLen)/2;
	return s.substring(leftBound, leftBound+maxPalLen);
}

MergeTwoLists.java

/*
	 * mergeTwoLists
	 * Returns the head of a sorted linked list, which is created by merging two sorted linked lists.
	 * 
	 * @author	Xiang Li <[email protected]>
	 * @param	l1 	the head of the first sorted linked list to be merged
	 * @param	l2 	the head of the second sorted linked list to be merged
	 * @return	the head of the merged linked list
	 * 
	 * 
	 * Let N be the total number of nodes of the two lists to be merged
	 * Big-O Runtime Analysis: 
	 * O(N) - worst case, since we need to traverse through all nodes in two lists in order to merge them
	 * O(1) - best case, one or both of the two lists are null, therefore we do not need to go through all nodes since we can simply return 
	 * 		  the list that is not null or if both of them are null, return null
	 *
	 * Idea:
	 * Problem 1:	
	 * First we need to deal with the head issue: we may need several lines of codes to compare the heads of two lists and set up a new head,
	 * in order to have a head node that can access the "next" member
	 * 
	 * Solution:
	 * Use of dummy node - now every node, including the heads of two lists, becomes "next"
	 * 
	 * Problem 2:
	 * Then we need to check for null: 
	 * if one of the two lists is null, the other list is the desired list; if both are null, the we just return null
	 * 
	 * Solution:
	 * By using the dummy node, we don't need to do anything since dummy.next = null by default if we don't append anything to it
	 * 
	 * Problem 3:
	 * Merge: the main process of this function
	 * 
	 * Solution:
	 * Use a typical merge process that is generally used in mergesort algorithm
	 * When we are iterating the two lists, if l1.val < l2.val, then the next node is l1
	 * else, the next node is l2
	 * 
	 * Problem 4:
	 * Post-merging process: we may have some nodes left in original two lists after merging
	 * 
	 * Solution:
	 * The left nodes are those who can't be compared (i.e., no node in the other list is bigger than those nodes)
	 * We can simply append them to the iterator
	 * This can be done together with check null process
	 */
	
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		//l1 - head of list 1, l2 - head of list 2
		
		ListNode dummy = new ListNode(0); //set up a dummy node used as a "fake" head
		ListNode iter = dummy; //set up the iterator, starting from the dummy node
		
		//The merge process. 
		//It will not go into the loop if one or both of the two lists are null
		while (l1 != null && l2 != null) {
			if (l1.val < l2.val) {
				iter.next = l1;	//case 1: l1's value is smaller, then next node is l1
				l1 = l1.next;	//l1 is now its next node in list 1
			} else {
				iter.next = l2;	//case 2: l2's value is smaller, or both l1 and l2's value are the same
				l2 = l2.next;	//l2 is now its next node in list 2
			}
			iter = iter.next;	//update iterator's location to the next to-be added node (i.e., its next)
		}
		
		//check for null and do the post-merging process
		
		//Case 1: There are some nodes left in list 1. Append them to iterator. 
		//		  Or the l2 is null, then list 1 is our desired list. Append list 1 to iterator.
		if (l1 != null) iter.next = l1;	
		
		//Case 2: There are some nodes left in list 2. Append them to iterator.
		//		  Or the l1 is null, then list 2 is our desired list. Append list 2 to iterator.
		if (l2 != null) iter.next = l2;	
		
		//Case 3: Both of list 1 and list 2 are null, we don't need to do anything since dummy's (and iter's, in this case)
		//default next node is null.
		
		return dummy.next; //dummy.next is the true head of our merged list since we begin our merging process from dummy.next
	}

removeVowel.java

public static String removeVowel(String s)
{
	String ret = "";
	Set<Character> set = new HashSet<Character>();
	set.add('a');
	set.add('e');
	set.add('i');
	set.add('o');
	set.add('u');
	set.add('A');
	set.add('E');
	set.add('I');
	set.add('O');
	set.add('U');
	
	for(int i=0;i<s.length();++i)
	{
		if(!set.contains(s.charAt(i)))
			ret+=s.charAt(i);
	}
	return ret;
}

reverseHalf.java

//1-2-3			1-3-2
//1-2-3-4		1-2-4-3
//1-2-3-4-5		1-2-5-4-3
/*
 * reverseHalf
 * Returns the list in which the second half has been reversed
 * 
 *
 * Big-O Analysis:
 * O(N): we need to traverse the whole linked list in order to get the length and then find the half point.
 *
 * @author	Xiang Li <[email protected]>
 * @param	head	a listnode that points to the head of the list
 * @return	the head of the list in which the second half has been reversed
 * 
 * 
 */




public static ListNode reverseHalf(ListNode head)
{
	
	 if(head==null) return null;//if the list itself is null, return null
	 if(head.next==null) return head;//if the list has only one node, no need to do anything
	 if(head.next.next==null) return head;//if the list has only two nodes, no need to do anything
	 
	 //STEP 1: Calculate the length and get the half length
	 int len = 1;
	 ListNode curr = head;
	 while(curr.next!=null)
	 {
		 curr = curr.next;
		 len++;
	 }
	 int half=len/2+1;
	 
	 
	 len = 1;//reset the len to be 1 for next step
	 
	 //STEP 2: Locate the start node of the reverse (and the end node, which is just the tail of the list)
	 ListNode reverseStart = head;
	 ListNode reverseEnd = curr;
	 ListNode next = null;
	 ListNode prev = null;//have a prev node pointing to the previous node of the starting point of reverse
	 while(reverseStart!=null)
	 {
		 len++;
		 prev = reverseStart;
		 reverseStart =reverseStart.next;
		 if(len==half)
			 break;//once we have reached the half point, we know that we have got the starting point
	 }
	 
	 //STEP 3: Reverse
	 prev.next = reverseEnd;//now the previous node's next is the current tail
	 curr = head;
	 prev = null;
	 curr = reverseStart;
	 while(curr!=null)
	 {		
		//the process of switch next and previous nodes
		next = curr.next;
		curr.next = prev;
		prev = curr;
		curr = next;
	 }	
	 return head;
}

subtree.java

/*
 * subtree
 * Returns if the tree with root node2 is a subtree of the tree with root node1
 * 
 * Big-O Analysis:
 * O(N) - we need to traverse the whole tree (worst case) in order to try all possible roots of the subtree.
 * 
 * @author	Xiang Li <[email protected]>
 * @param	node1	the root of the tree 1 to be checked for subtree
 * @param	node2	the root of a tree that needs to be tested if it is a subtree for tree 1
 * @return	true 	if node2 is the root of a subtree of tree 1
 * 			false 	otherwise
 * 
 */




static boolean subtree(TreeNode node1, TreeNode node2)
{
	if(node2==null) return true;//null is a subtree of all trees
	if(node1==null) return false;//null has only one subtree which is also null, and this case is tested above
	if(node1.value == node2.value)
		//successfully found the root of a potential subtree, recursively check left and right children
		return subtree(node1.left, node2.left) && subtree(node1.right, node2.right);
	else
		//failed finding the root of subtree, recursively try left and right to find root
		return subtree(node1.left, node2) || subtree(node1.right, node2);
}

twoSumPairs.java

	
	/*
	 * twoSum
	 * Returns number of pairs of distinct numbers that for each pair the sum of its two elements equals to the target
	 * 
	 * 
	 * Big-O Analysis
	 * O(N): we need to go through the whole array in order to check all values 
	 *
	 * @author	Xiang Li <[email protected]>
	 * @param	numbers the array that contains all numbers to be tested
	 * @param	target the number that for every desired pair the sum of its two elements equals to
	 * @return	number of desired distinct pairs
	 * 
	 * 
	 */
	
	
	public static int twoSumDistinct(int[] numbers, int target) {
		//use one hashset set to store the visited value so far
		Set<Integer> set = new HashSet<>();
		//use the hashmap paired to store the value that has already been paired, and its size is the number of pairs we need
		Set<Integer> paired = new HashSet<>();
		int counter=0;
		for (int i = 0; i < numbers.length; i++) {
			int value = numbers[i];
			//set.contains -> determine if the part that has been visited contains the target-value
			//paired.contains -> determine if the value and target-value has already been used -> eliminate duplicate
			if (set.contains(target - value) && !paired.contains(value) &&!paired.contains(target-value)) {
				paired.add(value);//we have already find a pair, add this value and will never use it again
			}
			set.add(value);//add the visited value
		}
		return paired.size();//the size of the hashset is the number of pairs
	}
	
	/*
	 * twoSum
	 * Returns number of pairs of numbers that for each pair the sum of its two elements equals to the target
	 * 
	 * Big-O Analysis:
	 * O(N)
	 * @author	Xiang Li <[email protected]>
	 * @param	numbers the array that contains all numbers to be tested
	 * @param	target the number that for every desired pair the sum of its two elements equals to
	 * @return	number of desired pairs
	 * 
	 * 
	 */
	public static int twoSumRepeat(int[] numbers, int target)
	{
		//hashmap count is used to store the number of each value
		Map<Integer, Integer> count = new HashMap<>();
		int counter=0;//the integer counter is the number of pairs
		
		//now we need go through the array and store the numbers of each value
		for(int i=0;i<numbers.length;++i)
		{	
			if(count.containsKey(numbers[i]))
				count.put(numbers[i], count.get(numbers[i])+1);
			else
				count.put(numbers[i], 1);
		}
		for (int i = 0; i < numbers.length; i++) {
			int value = numbers[i];
			if (count.containsKey(target-value)) {
				//now since target-value and value are both in the hashmap, we are sure there has to be at least one pair
				if(target-value == value)
					counter+=count.get(target-value)-1;//if the target == value+value, then we need get rid of one repeated identical pair
				else
					counter+=count.get(target-value);//else, we can simply add up the number of target-value
			}
		}
		return counter/2;//for each pair we have added it twice (one for value, one for target-value) so we need to divide by two
	}
}

validpar.java

	/*
	 * isValid
	 * Returns if the given string has valid combination of parenthesis
	 * 
	 * 
	 * @author	Xiang Li <[email protected]>
	 * @param	s the string that contains parenthesis
	 * @return	true if the string has valid combination of parenthesis
	 * 			false otherwise
	 * 
	 * O(N)
	 */
	
		
	//a hashmap which works as a dictionary, figuring out matching parenthesis pairs
	//key is the left (beginning) parenthesis, and value is the right(ending) parenthesis 
	private static final Map<Character, Character> map =
			new HashMap<Character, Character>() {{
				put('(', ')');
				put('{', '}');
				put('[', ']');
			}};
			
			public boolean isValid(String s) {
				Deque<Character> stack = new ArrayDeque<>();//set up a stack to check parenthesis in a LIFO order
				for (char c : s.toCharArray()) {
					if (map.containsKey(c)) {
						stack.push(c); //if left parenthesis, push into stack
					} else if (stack.isEmpty() || map.get(stack.pop()) != c) {
						//if right parenthesis we return false in two cases:
						//1. there is no left parenthesis (stack is empty), or
						//2. the last pushed left parenthesis is not a matching one for this right parenthesis
						return false;
					}
				}
				return stack.isEmpty();//after all checking process is done, if stack is empty we have balanced parentheses
			}