Key to CSE143X Final, Fall 2017

1.      Preorder traversal:     2 6 3 4 9 7 8 1 5 0
        Inorder traversal:      6 9 4 3 7 2 1 5 8 0
        Postorder traversal:    9 4 7 3 6 5 1 0 8 2


2.  Statement                       Output
    -----------------------------------------------------------------
    var1.method1();                 Rey 1
    var2.method1();                 Rey 1
    var5.method1();                 compiler error
    var2.method2();                 Rey 2
    var3.method2();                 Poe 2/Rey 1
    var4.method2();                 Rey 2
    var6.method2();                 Poe2/Rey 1
    var1.method3();                 compiler error
    var2.method3();                 Finn 3/Rey 2
    var3.method3();                 Finn 3/Poe 2/Rey 1
    var5.method3();                 compiler error
    var7.method3();                 compiler error
    ((Finn)var1).method1();         runtime error
    ((Rey)var4).method1();          Rey 1/Kylo 1
    ((Finn)var4).method1();         compiler error OR runtime error
    ((Rey)var3).method2();          Poe 2/Rey 1
    ((Kylo)var5).method2();         runtime error
    ((Poe)var6).method2();          Poe 2/Rey 1
    ((Kylo)var7).method3();         Kylo 3
    ((Rey)var6).method3();          compiler error

3. Two possible solutions:

		public static String moveToEnd(String s, char c) {
			if (s.isEmpty()) {
				return s;
			} else {
				if (s.charAt(0) == c) {
					return moveToEnd(s.substring(1), c) + s.charAt(0);
				} else {
					return s.charAt(0) + moveToEnd(s.substring(1), c);
				}
			}
		}       
		-----
		public static String moveToEnd(String s, char c) {
			int index = s.indexOf(c);
			if (index < 0) {
				return s;
			} else {
				return s.substring(0, index) + moveToEnd(s.substring(index + 1), c) + c;
			}
		}       
		
			
4. One possible solution:

		public static void removeWithFirstLetter(Set<String> words, String start) {
			Iterator<String> iter = words.iterator();
			while (iter.hasNext()) {
				String s = iter.next().toLowerCase();
				if (s.substring(0, 1).equals(start.toLowerCase())) {
					iter.remove();
				} 
			}
		}
		
		
5. One possible solution:

		public static void rearrangeDuplicates(Queue<Integer> q) {
			Stack<Integer> s = new Stack<Integer>();
			
			if (!q.isEmpty()) {
				int size = q.size();
				int prev = q.remove();
				q.add(prev);
				for (int i = 0; i < size - 1; i++) {
					int curr = q.remove();
					if (curr == prev) {
						s.push(curr);
					} else {
						q.add(curr);
						prev = curr;
					}
				}
				int unique = q.size();
				
				while (!s.isEmpty()) {
					q.add(s.pop());
				}
				for (int i = 0; i < unique; i++) {
					q.add(q.remove());
				}
				for (int i = 0; i < size - unique; i++) {
					s.push(q.remove());
				}
				while (!s.isEmpty()) {
					q.add(s.pop());
				}
			}
		}
		
		
6. One possible solution:

		public boolean equals(IntTree other) {
			return equals(overallRoot, other.overallRoot);
		}
		
		private boolean equals(IntTreeNode root1, IntTreeNode root2) {
			if (root1 == null || root2 == null)
				return root1 == null && root2 == null;
			else
				return root1.data == root2.data
					&& equals(root1.left, root2.left)
					&& equals(root1.right, root2.right);
		}
		
		
7. One possible solution:

		public static Map<String, Double> computeGrades(Map<String, Map<String, Integer>> scores,
		                                                Map<String, Integer> values) {
			Map<String, Double> grades = new TreeMap<String, Double>();
			
			for (String student : scores.keySet()) {
				double total = 0;
				double possible = 0;
				Map<String, Integer> studentScores = scores.get(student);
				for (String assign : studentScores.keySet()) {
					total += studentScores.get(assign);
					possible += values.get(assign);
				}
				
				grades.put(student, total / possible);
			}
			
			return grades;
		}
		
		
8. One possible solution: 

		public class ClockTime implements Comparable<ClockTime> {
			private int hours;
			private int minutes;
			private boolean isAm;

			public ClockTime(int hours, int minutes, boolean isAm) {
				this.hours = hours;
				this.minutes = minutes;
				this.isAm = isAm;
			}
			
			public String toString() {
				String result = "";
				result += hours + ":";
				if (minutes < 10) {
					result += "0";
				}
				result += minutes + " ";
				if (isAm) {
					result += "am";
				} else {
					result += "pm";
				}
				
				return result;
			}
			
			public int compareTo(ClockTime other) {
				if (this.isAm != other.isAm) {
					if (this.isAm) {
						return -1;
					} else {
						return 1;
					}
				} else if (this.hours != other.hours) {
					return (this.hours % 12) - (other.hours % 12);
				} else {
					return this.minutes - other.minutes;
				}
			}
		}
		
		
9. One possible solution:

		public void trim(int min, int max) {
			overallRoot = trim(overallRoot, min, max);
		}
		
		private IntTreeNode trim(IntTreeNode root, int min, int max) {
			if (root == null) {
				return root;
			} else if (root.data < min) {
				// root and entire left subtree cut
				return trim(root.right, min, max);
			} else if (root.data > max) {
				// root and entire right subtree cut
				return trim(root.left, min, max);
			} else {
				// root stays in; check subtrees
				root.left = trim(root.left, min, max);
				root.right = trim(root.right, min, max);
				return root;
			}
		}
		
		
10. One possible solution:

		public void duplicatePairs() {
			ListNode curr = front;
			while (curr != null && curr.next != null) {
				ListNode second = new ListNode(curr.next.data, curr.next.next);
				ListNode first = new ListNode(curr.data, second);
				
				curr.next.next = first;
				
				curr = curr.next.next.next.next;
			}
		}