<![CDATA[
Problem #1
Preorder traversal 3, 2, 4, 5, 7, 0, 1, 6, 9, 8
Inorder traversal 4, 2, 7, 5, 0, 3, 1, 9, 6, 8
Postorder traversal 4, 7, 0, 5, 2, 9, 8, 6, 1, 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
+------------+
| Lee |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Britt | | Vin |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Bernardo | | Chris |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Chico | | Harry |
+------------+ +------------+
Only partial credit is 2 out of 4 points if just one node is in the wrong
place.
Problem #3
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
solutions
public void removeEvenLength(Set<String> set) {
Iterator<String> itr = set.iterator();
while (itr.hasNext()) {
String s = itr.next();
if (s.length() % 2 == 0) {
itr.remove();
}
}
}
1 correct header (static is okay, non-void return okay if they return something
of that type)
2 iterate over set
1 reasonable attempt--foreach loop or at least two of:
* construct iterator
* loop with test for hasNext
* call next inside the loop
1 correct: all three of above (no foreach loop) and next is called just
once on each iteration
2 remove even length strings (requires iterator attempt)
1 correct test for even length string
1 correctly removes using iterator remove method (can get this even if test
is flawed; can't get this if loop is a foreach)
Problem #5
solution
public void printLeaves() {
if (overallRoot == null)
System.out.println("no leaves");
else {
System.out.print("leaves:");
printLeaves(overallRoot);
System.out.println();
}
}
private void printLeaves(IntTreeNode root) {
if (root != null)
if (root.left == null && root.right == null)
System.out.print(" " + root.data);
else {
printLeaves(root.right);
printLeaves(root.left);
}
}
1 overall setup: correct public/private headers, public method passes
overallRoot to private method
1 prints "no leaves" when overallRoot is null and in no other cases (don't
worry about print versus println for this point)
1 base case for null (tests for this and prevents any NullPointerException)
3 handles leaf nodes properly
1 reasonable attempt to test for this case
1 prints root data for some leaves (ignore spacing, requires test attempt)
1 prints root data for all leaves and just leaves with spaces
3 recursive calls on left and right
1 reasonable attempt (some kind of recursive call on left or right)
1 correctly traverses the entire tree
1 traverses right-to-left
1 other formatting details correct (prints "leaves:" before call, each call
produces exactly one line of output)
Problem #6
solution
public Map<Integer, Set<String>> split(Set<String> words) {
Map<Integer, Set<String>> buckets = new TreeMap<Integer, Set<String>>();
for (String word : words) {
int n = word.length();
if (!buckets.containsKey(n)) {
buckets.put(n, new TreeSet<String>());
}
buckets.get(n).add(word);
}
return buckets;
}
1 header (static is okay)
2 construct and return proper map
1 reasonable attempt: constructing a map of ints/integers to something
involving strings (doesn't have to be a set)
1 all correct: correct generics, map is TreeMap, map is returned, must have
() in call to new
1 correct loop over set of words (foreach or iterator)
1 correct test for whether next word length is already in the map
2 new sets: adds a new set to map when new length is seen (can't happen every
time)
1 reasonable attempt: call on add or put with a new set of strings
1 all correct: correct generics, correct call on put, set is TreeSet, must
have () in call to new
3 adds to sets: adds each word to the appropriate set
1 reasonable attempt: call on add or put with both length and word
1 better attempt: calling get on word length to add/put word
1 all correct (works in all cases, no free syntax errors)
notes: SortedSet and SortedMap would be better interfaces to use for the map
being constructed, but this isn't required. They would lose the header
point if the set being passed in is of type SortedSet.
No penalty for calling put multiple times on the same int/set pair.
We are picky about ()'s on constructing, but don't take it off twice.
We don't care about str.length vs str.length()
Problem #7
solution
public class TeamData implements Comparable<TeamData> {
private String name;
private int solved;
private int totalTime;
private int problems;
public TeamData(String name, int problems) {
this.name = name;
this.problems = problems;
this.totalTime = 0;
this.solved = 0;
}
public void success(int problem, int time) {
solved++;
totalTime += time;
}
public String toString() {
return name + " solved " + solved + " of " + problems + " in "
+ totalTime + " minutes";
}
public int solved() {
return solved;
}
public int time() {
return totalTime;
}
public double percentCorrect() {
return 100.0 * solved / problems;
}
public int compareTo(TeamData other) {
if (solved != other.solved)
return other.solved - solved;
else
return totalTime - other.totalTime;
}
}
1 class header
4 fields (1 point each, -1 once if not private, okay to have extra field(s))
2 constructor
1 correct header
1 all fields set apropriately (can rely on defaults for totalTime, solved)
2 solved and time methods
1 reasonable attempt (at least one method completely correct or two methods
that are each partially correct)
1 all correct
2 percentCorrect method
1 reasonable attempt (exists, divides solved by problems)
1 correct
2 success method
1 reasonable attempt (updates at least one of the two fields)
1 all correct
2 toString
1 reasonable attempt (exists, includes at least 2 of the 4 fields)
1 all correct, including format
5 compareTo
1 primary comparison is for problems solved
1 compares times when problems solved is equal
2 correct comparison for problems solved (most people will miss this)
1 all other aspects correct (header, time comparison)
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
6 used x = change(x) or equivalent (ok to give "equivalent" to question leader)
2 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 root == null
1 attempt (tested this case)
2 correct: requires test, no NullPointerException, tree not changed in this
case
3 recursively stretching subtrees
1 attempt: calls on stretch(root.left) and stretch(root.right)
2 correct: stretch in all appropriate cases, no order problems
6 adding new nodes (ignoring the issue of stretching the children)
1 attempt to test for this case (one child null, the other not)
--stop here if they don't get test attempt
1 correct tests for both (has to exclude leaf case)
1 constructs a new node in each of the two cases (test could be flawed)
1 uses the 3-argument constructor for constructing node(s)
2 construct/return is otherwise correct: no double jeopardy with previous
points; must construct in both cases, must set left/right properly, must
return a reference to newly constructed nodes (or equivalent)
Problem #9
solution
public void shift() {
if (front != null && front.next != null) {
ListNode otherFront = front;
ListNode otherBack = front;
front = front.next;
ListNode current = front;
while (current.next != null && current.next.next != null) {
otherBack.next = current.next;
otherBack = current.next;
current.next = current.next.next;
current = current.next;
}
if (current.next != null) {
otherBack.next = current.next;
otherBack = current.next;
}
current.next = otherFront;
otherBack.next = null;
}
}
1 header
1 works (does nothing) for empty list (requires test)
1 works (does nothing) for 1-element list (requires test)
5 generous pattern matching
1 current variable moved forward in a loop
1 second current variable moved forward in the same loop
1 two <blah>.next assignments in loop
1 loop stops early
1 current.next = ... after the loop
4 simple cases
2 works for 2-element list
2 works for 3-element list
8 general cases (generally need all generous points and setting some .next to
null to get these)
2 works for 4-element list
2 works for 6-element list
2 works for 5-element list
2 all correct
Recursive solutions and "find back/size first" solutions 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.
-------------------------------------------------------------------------------
alternate size/append solutions:
public void shift() {
if (front != null && front.next != null) {
ListNode back = front;
while (back.next != null)
back = back.next;
ListNode first = front;
back.next = front;
front = front.next;
back = back.next;
ListNode current = front;
while (current != first && current.next != first) {
back.next = current.next;
back = back.next;
current.next = current.next.next;
current = current.next;
}
back.next = null;
}
}
public void shift() {
if (front != null && front.next != null) {
ListNode back = front;
int size = 1;
while (back.next != null) {
size++;
back = back.next;
}
ListNode temp = front;
front = front.next;
back.next = temp;
back = back.next;
ListNode cur = front;
size -=2;
while (size > 0) {
temp = cur.next;
cur.next = cur.next.next;
back.next = temp;
back = back.next;
size -= 2;
cur = cur.next;
}
back.next = null;
}
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011