<![CDATA[
Problem #1
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
+------------+
| Karl |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Chris | | Simon |
+------------+ +------------+
/ \ \
/ \ \
/ \ \
+------------+ +------------+ +------------+
| Anton | | John | | Zoe |
+------------+ +------------+ +------------+
/
/
/
+------------+
| Zach |
+------------+
Only partial credit is 2 out of 4 points if just one node is in the wrong
place.
-------------------------------------------------------------------------------
Problem #3
Method Call Output Produced
------------------------------------------------
mystery(grid, 0, 2, 2); 10 11
mystery(grid, 2, 3, 2); 12 9 12
mystery(grid, 1, 4, 1); 4 8 2 3
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, swapped pair
-0 for quotes
-1 for commas (just once)
partial credit:
3 points for swapping row/col
11 10
8 13 12
4 8 8 7
3 points for using offset on i, but not on j
10 11
15 3 11
7 7 1 8
2 points for weird solution where instead of:
for (int i...) {
sum = 0
for (int j...) {
sum +=
}
print
}
they think it's:
sum = 0
for (int i...) {
for (int j...) {
sum +=
print
}
}
getting this output:
4 10 17 21
6 12 14 21 27 33
4 12 14 17
Problem #4
solution
public static void retainEvenLength(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)
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
2 other approaches
1 basic idea: foreach loop or for-i-get loop that tests and calls s.remove
1 correct if you ignore concurrent modification (so it has to be a foreach,
it has to have a correct test, it has to have a correct call on remove)
Problem #5
solution
public boolean hasPathSum(int sum) {
return hasPathSum(overallRoot, sum);
}
private boolean hasPathSum(IntTreeNode root, int sum) {
if (root == null)
return false;
if (root.data == sum)
return true;
int sum2 = sum - root.data;
return hasPathSum(root.left, sum2) || hasPathSum(root.right, sum2);
}
1 correct public header && private header with root parameter && public method
returns result of calling private with overallRoot
2 base case when root == null
1 reasonable attempt to test for this case
1 correct (no NullPointerException, returns false whenever root is null)
2 base case when root.data == n
1 reasonable attempt to test for this case
1 correct (returns true for this case)
5 recursive cases
1 their answer includes recursive call on root.left and recursive call on
root.right and some kind of n
2 basic idea: either calls on left and right with n reduced by root data:
hasPathSum(root.left, n - root.data)
hasPathSum(root.right, n - root.data)
or calls on left and right with new total sum
hasPathSum(root.left, sum + root.data, n)
hasPathSum(root.right, sum + root.data, n)
2 correct (requires basic idea, requires putting together two calls with
some kind of if/else or logical or)
Problem #6
solution
public static int recordDate(Map<String, List<String>> dates,
String name1, String name2) {
if (!dates.containsKey(name1)) {
dates.put(name1, new LinkedList<String>());
}
if (!dates.containsKey(name2)) {
dates.put(name2, new LinkedList<String>());
}
dates.get(name1).add(0, name2);
dates.get(name2).add(0, name1);
int n = 0;
for (String s : dates.get(name1)) {
if (s.equals(name2)) {
n++;
}
}
return n;
}
1 header
3 constructs new LinkedList the first time names are seen
1 reasonable attempt for one name: testing for name not in map, adding a
new linked list if not
1 reasonable attempt for both names
1 correct code for one name (very nitpicky, including "()" in call to
LinkedList constructor)
3 adding to lists
1 reasonable attempt for one name: requires a call on get for the map and a
call on add with the other name
1 reasonable attempt for both names
1 correct code for one name (very nitpicky)
3 returning date #
1 basic idea: loop through one list searching for the other name
1 correct loop over one list, testing for the other name (requires call on
String equals method)
1 counter setup: initialize counter, increment in a loop, return after
loop, correct value of n
Problem #7
solution
public class ClockTime implements Comparable<ClockTime> {
private int hours;
private int minutes;
private String amPm;
public ClockTime(int hours, int minutes, String amPm) {
this.hours = hours;
this.minutes = minutes;
this.amPm = amPm;
}
public int compareTo(ClockTime other) {
if (!amPm.equals(other.amPm))
return amPm.compareTo(other.amPm);
else if (hours != other.hours)
return hours % 12 - other.hours % 12;
else
return minutes - other.minutes;
}
public int getHours() {
return hours;
}
public int getMinutes() {
return minutes;
}
public String getAmPm() {
return amPm;
}
public String toString() {
String result = hours + ":";
if (minutes < 10)
result += "0" + minutes;
else
result += minutes;
result += " " + amPm;
return result;
}
}
1 class header
3 fields declared correctly (1 point per field, -1 if not private, okay to have
extra fields)
2 constructor
1 attempt
1 correct
2 get methods (getHours, getMinutes, getAmPm)
1 at least one corect
1 all correct
8 compareTo
2 correct am/pm test (-1 if == versus equals)
3 correct hours test
1 1 ignoring 12
2 including 12
1 reasonable attempt to handle this case
1 correctly handles this case
1 correct minutes test
2 correct order (am/pm, then hours, then minutes) and header
1 close (at most one transposition, header problem okay for this point)
1 correct order and header
4 toString
1 includes all 3 fields
1 all correct ignoring extra "0"
2 extra 0 included for 1-digit numbers
1 reasonable attempt to handle this case
1 correctly handles this case
Notes:
if they reset hours to something like 0 to solve the comparison problem,
they get attempt but not correct for "extra 0" points in toString
Problem #8
solution
public void makeFull() {
overallRoot = makeFull(overallRoot, 1);
}
private IntTreeNode makeFull(IntTreeNode root, int level) {
if (root != null) {
if (root.left == null && root.right != null) {
root = new IntTreeNode(-level, root, root.right);
root.left.right = null;
} else if (root.left != null && root.right == null) {
root = new IntTreeNode(-level, root.left, root);
root.right.left = null;
}
root.left = makeFull(root.left, level + 1);
root.right = makeFull(root.right, level + 1);
}
return root;
}
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) (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 1 && all left are like this)
1 root.right = recurse(root.right) (at least 1 && all right are like this)
1 private method returns an IntTreeNode in at least one case
1 root == null case
2 correctly computes level
1 level parameter in private method
1 correctly computes the level on each call (tend to lose this for ++)
4 adding new nodes: 1-child cases
1 correct test for one of the 1-child cases
1 correctly constructs a node with the same child as the old root and with
the old root as a child where there was an empty subtree for one case
(should have data that is minus level, but no double jeopardy with level
computation)
1 correct test for second 1-child case
1 correct construction for second 1-child case (can get this if there is a
minor error that lost the first node construction point)
3 severing links for old parent nodes
2 correctly sets old child link to null for one case
1 correctly sets old child link to null for second case
2 correct recursive calls are made for 2-child case (left and right)
2 recursive calls are made for 1-child cases
notes:
attempt to change data fields or iterative or constructing too many nodes go to
Question Leader
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
Solution:
public void reverse3() {
if (front != null && front.next != null &&
front.next.next != null) {
ListNode temp = front;
front = front.next.next;
ListNode temp2 = front.next;
front.next = temp.next;
temp.next.next = temp;
temp.next = temp2;
while (temp.next != null && temp.next.next != null &&
temp.next.next.next != null) {
temp2 = temp.next;
temp.next = temp.next.next.next;
temp = temp2;
temp2 = temp.next.next.next;
temp.next.next.next = temp.next;
temp.next.next = temp;
temp.next = temp2;
}
}
}
1 header
3 simple cases
1 works (does nothing) for empty list (requires test)
1 works (does nothing) for 1-element list (requires test)
1 works (does nothing) for 2-element (requires test)
10 Works for specific cases (if you think they have a bug that is not caught by
the test cases, ask the question leader what points to deduct)
4 3-element list
1 6-element list (ignoring first triple)
1 9-element list (ignoring first triple)
1 4-element list (ignoring first triple)
1 5-element list (ignoring first triple)
1 7-element list (ignoring first triple)
1 8-element list (ignoring first triple)
3 attempt to rearrange links for first 3 values (must appear before a loop)
1 attempt: change 2 of (front, 3 ~.next) to something other than null
1 better: change 3 of (front, 3 ~.next) to something other than null
1 best: change 4 of (front, 3 ~.next) to something other than null
3 attempt to rearrange links for later triples (must appear inside a loop)
1 attempt: change 2 of (4 ~.next) to something other than null
1 better: change 3 of (4 ~.next) to something other than null
1 best: change 4 of (4 ~.next) to something other than null
note: they can get credit for both of these with one sequence of code if:
* they call a method before the loop passing front and inside the loop
passing ~.next
* they write it recursively and begin with a call on front and then have a
call on ~.next
* inside their loop, they have an if/else where they either change front or
~.next
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 solution to #7 using recursion
public void reverse3() {
front = reverse3(front);
}
private ListNode reverse3(ListNode lst) {
if (lst != null && lst.next != null && lst.next.next != null) {
ListNode temp = lst;
lst = lst.next.next;
ListNode temp2 = lst.next;
lst.next = temp.next;
temp.next.next = temp;
temp.next = temp2;
temp.next = reverse3(temp.next);
}
return lst;
}
notes:
syntax mistakes fall into different categories:
* scope issues
* variable declaration (or redeclaration)
* semicolons
* etc
They get one category for free and then -1 per category, max -2
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011