<![CDATA[
Problem #1
Preorder traversal 0, 3, 1, 2, 5, 8, 9, 4, 7, 6
Inorder traversal 1, 3, 5, 2, 8, 0, 9, 7, 4, 6
Postorder traversal 1, 5, 8, 2, 3, 7, 6, 4, 9, 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
+------------+
| Ephraim |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Ben | | Frank |
+------------+ +------------+
/ \ \
/ \ \
/ \ \
+------------+ +------------+ +------------+
| Adam | | Dan | | Gideon |
+------------+ +------------+ +------------+
/
/
/
+------------+
| Caleb |
+------------+
Only partial credit is 2 out of 4 points if just one node is in the wrong
place.
-------------------------------------------------------------------------------
Problem #3
Method Call Value Returned
----------------------------------------
mystery(grid, 5) 5
mystery(grid, 3) 22
mystery(grid, 1) 24
1 pt for first problem
2 pt for second problem
2 pt for third problem
Problem #4
solution
public String acronymFor(List<String> words) {
String acronym = "";
for (String next : words) {
acronym += next.toUpperCase().charAt(0);
}
return acronym;
}
1 correct header (static is okay)
1 loop over list (can be foreach, iterator, get/size, as long as it traverses
the list so that each string is visited once in the loop)
3 construct and return acronym; there are 5 things to do:
declare local String variable and initialize to empty string
return the local String variable at the end
get the first character of each string
convert that character to its capitalized version
concatenate each capital letter to the local string variable
The points are based on how many of the 5 they do right:
1 at least 2 of these
1 at least 4 of these
1 all 5 of these and the pieces fit together
notes:
-1 if they change the list
Problem #5
solution
public void printLevel(int target) {
if (target < 1) {
throw new IllegalArgumentException();
}
System.out.print("nodes at level " + target + " =");
printLevel(overallRoot, target, 1);
System.out.println();
}
private void printLevel(IntTreeNode root, int target, int level) {
if (root != null)
if (level == target)
System.out.print(" " + root.data);
else {
printLevel(root.left, target, level + 1);
printLevel(root.right, target, level + 1);
}
}
1 overall setup: private header with a root parameter and public method calls
private method passing it overallRoot; private header has target as a
parameter and public method passes target
1 correct exception
1 base case for null (tests for this and prevents any NullPointerException)
2 recursive calls on left and right
1 reasonable attempt (some kind of recursive call on left or right)
1 correctly traverses the entire tree
3 correctly computes level information to form a test (recurses on level + 1 vs
target or recurses on level - 1 vs 1)
1 attempt (requires recursion attempt, some kind of test that could be a
level test)
2 correct (-1 if minor error like obob)
2 prints data for target level
1 attempt (prints root.data and one of: text before recursion, space with
root.data, println after recursion)
1 correct (requires "compute level" attempt, prints correct text before
call, includes spaces, println after, all other calls are print)
Problem #6
solution
public Map<String, Set<List<String>>> acronyms(
Set<List<String>> lists) {
Map<String, Set<List<String>>> result =
new TreeMap<String, Set<List<String>>>();
for (List<String> words : lists) {
String acronym = acronymFor(words);
if (!result.containsKey(acronym)) {
result.put(acronym, new HashSet<List<String>>());
}
result.get(acronym).add(words);
}
return result;
}
1 header (static is okay)
2 construct and return proper map
1 reasonable attempt: map of strings to sets of lists of strings
1 all correct (correct generics, correct return, map is a TreeMap, used Map
interface for variable, missing parens are a syntax error)
1 loop over set (foreach or iterator)
1 get the acronym for the list (easiest if they call acronymFor)
3 add a new set to map when acronym is first seen
1 reasonable attempt to test for this case
1 reasonable attempt to construct a set that they add to their map (should
be a HashSet, only 1 mistake allowed)
1 all correct (tests whether this acronym is there, adds an entry if it is
new, associates it with a HashSet, correct generics)
2 adds list 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 = other.getRating() - 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)
Problem #8
solution
public void limitLeaves(int min) {
overallRoot = limitLeaves(overallRoot, min);
}
private IntTreeNode limitLeaves(IntTreeNode root, int min) {
if (root != null) {
root.left = limitLeaves(root.left, min);
root.right = limitLeaves(root.right, min);
if (root.left == null && root.right == null && root.data <= min)
root = null;
}
return root;
}
----------------------------------------------------------------------
// void solution (not x=change(x))
public void limitLeaves(int min) {
limitLeaves(overallRoot, min);
if (overallRoot != null && overallRoot.left == null &&
overallRoot.right == null && overallRoot.data <= min) {
overallRoot = null;
}
}
private void limitLeaves(IntTreeNode root, int min) {
if (root != null) {
limitLeaves(root.left, min);
limitLeaves(root.right, min);
if (root.left != null && root.left.left == null &&
root.left.right == null && root.left.data <= min) {
root.left = null;
}
if (root.right != null && root.right.left == null &&
root.right.right == null && root.right.data <= min) {
root.right = null;
}
}
}
1 public header
1 overall setup: private header with a root parameter and public method calls
private method passing it overallRoot; private header has min as a parameter
and public method passes min
5 used x = change(x) or equivalent (ok to 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 root == null
1 attempt (tested this case)
1 correct: requires test, no NullPointerException, tree not changed in this
case
2 recurse on left and right
1 attempt (either one call with min or two calls without)
1 correct (2 calls each with min)
3 removing current node if it's a leaf with data <= min
1 test for this case (some comparison of root.data vs min)
1 reset root to null in this case
1 all correct (test is root.data <= min)
6 removes ancestors of removed leaves when appropriate
2 reasonable attempt (after some recursive call, attempt to potentially
remove this node--could be something that leads to infinite
loop/recursion)
4 correct (normally solved with correct order)
notes:
Give to question leader solutions that avoid x=change(x), that have extra
data structures, that change data fields, that are inefficient (might not be
O(n)) and anything else odd.
Problem #9
solution
public boolean bubble() {
boolean swap = false;
if (front != null && front.next != null) {
if (front.data > front.next.data) {
swap = true;
ListNode temp = front;
front = front.next;
temp.next = front.next;
front.next = temp;
}
ListNode current = front;
while (current.next != null && current.next.next != null) {
if (current.next.data > current.next.next.data) {
swap = true;
ListNode temp = current.next.next;
current.next.next = temp.next;
temp.next = current.next;
current.next = temp;
}
current = current.next;
}
}
return swap;
}
1 header
2 correctly handles 0-element and 1-element lists
1 attempt: two tests or one test that returns false
1 correct: test for each case, doesn't change list, returns false
3 swap flag
1 swap flag declared and initialized to false before loop (or
equivalent--e.g., a count of the number of changes)
1 swap flag set to true in the context of some list change
1 swap flag always set to true when list is changed and returned
4 generous pattern matching
1 current variable that is moved forward in a loop
1 loop stops one early
1 at least two <blah>.next assignments in loop
1 three <blah>.next assignments in loop
4 correctly handles 2-element list (ignoring swap flag)
1 test whether front.data > front.next.data
3 correctly swaps first pair ([2, 1])
6 correctly handles > 2-element lists
2 [1, 3, 2, 4]
2 [1, 4, 3, 2]
2 [3, 2, 1, 5, 4, 6]
Note: if it gets a 20 and isn't correct, show 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.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011