<![CDATA[
Problem #1
1. Preorder traversal 4, 2, 7, 9, 3, 6, 1, 8, 5, 0
Inorder traversal 7, 9, 2, 3, 6, 4, 8, 1, 0, 5
Postorder traversal 9, 7, 6, 3, 2, 8, 0, 5, 1, 4
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
+------------+
| Moon |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Mercury | | Sun |
+------------+ +------------+
/ / \
/ / \
/ / \
+------------+ +------------+ +------------+
| Jupter | | Saturn | | Venus |
+------------+ +------------+ +------------+
\
\
\
+------------+
| Mars |
+------------+
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 retainEqual(Set<Point> data) {
Iterator<Point> itr = data.iterator();
while (itr.hasNext()) {
Point p = itr.next();
if (p.getX() != p.getY()) {
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 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<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 (static is okay)
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, used Map
interface for variable, must have () in call to new)
1 loop over set (foreach or iterator)
2 properly split the string
1 reasonable attempt
1 correct
2 add a new set to map when key is first seen
1 reasonable attempt to test for this case
1 all correct (tests whether this key is there, adds an entry if it is new,
associates it with the exchange, correct generics)
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 FoodData implements Comparable<FoodData> {
private String name;
private double fat;
private double carbs;
private double protein;
public FoodData(String name, double fat, double carbs,
double protein) {
if (fat < 0 || carbs < 0 || protein < 0)
throw new IllegalArgumentException();
this.name = name;
this.fat = fat;
this.carbs = carbs;
this.protein = protein;
}
public String getName() {
return name;
}
public double getCalories() {
return 9 * fat + 4 * (carbs + protein);
}
public double percentFat() {
return 100.0 * (9 * fat / getCalories());
}
public String toString() {
return name + ": " + fat + "g fat, " + carbs +
"g carbohydrates, " + protein + "g protein";
}
public int compareTo(FoodData other) {
double difference = percentFat() - other.percentFat();
if (difference < 0)
return -1;
else if (difference > 0)
return 1;
else
return name.compareTo(other.name);
}
}
1 class header
4 fields (1 point each, -1 if not private, okay to have extra field(s) for
calories or fat calories or percent fat)
3 constructor
1 correct header
1 exception
1 sets four fields correctly
1 getName correct
2 getCalories correct
1 attempt
1 correct
3 percentFat correct (don't have to worry about getCalories() == 0)
1 attempt
2 correct (-1 if close--e.g., missing the *100)
2 toString correct
1 includes all four fields
1 correct format
4 compareTo
1 primary comparison is for some kind of fat comparison
1 correctly computes difference of percent fat and returns int (using
if/else or (int)Math.signum; hard to get this unless they make calls on
percentFat)
1 puts lower percent fat first
1 all other aspects correct (header, alphabetical name comparison when
percentFat equal)
Problem #8
solutions
public void limitPathSum(int max) {
overallRoot = limitPathSum(overallRoot, max);
}
private IntTreeNode limitPathSum(IntTreeNode root, int max) {
if (root != null) {
if (root.data > max) {
root = null;
} else {
root.left = limitPathSum(root.left, max - root.data);
root.right = limitPathSum(root.right, max - root.data);
}
}
return root;
}
---------------------------------------------------------------------------
public void limitPathSum(int max) {
overallRoot = limitPathSum(overallRoot, max, 0);
}
private IntTreeNode limitPathSum(IntTreeNode root, int max, int current) {
if (root != null) {
current += root.data;
if (current > max)
root = null;
else {
root.left = limitPathSum(root.left, max, current);
root.right = limitPathSum(root.right, max, current);
}
}
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) (void solutions that might work go to question 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 (always avoids NullPointerException)
3 correctly computes path sum using a parameter
1 private method has a parameter for path sum or for current max and is
either adding or subtracting root.data somewhere
2 correctly computes the path sum or current max (-1 if close)
3 setting root to null when current > max
1 reasonable attempt (testing an int parameter against root.data, attempt
to eliminate node)
2 correct (-1 if close, e.g., using current >= max)
2 correct recursive calls (no double jeopardy with path sum calculation)
1 reasonable attempt (e.g., one correct call or two almost-correct calls)
1 correct
notes:
Give to question leader solutions that avoid x=change(x), that have extra
data structures, that change data fields, and anything else odd.
Example of a void solution that works:
public void limitPathSum(int max) {
if (overallRoot != null && overallRoot.data > max) {
overallRoot = null;
} else {
limitPathSum(overallRoot, max);
}
}
private void limitPathSum(IntTreeNode root, int max) {
if (root != null) {
if (root.left != null && root.data + root.left.data > max) {
root.left = null;
}
if (root.right != null && root.data + root.right.data > max) {
root.right = null;
}
limitPathSum(root.left, max - root.data);
limitPathSum(root.right, max - root.data);
}
}
Problem #9
solution
public void mergeFrom(LinkedIntList other) {
if (other.front != null) {
if (front == null)
front = other.front;
else {
ListNode current1 = front;
ListNode current2 = other.front;
if (front.data <= other.front.data) {
current1 = current1.next;
} else {
front = other.front;
current2 = current2.next;
}
ListNode current3 = front;
while (current1 != null && current2 != null) {
if (current1.data <= current2.data) {
current3.next = current1;
current1 = current1.next;
} else {
current3.next = current2;
current2 = current2.next;
}
current3 = current3.next;
}
if (current1 != null) {
current3.next = current1;
} else {
current3.next = current2;
}
}
other.front = null;
}
}
1 header
2 sets other.front to null (for later points, ignore the issue of other.front
being set to null)
1 reasonable attempt
1 correct in all cases
1 works when front is null (resets front to other.front)
1 works when other.front == null based on a test (does nothing)
2 generous pattern match
1 using curr1/curr2 variables to keep track of a position in each of the
two lists (curr2 might be other.front)
1 test to see if curr1.data <= curr2.data or similar inside a loop or
recursion (requires curr1/curr2 variables, can be <)
8 specific cases: 5 with no dupes, 3 with dupes
1 lengths 1/1
1 lengths 1/2
1 lengths 2/2
1 lengths 4/6
1 lengths 10/15
1 lengths 3/3
1 lengths 5/7
1 lengths 12/18
Notes:
-1 if they say other when they mean other.front (but only if that raises their
score)
-2 if they say things like curr1 < curr2 instead of curr1.data < curr2.data
(but only if that raises their score)
If their parameter is of type ListNode, they can get attempt but not correct
for setting other.front to null if they say other = null
We have a general rule that if you can fix one problem and it suddenly works,
then we make that fix and charge them 4 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.
Any O(n^2) solutions or odd solutions (new nodes, changing data) go to the
question leader.
-4 for O(n^2)
Problem #10
Solutions:
public IntTree(int n) {
if (n < 0) {
throw new IllegalArgumentException();
}
overallRoot = makeTree(1, n);
}
private IntTreeNode makeTree(int low, int high) {
if (low > high) {
return null;
} else {
int mid = (low + high - 1) / 2;
return new IntTreeNode(high, makeTree(low, mid),
makeTree(mid + 1, high - 1));
}
}
---------------------------------------------------------------------------
public IntTree(int n) {
if (n < 0) {
throw new IllegalArgumentException();
}
overallRoot = build(n);
number(overallRoot, 1);
}
private IntTreeNode build(int n) {
if (n <= 0) {
return null;
} else {
n--;
return new IntTreeNode(n, build(n / 2 + n % 2), build(n / 2));
}
}
private int number(IntTreeNode root, int start) {
if (root == null) {
return 0;
} else {
int numLeft = number(root.left, start);
int numRight = number(root.right, start + numLeft);
root.data = start + numLeft + numRight;
return numLeft + numRight + 1;
}
}
(not very good) Plus criteria (max +3)
example of things that got +1:
correct constructor header
correct exception
overallRoot = <something>
new IntTreeNode(something)
private method that takes at least one int as a parameter
private method has return type of IntTreeNode
Round 2 Criteria
required:
* recursive calls to construct left and right subtrees
* use of n/2 to try to build balance tree
up to 3 extra points (max score of 6):
+1 basic idea
+1 almost builds the correct structure (e.g., odd/even glitch)
+1 builds the correct structure
Round 3 Criteria
required:
* recursive calls to construct left and right subtrees
* parameters for low/high
* computing a midpoint
score of at least 5 points, but can lose points for:
-1 minor error
missing or incorrect exception
used 1-argument node constructor (take this off if it's the only error)
used an extra structure that didn't simplify the problem
ListNode instead of IntTreeNode
-2 medium error
-3 major error
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011