<![CDATA[
CSE143X Key to Final, Autumn 2021 handout #28
1. Preorder traversal 0, 3, 7, 4, 6, 2, 9, 1, 5, 8
Inorder traversal 4, 7, 6, 3, 0, 1, 9, 2, 8, 5
Postorder traversal 4, 6, 7, 3, 1, 9, 8, 5, 2, 0
2. One possible solution appears below.
public String undouble(String s) {
if (s.length() < 2) {
return s;
} else if (s.charAt(0) == s.charAt(1)) {
return s.charAt(0) + undouble(s.substring(2));
} else {
return s.charAt(0) + undouble(s.substring(1));
}
}
3. Statement Output
------------------------------------------------------------
var1.method2() Box 2
var2.method2() Jar 2
var3.method2() Cup 2/Box 2
var4.method2() Jar 2
var5.method2() compiler error
var6.method2() Pill 2
var1.method3() Box 2/Box 3
var2.method3() compiler error
var3.method3() Cup 2/Box 2/Box 3
var4.method3() Jar 2/Box 3
((Cup)var1).method1() runtime error
((Jar)var2).method1() Jar 1
((Cup)var3).method1() Cup 1
((Cup)var4).method1() runtime error
((Jar)var4).method2() Jar 2
((Box)var5).method2() Box 2
((Pill)var5).method3() compiler error
((Jar)var2).method3() Jar 2/Box 3
((Cup)var3).method3() Cup 2/Box 2/Box 3
((Cup)var5).method3() runtime error
4. One possible solution appears below.
public boolean isSorted(Stack<Integer> s) {
if (s.size() <= 1) {
return true;
} else {
Queue<Integer> q = new LinkedList<>();
int prev = s.pop();
q.add(prev);
boolean ok = true;
while (!s.isEmpty()) {
int next = s.pop();
if (prev < next) {
ok = false;
}
q.add(next);
prev = next;
}
while (!q.isEmpty()) {
s.push(q.remove());
}
while (!s.isEmpty()) {
q.add(s.pop());
}
while (!q.isEmpty()) {
s.push(q.remove());
}
return ok;
}
}
5. One possible solution appears below.
public static Set<Point> switchXY(Set<Point> points) {
Set<Point> result = new HashSet<>();
Iterator<Point> itr = points.iterator();
while (itr.hasNext()) {
Point p = itr.next();
if (p.getX() == p.getY()) {
itr.remove();
} else {
result.add(new Point(p.getY(), p.getX()));
}
}
return result;
}
6. One possible solution appears below.
public String toString() {
return toString(overallRoot);
}
private String toString(IntTreeNode root) {
if (root == null) {
return "empty";
} else if (root.left == null && root.right == null) {
return "" + root.data;
} else {
return "(" + root.data + ", " + toString(root.left)
+ ", " + toString(root.right) + ")";
}
}
7. 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<>());
}
if (!dates.containsKey(name2)) {
dates.put(name2, new LinkedList<>());
}
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;
}
8. One possible solution appears below.
class BookData implements Comparable<BookData> {
private String title;
private int reviews;
private double total;
public BookData(String title) {
this.title = title;
this.reviews = 0;
this.total = 0.0;
}
public void review(double rating) {
reviews++;
total += rating;
}
public double getRating() {
return total / reviews;
}
public String toString() {
return title + " " + getRating() + " (reviews: " + reviews + ")";
}
public int compareTo(BookData other) {
if (getRating() > other.getRating()) {
return -1;
} else if (getRating() < other.getRating()) {
return 1;
} else {
return other.reviews - reviews;
}
}
}
9. One possible solution appears below.
public void limitLeaves(int min) {
overallRoot = limitLeaves(overallRoot, min);
}
private IntTreeNode limitLeaves(IntTreeNode root, int min) {
if (root != null) {
root.left = limitLeaves(root.left, min);
root.right = limitLeaves(root.right, min);
if (root.left == null && root.right == null && root.data <= min) {
root = null;
}
}
return root;
}
10. One possible solution appears below.
public LinkedIntList removeAlternatePairs() {
LinkedIntList result = new LinkedIntList();
if (front != null && front.next != null) {
result.front = front;
front = front.next.next;
ListNode current1 = result.front.next;
ListNode current2 = front;
while (current2 != null && current2.next != null &&
current2.next.next != null &&
current2.next.next.next != null) {
current1.next = current2.next.next;
current2.next.next = current2.next.next.next.next;
current2 = current2.next.next;
current1 = current1.next.next;
}
current1.next = null;
}
return result;
}
]]>