<![CDATA[
CSE143X Key to Final, Autumn 2013 handout #38
1. Preorder traversal 0, 3, 2, 9, 4, 1, 6, 5, 7, 8
Inorder traversal 2, 9, 3, 0, 6, 1, 5, 4, 7, 8
Postorder traversal 9, 2, 3, 6, 5, 1, 8, 7, 4, 0
2. Two possible solutions appear below.
public int digitMatch(int x, int y) {
if (x < 0 || y < 0)
throw new IllegalArgumentException();
else if (x < 10 || y < 10) {
if (x % 10 == y % 10)
return 1;
else
return 0;
} else if (x % 10 == y % 10)
return 1 + digitMatch(x / 10, y / 10);
else
return digitMatch(x / 10, y / 10);
}
public int digitMatch(int x, int y) {
if (x < 0 || y < 0)
throw new IllegalArgumentException();
else {
int count = 0;
if (x % 10 == y % 10)
count++;
if (x >= 10 && y >= 10)
count+= digitMatch2(x / 10, y / 10);
return count;
}
}
3. Statement Output
------------------------------------------------------------
var1.method1(); Scoop 1
var2.method1(); Spoon 1/Cone 1
var3.method1(); Cone 1
var4.method1(); compiler error
var5.method1(); Scoop 1
var6.method1(); compiler error
var1.method2(); Cone 2/Scoop 1
var2.method2(); Cone 2/Spoon 1/Cone 1
var3.method2(); Cone 2/Cone 1
var4.method2(); compiler error
var5.method2(); Cone 2/Scoop 1
var6.method2(); compiler error
((Spoon)var1).method3(); compiler error
((Cup)var6).method3(); Cup 3
((Scoop)var4).method1(); runtime error
((Cone)var6).method2(); Cone 2/Cone 1
((Cone)var4).method1(); Spoon 1/Cone 1
((Scoop)var6).method3(); runtime error
((Scoop)var3).method3(); runtime error
((Scoop)var5).method3(); Scoop 3
4. One possible solution appears below.
public void reverseByN(Queue<Integer> q, int n) {
Stack<Integer> s = new Stack<Integer>();
int times = q.size() / n;
int extra = q.size() % n;
for (int i = 0; i < times; i++) {
for (int j = 0; j < n; j++)
s.push(q.remove());
while (!s.isEmpty())
q.add(s.pop());
}
for (int i = 0; i < extra; i++)
s.push(q.remove());
while (!s.isEmpty())
q.add(s.pop());
}
5. One possible solution appears below.
public void printLevel(int target) {
if (target < 1)
throw new IllegalArgumentException();
printLevel(overallRoot, target, 1);
}
private void printLevel(IntTreeNode root, int target, int level) {
if (root != null)
if (level == target)
System.out.println(root.data);
else {
printLevel(root.right, target, level + 1);
printLevel(root.left, target, level + 1);
}
}
6. One possible solution appears below.
public static int recordDate(Map<String, List<String>> dates,
String name1, String name2) {
if (!dates.containsKey(name1)) {
dates.put(name1, new LinkedList<String>());
}
if (!dates.containsKey(name2)) {
dates.put(name2, new LinkedList<String>());
}
dates.get(name1).add(0, name2);
dates.get(name2).add(0, name1);
int n = 0;
for (String s : dates.get(name1)) {
if (s.equals(name2)) {
n++;
}
}
return n;
}
7. One possible solution appears below.
public class TeamData implements Comparable<TeamData> {
private String name;
private int solved;
private int totalTime;
private int problems;
public TeamData(String name, int problems) {
this.name = name;
this.problems = problems;
this.totalTime = 0;
this.solved = 0;
}
public void success(int problem, int time) {
solved++;
totalTime += time;
}
public String toString() {
return name + " solved " + solved + " of " + problems + " in "
+ totalTime + " minutes";
}
public int solved() {
return solved;
}
public int time() {
return totalTime;
}
public double percentCorrect() {
return 100.0 * solved / problems;
}
public int compareTo(TeamData other) {
if (solved != other.solved)
return other.solved - solved;
else
return totalTime - other.totalTime;
}
}
8. One possible solution appears below.
public void makeFull() {
overallRoot = makeFull(overallRoot, 1);
}
private IntTreeNode makeFull(IntTreeNode root, int level) {
if (root != null) {
if (root.left == null && root.right != null) {
root = new IntTreeNode(-level, root, root.right);
root.left.right = null;
} else if (root.left != null && root.right == null) {
root = new IntTreeNode(-level, root.left, root);
root.right.left = null;
}
root.left = makeFull(root.left, level + 1);
root.right = makeFull(root.right, level + 1);
}
return root;
}
9. One possible solution appears below.
public void interleave(LinkedIntList other) {
if (front == null) {
front = other.front;
} else if (other.front != null) {
ListNode current1 = front;
ListNode current2 = other.front;
while (current1.next != null && current2.next != null) {
ListNode temp = current1.next;
current1.next = current2;
current2 = current2.next;
current1.next.next = temp;
current1 = temp;
}
if (current1.next == null)
current1.next = current2;
else {
current2.next = current1.next;
current1.next = current2;
}
}
other.front = null;
}
]]>