<![CDATA[
Problem #1
Preorder traversal 7, 2, 3, 8, 4, 1, 9, 6, 0, 5
Inorder traversal 3, 8, 2, 4, 1, 7, 6, 9, 5, 0
Postorder traversal 8, 3, 1, 4, 2, 6, 5, 0, 9, 7
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
+------------+
| Mike |
+------------+
/ \
/ \
+------------+ +------------+
| Eleven | | Will |
+------------+ +------------+
/ \ /
/ \ /
+------------+ +------------+ +------------+
| Dustin | | Lucas | | Nancy |
+------------+ +------------+ +------------+
\
\
+------------+
| Steve |
+------------+
Only partial credit is 2 out of 4 points if just one node is in the wrong
place.
-------------------------------------------------------------------------------
Problem #3
Method Call Contents of Set Returned
-----------------------------------------------
mystery(grid, 0) [2, 4]
mystery(grid, 1) [4, 5, 6, 9]
mystery(grid, 3) [4, 5, 6]
1 pt for first problem
2 pt for second problem
2 pt for third problem
-1 for order error (just once for the entire question)
-1 for duplicates (just once for the entire question)
-1 for missing number
-1 for extra number
no subproblem can go negative
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 (could be an inner foreach or iterator loop over
the second set, but that requires a flag)
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: correct loop over s1 (not for-i-get), removing value if it is
not in s2 (concurrent modifcation is okay)
Problem #5
solution
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) + ")";
}
}
1 overall setup: correct public/private headers, public method passes
overallRoot to private method
2 base case for null
1 attempt: test for this case
1 correct: always returns "empty" for null with no NullPointerException
3 base case for leaf node
1 attempt: separate case that returns just root.data
1 correct leaf test
1 always returns correct string for a leaf (requires correct conversion to
string)
1 recursive calls on root.left and root.right (generous)
3 correctly computes string for general recursive case
1 attempt: separate case that puts together a string with parentheses and
results of recursive calls on left and right
2 correct (-1 if minor error like missing a plus or leaving out the comma)
Problem #6
solution
public static Map<Point, Set<Integer>> pointMap(List<Point> data) {
Map<Point, Set<Integer>> map = new HashMap<Point, Set<Integer>>();
for (int i = 0; i < data.size(); i++) {
Point p = data.get(i);
if (!map.containsKey(p)) {
map.put(p, new TreeSet<Integer>());
}
map.get(p).add(i);
}
return map;
}
1 header (static is okay)
2 construct and return proper map
1 reasonable attempt: constructing a map of points to something involving
ints (doesn't have to be a list)
1 all correct: correct generics, map is HashMap, map is returned, must have
() in call to new
1 correct loop over list of points (foreach or size/get, computing index)
1 correct test for whether next point is already in the map
2 new lists: adds a new list to map when new point is seen (can't happen every
time)
1 reasonable attempt: call on add or put with a new list or set of ints
1 all correct: correct generics, correct call on put, list is either
Arraylist or LinkedList, must have () in call to new
3 adds to lists: adds each index to the appropriate list
1 reasonable attempt: call on add or put with both point and index
1 better attempt: calling get on point to add/put word
1 all correct (works in all cases, no free syntax errors)
notes: No penalty for calling put multiple times on the same point/list pair
We are picky about ()'s on constructing, but don't take it off twice.
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 add(IntTree other) {
overallRoot = add(overallRoot, other.overallRoot);
}
private IntTreeNode add(IntTreeNode root1, IntTreeNode root2) {
if (root2 != null) {
if (root1 == null) {
root1 = new IntTreeNode(0, null, null);
}
root1.data += root2.data;
root1.left = add(root1.left, root2.left);
root1.right = add(root1.right, root2.right);
}
return root1;
}
1 overall setup: public header (return is not okay) and private header with a
root parameter and public method calls private method passing it overallRoot
5 used x = change(x) on root or equivalent (give equivalent to question 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 right are like this)
1 returns root correctly in all cases where root doesn't change
3 base case for root2 == null
1 attempt (tested either root1 or root2 for null)
2 correct: requires test, no NullPointerException when root2 is null, first
tree not changed in this case (requires root2 parameter)
6 constructs a new node when root1 is null (requires root2 parameter)
1 reasonable attempt to test for this case
1 correctly constructs a new node for this case
2 new node ends up with correct data value (either initialed to root2.data
with no later addition or initialized to 0 with a later addition)
2 new node ends is constructed with null values for left and right (instead
of, say, copies of root2's left and right)
3 recurse on left and right
1 attempt (at least one correct call passing both root parameters or two
calls passing a single root parameter)
2 correct: 2 correct calls that pass two root parameters and recursion
occurs in both cases (existing node, new node)
2 adds root2.data to root1.data when root2 is not null or constructs a new node
that has the sum to replace root1 (requires root2 parameter)
Note: notice that if they have only one root parameter, they can get at most 8
points:
1 overall setup
5 x = change(x)
1 base case attempt
1 recurse on left and right attempt
If they call 0-argument or 1-argument node constructor, that is a syntax error
first syntax error is free, then -1 per syntax category, max -2
Problem #9
solutions
// like switchPairs, one temp, 3 assignments to .next in loop
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;
}
}
}
// solution that changes just 2 .next fields in the loop with a final
// .next set after the loop
public void switchPairsOfPairs() {
if (front != null && front.next != null &&
front.next.next != null && front.next.next.next != null) {
ListNode current = front.next.next;
ListNode temp1 = current.next.next;
current.next.next = front;
front = current;
current = current.next.next.next;
while (temp1 != null && temp1.next != null &&
temp1.next.next != null &&
temp1.next.next.next != null) {
ListNode temp2 = temp1.next.next;
ListNode temp3 = temp1;
temp1 = temp2.next.next;
temp2.next.next = temp3;
current.next = temp2;
current = temp2.next.next.next;
}
current.next = temp1;
}
}
// solution with two temps
public void switchPairsOfPairs() {
if (front != null && front.next != null &&
front.next.next != null && front.next.next.next != null) {
ListNode temp1 = front.next.next;
ListNode temp2 = temp1.next.next;
temp1.next.next = front;
front.next.next = temp2;
ListNode current = front.next;
front = temp1;
while (current.next != null && current.next.next != null &&
current.next.next.next != null &&
current.next.next.next.next != null) {
temp1 = current.next.next.next;
temp2 = temp1.next.next;
temp1.next.next = current.next;
current.next.next.next = temp2;
current.next = temp1;
current = current.next.next.next.next;
}
}
}
// recursive solution
public void switchPairsOfPairs() {
front = switchPairsOfPairs(front);
}
public ListNode switchPairsOfPairs(ListNode list) {
if (list != null && list.next != null &&
list.next.next != null && list.next.next.next != null) {
ListNode temp = list.next.next;
list.next.next = temp.next.next;
temp.next.next = list;
list = temp;
list.next.next.next.next =
switchPairsOfPairs(list.next.next.next.next);
}
return list;
}
1 header (non-void okay if there is a return that is consistent)
4 simples cases: can't get these for no code...each requires a test
1 length 0 case: does nothing and doesn't throw an exception
1 length 1 case: does nothing and doesn't throw an exception
1 length 2 case: does nothing and doesn't throw an exception
1 length 3 case: does nothing and doesn't throw an exception
2 generous pattern match
1 using a "current" variable in a loop to keep track of a position in the
list
1 resetting at least three "next" fields in a loop or resetting two in a
loop and resetting one after the loop
13 other specific cases
3 length 4
1 length 5
1 length 6
1 length 7
1 length 8
1 length 9
1 length 10
1 length 11
1 length 12
1 length 16
1 length 20
notes:
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. A single correction would involve adding or
deleting a single line of code like curr=curr.next or changing a test for
something like curr!=null to be curr.next!=null (this could be a double-change
to parallel curr1/curr2). Another change to consider is calling a special
method included in the grading program called switchFronts that switches the
fronts of the lists. Any such change costs 5 points and we are willing to make
only ONE such change.
Another example of a change would be if they use a name like "curr" when they
have variables with names like "curr1" and "curr2", so we don't know which one
they mean. That would require a 5-point charge.
Any O(n^2) solutions or odd solutions (new nodes, changing data) go to the
question leader.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011