<![CDATA[
Problem #1
Preorder traversal 0, 3, 2, 9, 4, 1, 6, 5, 7, 8
Inorder traversal 2, 9, 3, 0, 6, 1, 5, 4, 7, 8
Postorder traversal 9, 2, 3, 6, 5, 1, 8, 7, 4, 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
+------------+
| Leonard |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Howard | | Penny |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Amy | | Sheldon |
+------------+ +------------+
\ /
\ /
\ /
+------------+ +------------+
| Bernadette | | Raj |
+------------+ +------------+
Only partial credit is 2 out of 4 points if just one node is in the wrong
place.
Problem #3
map1: {bar=1, baz=2, foo=3, mumble=4}
map2: {1=earth, 2=wind, 3=air, 4=fire}
map returned: {bar=earth, baz=wind, foo=air, mumble=fire}
map1: {five=105, four=104, one=101, six=106, three=103, two=102}
map2: {99=uno, 101=dos, 103=tres, 105=quatro}
map returned: {five=quatro, one=dos, three=tres}
map1: {a=42, b=9, c=7, d=15, e=11, f=24, g=7}
map2: {1=four, 3=score, 5=and, 7=seven, 9=years, 11=ago}
map returned: {b=years, c=seven, e=ago, g=seven}
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 Set<Point> extractEqual(Set<Point> data) {
Set<Point> result = new HashSet<Point>();
for (Point p : data)
if (p.getX() == p.getY())
result.add(p);
return result;
}
public Set<Point> extractEqual(Set<Point> data) {
Set<Point> result = new HashSet<Point>();
Iterator<Point> i = data.iterator();
while (i.hasNext()) {
Point p = i.next();
if (p.getX() == p.getY())
result.add(p);
}
return result;
}
1 correct header (static is okay)
2 construct and return a new set
1 reasonable attempt (at least 2 of: constructing a set, HashSet, return)
1 all correct (including Set interface for variable)
1 iterate over the set passed as a parameter
1 adding values to the new set if getX() == getY() (can get this even if they
missed the "construct" points as long as there is some indication that it's a
different set than the one passed as a parameter)
Problem #5
solution
public void printLevel(int target) {
if (target < 1)
throw new IllegalArgumentException();
printLevel(overallRoot, target, 1);
}
private void printLevel(IntTreeNode root, int target, int level) {
if (root != null)
if (level == target)
System.out.println(root.data);
else {
printLevel(root.left, target, level + 1);
printLevel(root.right, target, level + 1);
}
}
1 overall setup: correct public/private headers, public method passes
overallRoot to private method
1 correct exception
2 base case for null
1 attempt: test for this case
1 correct: always does nothing and prevents any NullPointerException
1 recursive calls on root.left and root.right (generous)
3 correctly computes level information (recurse on level + 1 vs target or
recurs on level - 1 vs 1)
1 attempt
2 correct (-1 if minor error like obob)
2 prints data for target level (requires "compute level" attempt)
1 attempt
1 correct
Problem #6
solution
public Map<String, List<Integer>> indexMap(List<String> data) {
Map<String, List<Integer>> result =
new TreeMap<String, List<Integer>>();
for (int i = 0; i < data.size(); i++) {
String next = data.get(i);
if (!result.containsKey(next))
result.put(next, new ArrayList<Integer>());
result.get(next).add(i);
}
return result;
}
1 header (static is okay)
2 construct and return proper map
1 reasonable attempt: constructing a map of strings to something involving
ints (doesn't have to be a list)
1 all correct: correct generics, map is TreeMap, map is returned, must have
() in call to new
1 correct loop over list of strings (foreach or size/get, computing index)
1 correct test for whether next string is already in the map
2 new lists: adds a new list to map when new string is seen (can't happen every
time)
1 reasonable attempt: call on add or put with a new list or set of ints
1 all correct: correct generics, correct call on put, list is either
Arraylist or LinkedList, must have () in call to new
3 adds to lists: adds each word to the appropriate set
1 reasonable attempt: call on add or put with both string and index
1 better attempt: calling get on string to add/put word
1 all correct (works in all cases, no free syntax errors)
notes: No penalty for calling put multiple times on the same string/list pair.
We are picky about ()'s on constructing, but don't take it off twice.
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; new Double(...).compareTo(...); 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
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;
}
1 public header
1 overall setup: private header with a root parameter and public method calls
private method passing it overallRoot; private header has n as a parameter
and public method passes n
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 n or two calls without)
1 correct (2 calls each with n)
3 removing current node if it's a leaf with data <= n
1 test for this case (some comparison of root.data vs n)
1 reset root to null in this case
1 all correct (test is root.data <= n)
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)
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