CSE143X Key to Final, Autumn 2018 handout #25 1. Preorder traversal 2, 0, 5, 1, 7, 6, 3, 4, 9, 8 Inorder traversal 1, 5, 0, 7, 6, 2, 3, 9, 4, 8 Postorder traversal 1, 5, 6, 7, 0, 9, 8, 4, 3, 2 2. One possible solution appears below. public int weave(int x, int y) { if (x < 0 || y < 0) { throw new IllegalArgumentException(); } if (x == 0 && y == 0) { return 0; } else { return 100 * weave(x / 10, y / 10) + 10 * (x % 10) + y % 10; } } 3. Statement Output ------------------------------------------------------------ var1.method1(); Blue 1/Blue 2 var2.method1(); Green 1 var3.method1(); compiler error var4.method1(); Green 1 var1.method2(); Blue 2 var2.method2(); Red 2/Blue 2 var3.method2(); compiler error var4.method2(); Red 2/Blue 2 var1.method3(); compiler error var2.method3(); Green 3 var3.method3(); compiler error var4.method3(); compiler error ((Blue)var3).method1(); Blue 1/White 2 ((Red)var3).method2(); White 2 ((White)var3).method3(); White 3 ((White)var4).method3(); runtime error ((Green)var5).method3(); runtime error ((Red)var5).method1(); Blue 1/Red 2/Blue 2 ((Blue)var6).method3(); compiler error ((Green)var6).method3(); runtime error 4. One possible solution appears below. public static void mirrorCollapse(Stack<Integer> s) { Queue<Integer> q = new LinkedList<Integer>(); while (!s.isEmpty()) { q.add(s.pop()); } int oldSize = q.size(); for (int i = 0; i < oldSize / 2; i++) { s.push(q.remove()); } if (oldSize % 2 == 1) { q.add(q.remove()); } while (!s.isEmpty()) { q.add(q.remove() + s.pop()); } while (!q.isEmpty()) { s.push(q.remove()); } } 5. One possible solution appears below. public void recordTrip(Map<String, Set<String>> trips, String person, String place) { if (!trips.containsKey(person)) { trips.put(person, new TreeSet<String>()); } trips.get(person).add(place); } 6. One possible solution appears below. public List<Integer> inorderList() { List<Integer> result = new ArrayList<Integer>(); inorderList(result, overallRoot); return result; } private void inorderList(List<Integer> result, IntTreeNode root) { if (root != null) { inorderList(result, root.left); result.add(root.data); inorderList(result, root.right); } } 7. One possible solution appears below. public Set<Point> removePoints(Map<Integer, List<Point>> points, int n) { Set<Point> removed = new HashSet<Point>(); if (points.containsKey(n)) { Iterator<Point> itr = points.get(n).iterator(); while (itr.hasNext()) { Point p = itr.next(); if (p.getX() < p.getY()) { itr.remove(); removed.add(p); } } } return removed; } 8. Two possible solutions appear below. public class USCurrency implements Comparable<USCurrency> { private int totalCents; public USCurrency(int dollars, int cents) { totalCents = dollars * 100 + cents; } public int dollars() { return totalCents / 100; } public int cents() { return totalCents % 100; } public String toString() { int cents = Math.abs(totalCents); String s = cents / 100 + "." + cents % 100 / 10 + cents % 10; if (totalCents < 0) { return "-\$" + s; } else { return "\$" + s; } } public int compareTo(USCurrency other) { return totalCents - other.totalCents; } } public class USCurrency implements Comparable<USCurrency> { private int dollars; private int cents; public USCurrency(int dollars, int cents) { int totalCents = 100 * dollars + cents; this.dollars = totalCents / 100; this.cents = totalCents % 100; } public int dollars() { return dollars; } public int cents() { return cents; } public String toString() { String s = Math.abs(dollars) + "."; if (Math.abs(cents) < 10) { s += "0" + Math.abs(cents); } else { s += Math.abs(cents); } if (dollars < 0 || cents < 0) { return "-\$" + s; } else { return "\$" + s; } } public int compareTo(USCurrency other) { return dollars * 100 + cents - other.dollars * 100 - other.cents; } } 9. One possible solution appears below. public void limitPathSum(int max) { overallRoot = limitPathSum(overallRoot, max); } private IntTreeNode limitPathSum(IntTreeNode root, int max) { if (root != null) { if (root.data > max) { root = null; } else { root.left = limitPathSum(root.left, max - root.data); root.right = limitPathSum(root.right, max - root.data); } } return root; } 10. One possible solution appears below. public void switchPairsOfPairs() { if (front != null && front.next != null && front.next.next != null && front.next.next.next != null) { ListNode current = front.next.next; front.next.next = current.next.next; current.next.next = front; front = current; current = current.next.next.next; while (current.next != null && current.next.next != null && current.next.next.next != null && current.next.next.next.next != null) { ListNode temp = current.next.next.next; current.next.next.next = temp.next.next; temp.next.next = current.next; current.next = temp; current = temp.next.next.next; } } }
Stuart Reges
Last modified: Wed Dec 19 13:28:28 PST 2018