<![CDATA[
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;
}
}
}
]]>