<![CDATA[
Problem #1
Preorder traversal 2, 7, 9, 0, 5, 3, 6, 1, 4, 8
Inorder traversal 9, 7, 5, 0, 3, 2, 6, 4, 1, 8
Postorder traversal 9, 5, 3, 0, 7, 4, 8, 1, 6, 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
+------------+
| Legolas |
+------------+
/ \
/ \
/ \
+-----------+ +---------+
| Frodo | | Sam |
+-----------+ +---------+
/ \ /
/ \ /
/ \ /
+-------------+ +-----------+ +-----------+
| Aragorn | | Gimli | | Merry |
+-------------+ +-----------+ +-----------+
\ \
\ \
\ \
+-------------+ +------------+
| Boromir | | Pippin |
+-------------+ +------------+
Only partial credit is 2 out of 4 points if just one node is in the wrong
place.
Problem #3
3. Two-Dimensional Array Contents of List Returned
---------------------------------------------------------------------
[[1, 2, 3], [4, 5, 6]] [8, 17]
[[3, 4], [1, 2, 3], [], [5, 6]] [4, 8, 0, 6]
[[1, 2, 3], [4, 5, 6], [7, 8, 9]] [8, 17, 26]
1 pt for first problem
2 pt for second problem
2 pt for third problem
-1 for each error: missing number, extra number, wrong number
Problem #4
solution
public Map<Integer, Integer> convert(int[] list) {
Map<Integer, Integer> result = new TreeMap<Integer, Integer>();
for (int i = 0; i < list.length; i++) {
if (list[i] != 0) {
result.put(i, list[i]);
}
}
return result;
}
1 correct header (static is okay)
2 construct and return a new map
1 reasonable attempt to construct a new map (at least 2 of: map is
<Integer, Integer> or <int, int>, it's a TreeMap, they return it)
1 all correct (including Map interface for variable)
2 traverse array, populating map
1 reasonable attempt (at least 2 of these are correct: traverse array, test
for 0, add to map)
1 all correct
Note: missing () in call to new can be a free syntax error if there are no
other syntax errors
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 Map<Point, Integer> sumStrings(Map<String, Point> data) {
Map<Point, Integer> result = new HashMap<Point, Integer>();
for (String s : data.keySet()) {
Point p = data.get(s);
if (!result.containsKey(p)) {
result.put(p, s.length());
} else {
result.put(p, result.get(p) + s.length());
}
}
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, used Map
interface for variable, must have () in call to new)
2 loop over map passed as a parameter
1 reasonable attempt to map over key set of the parameter
1 all correct (iterator or foreach over key set, obtain String for each
key)
2 add a new entry to map when Point is first seen
1 reasonable attempt to test for this case
1 all correct (tests whether this key is there, adds an entry if it is new,
associates it with the length of the current string)
3 adds current String length if Point has been seen before
1 reasonable attempt to test for this case and do something different than
the case where it's new
1 reasonable attempt to get the old value, add something to it, and put it
back into the map
1 all correct (requires use of length method for the String)
Problem #7
solution
public class TimeSpan implements Comparable<TimeSpan> {
private int totalSeconds;
public TimeSpan(int hours, int minutes, int seconds) {
if (hours < 0 || minutes < 0 || seconds < 0) {
throw new IllegalArgumentException();
}
totalSeconds = seconds + 60 * (minutes + 60 * hours);
}
public int hours() {
return totalSeconds / 3600;
}
public int minutes() {
return totalSeconds % 3600 / 60;
}
public int seconds() {
return totalSeconds % 60;
}
public int totalSeconds() {
return totalSeconds;
}
public String toString() {
return hours() + ":" + minutes() / 10 + minutes() % 10 + ":" +
seconds() / 10 + seconds() % 10;
}
public TimeSpan add(TimeSpan other) {
TimeSpan result = new TimeSpan(0, 0, 0);
result.totalSeconds = totalSeconds + other.totalSeconds;
return result;
}
public int compareTo(TimeSpan other) {
return this.totalSeconds - other.totalSeconds;
}
}
Criteria for totalSeconds solution
1 class header
1 field (okay to have extra field(s))
4 constructor
1 correct exception
1 initialize totalSeconds to some combination of hours/minutes/seconds
2 all correct other than exception (-1 if minor error in computation of
total seconds)
5 hours/minutes seconds methods
2 methods are declared properly and return something (-1 per wrong method)
1 seconds computed correctly
1 minutes computed correctly
1 hours computed correctly
note: no double jeopardy (e.g., if minutes computation depends on seconds
computation, don't take off for the same mistake twice)
1 totalSeconds method
4 toString
1 reasonable attempt (exists, includes hours, minutes, seconds)
1 all correct ignoring leading zeros
1 adds leading zero to minutes if needed
1 adds leading zero to seconds if needed
2 add method
1 reasonable attempt
1 correct
2 compareTo
1 attempt: compares totalSeconds of each
1 correct
public class TimeSpan implements Comparable<TimeSpan> {
private int hours, minutes, seconds;
public TimeSpan(int hours, int minutes, int seconds) {
if (hours < 0 || minutes < 0 || seconds < 0) {
throw new IllegalArgumentException();
}
int total = seconds + 60 * (minutes + 60 * hours);
this.seconds = total % 60;
this.minutes = total / 60 % 60;
this.hours = total / 3600;
}
public int hours() {
return hours;
}
public int minutes() {
return minutes;
}
public int seconds() {
return seconds;
}
public int totalSeconds() {
return seconds + 60 * (minutes + 60 * hours);
}
public String toString() {
return hours + ":" + minutes / 10 + minutes % 10 + ":" +
seconds / 10 + seconds % 10;
}
public TimeSpan add(TimeSpan other) {
return new TimeSpan(hours + other.hours, minutes + other.minutes,
seconds + other.seconds);
}
public int compareTo(TimeSpan other) {
if (hours != other.hours)
return hours - other.hours;
else if (minutes != other.minutes)
return minutes - other.minutes;
else
return seconds - other.seconds;
}
}
Criteria for hours/minutes/seconds solution
1 class header
2 fields (-1 once if not private, okay to have extra field(s))
2 constructor
1 correct exception
1 correct header and initialize fields ignoring illegal minutes/seconds
3 fix illegal minutes/seconds
1 attempt: fix at least one problem once
2 correct: fix it everywhere correctly (typically just in constructor, but
make sure that add does not cause a problem)
2 hours/minutes seconds methods (-1 per missing or incorrect method)
2 totalSeconds method
1 attempt: exists, attempt to compute total seconds
1 correct
4 toString
1 reasonable attempt (exists, includes hours, minutes, seconds)
1 all correct ignoring leading zeros
1 adds leading zero to minutes if needed
1 adds leading zero to seconds if needed
2 add method
1 reasonable attempt
1 correct
2 compareTo
1 attempt: uses some combination of hours/minutes/seconds or call on
totalSeconds to compute result
1 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);
root1.data += root2.data;
root1.left = add(root1.left, root2.left);
root1.right = add(root1.right, root2.right);
}
return root1;
}
1 public header
1 overall setup: private header with at least one 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
2 base case for root1 == null
1 attempt (tested this case)
1 correct: requires test, no NullPointerException, tree not changed in this
case
5 construct a new node when root2 is null (requires root2 parameter)
1 tested for this case
2 correctly constructs a new node for this case
2 all correct (new node is constructed that ends up storing root2.data)
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)
3 adds root2.data to root1.data when root2 is not null (requires root2
parameter)
1 test for this case
2 correct (adds root2.data to root1.data in this case, lose these points if
they construct a new node instead)
Note: notice that if they have only one root parameter, they can get at most 10
points:
1 public header
1 overall setup
5 x = change(x)
2 base case for root1 == null
1 recurse on left and right attempt
Problem #9
solutions
// builds up two lists that it puts together at the end
public void rearrange() {
if (front != null && front.next != null) {
ListNode sub1 = front;
ListNode sub1Back = front;
ListNode sub2 = front.next;
ListNode sub2Back = sub2;
front.next = null;
ListNode current = sub2.next;
boolean list1 = true;
while (current != null) {
ListNode temp = current;
current = current.next;
if (list1) {
temp.next = sub1;
sub1 = temp;
} else {
sub2Back.next = temp;
sub2Back = temp;
}
list1 = !list1;
}
front = sub1;
sub1Back.next = sub2;
sub2Back.next = null;
}
}
// builds up the answer as it goes, prepending one and appending the other
public void rearrange() {
if (front != null && front.next != null) {
ListNode current = front.next.next;
ListNode back = front.next;
while (current != null && current.next != null) {
ListNode temp = current.next.next;
back.next = current.next;
back = back.next;
current.next = front;
front = current;
current = temp;
}
back.next = null;
if (current != null) {
current.next = front;
front = current;
}
}
// same as previous, but using a flag to alternate rather than processing a
// pair each time through the loop
public void rearrange() {
if (front != null && front.next != null) {
ListNode current = front.next.next;
ListNode back = front.next;
boolean even = true;
while (current != null) {
ListNode temp = current.next;
if (even) {
current.next = front;
front = current;
} else {
back.next = current;
back = current;
}
even = !even;
current = temp;
}
back.next = null;
}
1 header
1 works (does nothing) for empty list (requires test)
1 works (does nothing) for 1-element list (requires test)
4 generous pattern matching
1 current variable moved forward in a loop
1 two <blah>.next assignments in loop (might be one each in an if/else)
1 resetting two other temporary variables besides current in loop (might be
one each in an if/else, one of them might be front)
1 moving current forward two inside a loop or moving it forward one with
an if/else to handle odd/even differently
5 simple cases (can be given based on hand trace)
1 works for 2-element list (requires test)
2 works for 3-element list
2 works for 4-element list
8 general cases (must type it in to give these points)
2 works for 5-element list
2 works for 6-element list
2 works for 7-element list
2 works for all lists
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