<![CDATA[
Problem #1
Preorder traversal 0, 3, 4, 7, 6, 2, 1, 5, 9, 8
Inorder traversal 7, 4, 6, 3, 2, 1, 0, 5, 8, 9
Postorder traversal 7, 6, 4, 1, 2, 3, 8, 9, 5, 0
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
+------------+
| Jeff |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Britta | | Shirley |
+------------+ +------------+
/ / \
/ / \
/ / \
+------------+ +------------+ +------------+
| Abed | | Pierce | | Troy |
+------------+ +------------+ +------------+
\
\
\
+------------+
| Annie |
+------------+
Only partial credit is 2 out of 4 points if just one node is in the wrong
place.
Problem #3
Two-Dimensional Array Contents of Set Returned
------------------------------------------------------------------
[[1, 2], [3, 4]] [1, 2, 13, 14]
[[7], [], [8, 8, 9, 10]] [7, 28, 29, 30]
[[3, 14], [5, 13, 4], [4, 3, 1]] [3, 14, 15, 21, 23, 24]
1 pt for first row
2 pt for second row
2 pt for third row
-1 for each error: missing number, extra number, duplicate number, wrong order
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 do it backwards
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
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
1 works (returns 0) when overallRoot is null
2 base case when root == null for nonempty trees
1 reasonable attempt to test for this case
1 correct (no NullPointerException, returns 0 whenever root is null)
6 recursive cases
1 their answer includes recursive call on root.left and recursive call on
root.right
3 adds root.data to their sum when level is odd
2 attempt (must pass extra int parameter updated with +1 or ++ or
extra boolean parameter updated with not)
1 correct
2 actually works to compute the sum (requires previous attempt)
Problem #6
solution
public static Map<String, Set<String>> convert(Set<String> numbers) {
Map<String, Set<String>> result = new TreeMap<String, Set<String>>();
for (String s : numbers) {
String exchange = s.substring(0, 3);
String digits = s.substring(4);
if (!result.containsKey(exchange)) {
result.put(exchange, new TreeSet<String>());
}
result.get(exchange).add(digits);
}
return result;
}
1 header
2 construct and return proper map
1 reasonable attempt: map of strings to sets
1 all correct (correct generics, correct return, map is a TreeMap)
1 loop over set
1 properly split the string
3 add a new set to map when key is first seen
1 reasonable attempt to test for this case
1 reasonable attempt to construct new set in this case
1 all correct (correct generics, set is TreeSet, efficient--constructs sets
only in this case)
2 adds suffix to existing set assuming key is there
1 reasonable attempt (getting something from the map that they then add to)
1 all correct
Problem #7
solution
public class BookData implements Comparable<BookData> {
private String title;
private String author;
private int reviews;
private double total;
public BookData(String title, String author) {
this.title = title;
this.author = author;
this.reviews = 0;
this.total = 0.0;
}
public void review(double rating) {
reviews++;
total += rating;
}
public String getTitle() {
return title;
}
public double getRating() {
if (reviews == 0)
return 0.0;
else
return total / reviews;
}
public String toString() {
double rating = (int) (10.0 * getRating()) / 10.0;
String result = title + ", by " + author + ", " + rating + " (";
if (reviews == 1)
result += "1 review)";
else
result += reviews + " reviews)";
return result;
}
public int compareTo(BookData other) {
double delta = getRating() - other.getRating();
if (delta < 0)
return 1;
else if (delta > 0)
return -1;
else // delta == 0
return other.reviews - reviews;
}
}
1 class header
4 fields (1 point each, -1 once if not private, okay to have extra field(s),
okay to store list of reviews instead of total)
1 constructor (can rely on defaults for reviews, total)
2 review method
1 reasonable attempt to record this score in a field
1 all correct (requires reviews and total field, has to record the score in
such a way that an average can be computed)
1 getTitle
3 getRating method
1 reasonable attempt (returns some kind of average)
1 correct when reviews > 0
1 special case for reviews == 0 (requires test)
4 toString
1 reasonable attempt (exists, includes at least 2 of the 4 data elements)
1 attempt to truncate rating (2 of *10, cast/round, / 10)
1 correct average rating (truncated, not round; divide by 10.0; reviews==0;
no double jeopardy if they call getRating)
1 all correct other than average rating (including format and special case
for "1 review")
4 compareTo
1 primary comparison is for some kind of average rating
1 correctly computes difference of average ratings and returns int (using
if/else or (int)Math.signum; hard to get this unless they make calls on
getRating)
1 puts higher ratings first
1 all other aspects correct (header, reviews comparison included and puts
higher counts first)
Notes:
Using a set or array of fixed size should lose -1 for the field, but then
pretend it works.
Problem #8
solutions
public void removeLeftLeaves() {
removeLeftLeaves(overallRoot, false);
}
private IntTreeNode removeLeftLeaves(IntTreeNode root, boolean left) {
if (root != null) {
root.left = removeLeftLeaves(root.left, true);
removeLeftLeaves(root.right, false);
if (left && root.left == null && root.right == null)
root = null;
}
return root;
}
public void removeLeftLeaves() {
removeLeftLeaves(overallRoot);
}
private void removeLeftLeaves(IntTreeNode root) {
if (root != null) {
removeLeftLeaves(root.left);
removeLeftLeaves(root.right);
if (root.left != null && root.left.left == null &&
root.left.right == null)
root.left = null;
}
}
Plus Criteria for solutions without left-leaf test (max +8)
+1 correct public header
+1 correct private header with a root parameter and public method calls private
method passing it overallRoot
+1 some test on null in private method
+1 recursive call on root.left
+1 recursive call on root.right
+3 leaf test
+2 setting a left link to null
+2 setting a leaf link to null (requires leaf test)
-------------------------------------------------------------------------------
Criteria for solutions with left-leaf test
1 public header
1 private header with a root parameter and public method calls private method
passing it overallRoot
4 null case (root being null and other cases, like root.left being null)
2 attempt (tested this case)
2 correct (always tests this case when necessary)
2 recursively trims left subtree
1 attempt (recursive call on root.left)
1 correct (always trims root.left)
2 recursively trims right subtree
1 attempt (recursive call on root.right)
1 correct (always trims root.right)
10 eliminates left leaves
4 left leaf test
3 correct sets either root or root.left to null if it's a leaf
3 recursively trims left subtree first
Problem #9
solutions
public void compressDuplicates() {
if (front != null) {
int count = 1;
while (front.next != null && front.data == front.next.data) {
count++;
front = front.next;
}
front = new ListNode(count, front);
ListNode current = front.next;
while (current.next != null) {
count = 1;
while (current.next.next != null &&
current.next.data == current.next.next.data) {
count++;
current.next = current.next.next;
}
current.next = new ListNode(count, current.next);
current = current.next.next;
}
}
}
public void compressDuplicates() {
if (front != null) {
int count = 1;
while (front.next != null && front.data == front.next.data) {
count++;
front = front.next;
}
front = new ListNode(count, front);
ListNode current = front.next;
count = 1;
while (current.next != null) {
if (current.next.next != null &&
current.next.data == current.next.next.data) {
count++;
current.next = current.next.next;
} else {
current.next = new ListNode(count, current.next);
current = current.next.next;
count = 1;
}
}
}
}
public void compressDuplicates() {
front = compressDuplicates(front);
}
private ListNode compressDuplicates(ListNode node) {
if (node != null) {
int count = 1;
while (node.next != null && node.data == node.next.data) {
count++;
node = node.next;
}
node = new ListNode(count, node);
node.next.next = compressDuplicates(node.next.next);
}
return node;
}
1 header
1 works (does nothing) for empty list (requires test)
8 attempt at main loop over list
1 attempt: current starts at front, while some form of current != null
1 includes current = current.next
2 keeps track of previous node before group of duplicates
2 inner if or inner while that increments a counter for duplicates
1 constructs a new node with count
1 newly constructed node points to one of the nodes with the data being
counted
2 attempt to compress at front of list: a second loop that counts duplicates at
front of list or a special case in the main loop for front
8 actually works
3 compresses at front of list
5 compresses later sequences
Recursive solutions go to question leader.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011