<![CDATA[
Problem #1
Preorder traversal 3, 5, 9, 6, 0, 2, 7, 8, 4, 1
Inorder traversal 3, 0, 6, 2, 9, 5, 4, 8, 7, 1
Postorder traversal 0, 2, 6, 9, 4, 8, 1, 7, 5, 3
2 points each, only partial credit is if the sequence matches the right answer
other than one single error (missing number, wrong number, transposed pair)
problem #2
+------------+
| Ginger |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Gilligan | | Professor |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Lovey | | Skipper |
+------------+ +------------+
\ \
\ \
\ \
+------------+ +------------+
| Maryann | | Thurston |
+------------+ +------------+
Only partial credit is 2 out of 4 points if just one node is in the wrong
place.
Problem #3
Two-Dimensional Array Contents of List Returned
------------------------------------------------------------------
[[0, 1], [2, 3]] [1]
[[0, 1, 2], [3, 4, 5], [6, 7, 8]] [2, 3, 5, 6]
[[3, 4], [1, 2, 3], [], [5, 6]] [0, 1, 4]
1 pt for first row
2 pt for second row
2 pt for third row
-1 for each error: missing number, extra number, transposed pair
partial credit solutions (each worth 3 pts--1 pt each):
[-1, 1] [1, 2] [0]
[-1, 0, 2, 3, 5, 6] [2, 3, 4, 5, 6, 7] [1, 2, 4, 5]
[2, 0, 1, 4] [0, 1, 2, 4, 5] [-1, 0, 3]
Problem #4
solutions
public boolean equals(Set<Integer> s1, Set<Integer> s2) {
for (int n : s1) {
if (!s2.contains(n))
return false;
}
return s1.size() == s2.size();
}
public static boolean equals(Set<Integer> s1, Set<Integer> s2) {
for (int n : s1) {
if (!s2.contains(n))
return false;
}
for (int n : s2) {
if (!s1.contains(n))
return false;
}
return true;
}
public static boolean equals(Set<Integer> s1, Set<Integer> s2) {
return s1.containsAll(s2) && s2.containsAll(s1);
}
public static boolean equals(Set<Integer> s1, Set<Integer> s2) {
return s1.containsAll(s2) && s1.size() == s2.size();
}
1 header (static is okay)
2 verifying that one set contains the other
1 attempt (trying to iterate over one set, seeing if other contains the
values or containsAll)
1 iteration is correct (foreach or iterator), correct test, return false
1 verifying other direction (second loop or second containsAll or size
comparison)
1 returns true if no differences found
Problem #5
solutions
public int countMultiples(int value) {
if (value == 0)
throw new IllegalArgumentException();
return countMultiples(overallRoot, value);
}
private int countMultiples(IntTreeNode root, int value) {
if (root == null)
return 0;
else {
int sum = countMultiples(root.left, value) +
countMultiples(root.right, value);
if (root.data % value == 0)
return 1 + sum;
else
return sum;
}
}
-------------------------------------------------------------------------
public int countMultiples(int value) {
if (value == 0)
throw new IllegalArgumentException();
return countMultiples(overallRoot, value, 0);
}
private int countMultiples(IntTreeNode root, int value, int count) {
if (root != null) {
if (root.data % value == 0)
count++;
count = countMultiples(root.left, value, count);
count = countMultiples(root.right, value, count);
}
return count;
}
1 overall setup: correct public/private headers, public returns result of
private, private passed overallRoot
1 exception handled correctly
2 base case when root == null
1 reasonable attempt to test for this case
1 correct (returns 0 whenever root is null)
2 test for multiple
1 attempt
1 correct
4 computation (requires "test for multiple" attempt)--2 approaches:
4 computation without counter (2 parameters)
1 correct for non-multiple (returns sum of recursive calls)
1 attempt for multiple (returns 1 and/or sum of recursive calls)
2 correct for multiple (returns 1 + sum of recursive calls)
4 computation with counter parameter (3 parameters)
1 increment counter for multiple and sometimes makes recursive calls on
left and right
1 always make recursive calls on left and right for non-null trees
2 correct (something like x=change(x); only partial credit would be for
something truly minor like a missing return)
Problem #6
solution
public Map<Point, Integer> pointCount(List<Point> list) {
Map<Point, Integer> result = new HashMap<Point, Integer>();
for (Point p : list) {
if (!result.containsKey(p))
result.put(p, 1);
else
result.put(p, result.get(p) + 1);
}
return result;
}
1 header (static is okay)
2 construct and return proper map
1 reasonable attempt: trying to construct a map of points to integers
1 all correct (correct generics, correct return, map is HashMap
3 efficiently loop over list
1 reasonable attempt (bracket notation with for loop is an attempt)
1 correctly iterates over list
1 efficient: iterator or foreach
2 add a new entry to map when Point is first seen
1 reasonable attempt to test for this case
1 all correct
2 increments count if Point has been seen
1 reasonable attempt
1 all correct
Problem #7
solution
public class FoodData implements Comparable<FoodData> {
private String name;
private double fat;
private double carbs;
private double protein;
public FoodData(String name, double fat, double carbs,
double protein) {
if (fat < 0 || carbs < 0 || protein < 0)
throw new IllegalArgumentException();
this.name = name;
this.fat = fat;
this.carbs = carbs;
this.protein = protein;
}
public String getName() {
return name;
}
public double getCalories() {
return 9 * fat + 4 * (carbs + protein);
}
public double percentFat() {
if (getCalories() == 0)
return 0.0;
else
return 100.0 * (9 * fat / getCalories());
}
public String toString() {
return name + ": " + fat + "g fat, " + carbs +
"g carbohydrates, " + protein + "g protein";
}
public int compareTo(FoodData other) {
double difference = percentFat() - other.percentFat();
if (difference < 0)
return -1;
else if (difference > 0)
return 1;
else
return name.compareTo(other.name);
}
}
1 class header
4 fields (1 point each, -1 if not private, okay to have extra field(s) for
calories or fat calories or percent fat)
3 constructor
1 correct header
1 exception
1 sets four fields correctly
1 getName correct
2 getCalories correct
1 attempt
1 correct
3 percentFat correct (don't have to worry about getCalories() == 0)
1 attempt
2 correct (-1 if close--e.g., missing the *100)
2 toString correct
1 includes all four fields
1 correct format
4 compareTo
1 primary comparison is for some kind of fat comparison
1 correctly computes difference of percent fat and returns int (using
if/else or (int)Math.signum; hard to get this unless they make calls on
percentFat)
1 puts lower percent fat first
1 all other aspects correct (header, alphabetical name comparison when
percentFat equal)
Problem #8
solution
public void makeFull() {
overallRoot = makeFull(overallRoot);
}
private IntTreeNode makeFull(IntTreeNode root) {
if (root != null) {
root.left = makeFull(root.left);
root.right = makeFull(root.right);
if (root.left == null && root.right != null)
root = root.right;
else if (root.left != null && root.right == null)
root = root.left;
}
return root;
}
2 overall setup
1 public/private headers (private needs root)
1 public calls private passing overallRoot
3 root == null case
1 attempt
2 correct (-1 if only problem is overallRoot)
3 Eliminating 1-child nodes
1 reasonable attempt to replace root with non-null child (other child null)
1 correctly resets root for one of the two 1-child cases
1 correctly resets root for other 1-child case
STOP HERE if they don't get 1-child node attempt (don't be shy about asking
question leader if something qualifies as attempt)
5 x = change(x) used correctly
1 return type for private method
1 return root in private
1 overallRoot = makeFull(overallRoot)
1 root.left = makeFull(root.left)--all such calls
1 root.right = makeFull(root.right)--all such calls
2 2-child case works (recursive calls)
2 leaf case works (unchanged)--requires tests
3 recursive calls are made for 1-child cases
1 exist
2 before assignment or as part of assignment (root = makeFull(root.left))
Problem #9
solution
public void reorder3() {
if (front != null && front.next != null) {
ListNode temp = front;
front = temp.next;
temp.next = front.next;
front.next = temp;
ListNode current = temp.next;
while (current != null && current.next != null &&
current.next.next != null) {
temp = current.next;
current.next = temp.next;
temp.next = current.next.next;
current.next.next = temp;
current = temp.next;
}
}
}
1 header
1 works (does nothing) for empty list (requires test)
1 works (does nothing) for 1-element list (requires test)
6 generous pattern matching
3 front of list (before loop)
1 temp = <something>
1 front = <something>
2 2 of <something>.next = <something>
3 middle of list (requires loop)
1 temp = <something>
1 first <something>.next = <something>
1 2 more <something>.next = <something>
11 specific cases
4 front of list
2 2-element
2 3-element
7 longer lists
1 4-element
1 5-element
1 6-element
2 8-element
2 9-element
Recursive solutions go to question leader.
Notes:
max of 18 if you know if it has a mistake (probably don't need this rule)
We have a general rule that if you can fix one problem and it suddenly works,
then we make that fix and charge them 5 points. If this gives someone a higher
score, you can grade it that way. But don't spend too much time trying to
figure out their mistakes.
-------------------------------------------------------------------------------
recursive solution:
public void reorder3() {
front = reorder3(front);
}
private ListNode reorder3(ListNode link) {
if (link != null && link.next != null) {
ListNode temp = link;
link = temp.next;
temp.next = link.next;
link.next = temp;
if (temp.next != null)
temp.next.next = reorder3(temp.next.next);
}
return link;
}
public void reorder3() {
front = reorder3(front);
}
private ListNode reorder3(ListNode list) {
if (list != null && list.next != null) {
ListNode temp = list.next;
list.next = temp.next;
temp.next = list;
list = temp;
if (list.next.next != null)
list.next.next.next = reorder3(list.next.next.next);
}
return list;
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011