<![CDATA[
Problem #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 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
2. +------------+
| Pride |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Envy | | Sloth |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Anger | | Greed |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Gluttony | | Lust |
+------------+ +------------+
Only partial credit is 2 out of 4 points if just one node is in the wrong
place.
Problem #3
list1: [b, l, u, e]
list2: [s, p, o, t]
map returned: {b=s, e=t, l=p, o=u, p=l, s=b, t=e, u=o}
list1: [k, e, e, p]
list2: [s, a, f, e]
map returned: {a=e, e=p, f=e, k=s, p=e, s=k}
list1: [s, o, b, e, r]
list2: [b, o, o, k, s]
map returned: {b=o, e=k, k=e, o=b, r=s, s=r}
1 pt for first problem
2 pt for second problem
2 pt for third problem
-1 for each error: missing pair, extra pair, duplicate pair, wrong pair, wrong
order
note: they should not lose more than one point because of order problems
Problem #4
solution
public void retainAll(Set<Integer> s1, Set<Integer> s2) {
Iterator<Integer> i = s1.iterator();
while (i.hasNext()) {
if (!s2.contains(i.next())) {
i.remove();
}
}
}
1 header (static is okay)
4 iterator approach
1 constructs iterator properly
1 loop that obtains each iterator value once
1 correct test for remove
1 correct remove using iterator
note: they lose construct/test points if they switch s1/s2
2 foreach loop or for-i-get approach that calls s1.remove
1 attempt (loop over one set or the other, calling s1.remove(value))
1 correct: loop over s1, removing value if it is not in s2
nested loop approach
1 correct first iterator before outer loop
1 correct second iterator inside outer loop and outer loop correct
1 correct inner loop to find value using flag
1 correct remove after find (lose this if they aren't using a flag approach
to remove after looking at all of the other values)
Problem #5
solution
public int evenBranches() {
return evenBranches(overallRoot);
}
private int evenBranches(IntTreeNode root) {
if (root == null)
return 0;
else if (root.left == null && root.right == null)
return 0;
else if (root.data % 2 == 0)
return 1 + evenBranches(root.left) + evenBranches(root.right);
else
return evenBranches(root.left) + evenBranches(root.right);
}
1 correct public/private headers
1 public method returns result of calling private method passing overallRoot
2 base case for null
1 attempt: test for this case
1 correct: always returns 0 for null with no NullPointerException
2 leaf case
1 attempt to test this case and exclude it from the sum
1 correct: always returns 0 for a leaf node
4 recursive case
1 attempt: returns count(left) + count(right)
1 tests odd/even data (requires attempt)
2 correct: includes 1 for even, 0 for odd with correct recursive calls
Problem #6
solution
public static Map<Point, String> recordMoves(List<Move> moves,
List<String> graveyard) {
Map<Point, String> result = new HashMap<Point, String>();
for (Move m : moves) {
Point p = new Point(m.getX(), m.getY());
if (result.containsKey(p)) {
graveyard.add(result.get(p));
}
result.put(p, m.getName());
}
return result;
}
2 header (-1 per error, static is okay)
2 construct and return proper map
1 reasonable attempt: trying to construct a map of points to strings
1 all correct (correct generics, correct return, map is HashMap, used Map
interface for variable, must have () in call to new)
2 correctly loop over list of moves
1 reasonable attempt to loop over list of moves
1 all correct (correctly obtains each Move object in proper sequence)
2 construct new Point and add to map with name
1 reasonable attempt to construct Point using x/y of move
1 correctly adds an entry to the map for this Point/getName
2 update graveyard
1 reasonable attempt to handle this case
1 correct
Problem #7
solutions
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 USCurrency add(USCurrency other) {
return new USCurrency(dollars() + other.dollars(),
cents() + other.cents());
}
public USCurrency subtract(USCurrency other) {
return new USCurrency(dollars() - other.dollars(),
cents() - other.cents());
}
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 USCurrency add(USCurrency other) {
return new USCurrency(dollars + other.dollars,
cents + other.cents);
}
public USCurrency subtract(USCurrency other) {
return new USCurrency(dollars - other.dollars,
cents - other.cents);
}
public int compareTo(USCurrency other) {
return dollars * 100 + cents - other.dollars * 100 - other.cents;
}
}
1 class header
2 fields (okay to have extra field(s), -1 if any aren't private, -2 if they are
using a totalCents approach and have no field)
1 constructor: correct header, sets fields appropriately
4 proper conversion of dollars/cents
dollars/cents approach: correctly changes dollars/cents in constructor or
computes in dollars/cents methods
1 attempt: recognized this issue and attempted to correct
1 correct when both positive or both negative
2 correct in all cases
total cents approach: computing total cents and converting in dollars/cents
methods
1 correctly computes total cents
1 attempt to convert: using %10 and /10 to compute separate values in
dollars/cents methods
2 correct
1 dollars method (correct header, appropriate return value, no double jeopardy
with conversion)
1 cents method (correct header, appropriate return value no double jeopardy
with conversion)
4 toString
1 separate code for negative values based on a test or use of Math.abs
1 separate case for single digit cents or use of mod to generate two
individual digits
2 all correct (-1 if minor formatting error)--note that the totalCents
solutions can lose this if they have incorrect expressions even if they
lost the points under conversion (but no double jeopardy if they call the
dollars and cents methods)
3 add and subtract methods
1 reasonable attempt for add
1 reasonable attempt for subtract
1 both correct (totalCents solutions can lose this if they have incorrect
expressions instead of calling dollars and cents methods)
3 compareTo
1 attempt: correct header and using totalCents or dollars/cents to return a
value
1 either compare total cents or they compare dollars first, cents second
1 all correct
Problem #8
solution
public void stretch() {
overallRoot = stretch(overallRoot);
}
private IntTreeNode stretch(IntTreeNode root) {
if (root != null) {
root.left = stretch(root.left);
root.right = stretch(root.right);
if (root.left != null && root.right == null)
root = new IntTreeNode(1, root, null);
else if (root.left == null && root.right != null)
root = new IntTreeNode(1, null, root);
}
return root;
}
1 public header
1 private header with a root parameter and public method calls private method
passing it overallRoot
5 used x = change(x) (if you think they didn't need it, show to quest leader)
1 overallRoot = recurse(overallRoot)
1 private method has return type IntTreeNode
1 root.left = recurse(root.left) (at least one && all left are like this)
1 root.right = recurse(root.right) (at least one && all left are like this)
1 private method returns an IntTreeNode in at least one case
1 basic idea: testing for single child
STOP HERE if they don't get single-child test attempt
3 base case when root = null for nonempty trees
1 attempt (tested this case)
2 correct (tree not changed in this case, no NullPointerException)
4 recursively stretching subtrees
1 attempt: calls on stretch(root.left) and stretch(root.right)
3 correct: stretch in all appropriate cases, no order problems
5 adding new nodes
1 correct tests for single-child (has to exclude leaf case)
2 construct a new node in these cases (requires test attempt)
1 call on node constructor is correct (includes 1, places old node in
correct place)
1 always reset root to new list node (or returns it)
notes:
attempt to change data fields or iterative go to Question Leader
Problem #9
solutions
public void weave(LinkedIntList other) {
if (front == null) {
front = other.front;
other.front = null;
} 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;
}
}
1 header
2 works for empty list
1 attempt: tested for this case and attempt to reset front
1 correct (both fronts reset properly)
1 works (does nothing) when other list is empty based on a test
3 generous pattern matching
1 current variable moved forward in a loop
1 second current variable moved forward in a loop
1 two <blah>.next assignments in loop (might be one each in an if/else)
2 sets list2.front to null after a loop (could be in an if inside the loop)
11 specific cases (1 point each)
1 lengths 1, 1
1 lengths 2, 2
1 lengths 3, 3
1 lengths 1, 2
1 lengths 2, 1
1 lengths 2, 3
1 lengths 3, 2
1 lengths 3, 4
1 lengths 4, 3
1 lengths 6, 9
1 lengths 12, 8
notes:
Parameters of type ListNode go to Question Leader.
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.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011