<![CDATA[
Problem #1
Preorder traversal 8, 7, 2, 4, 9, 5, 1, 3, 6, 0
Inorder traversal 4, 2, 9, 7, 8, 3, 1, 6, 5, 0
Postorder traversal 4, 9, 2, 7, 3, 6, 1, 0, 5, 8
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
+------------+
| George |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Emma | | Jane |
+------------+ +------------+
/ \ / \
/ \ / \
/ \ / \
+------------+ +------------+ +------------+ +------------+
| Elton | | Frank | | Harriet | | Weston |
+------------+ +------------+ +------------+ +------------+
Only partial credit is 2 out of 4 points if just one node is in the wrong
place.
-------------------------------------------------------------------------------
Problem #3
Method Call Contents of Set Returned
-----------------------------------------------
mystery(grid, 2, 2) [6, 7]
mystery(grid, 0, 2) [1, 2, 5, 8]
mystery(grid, 3, 3) [1, 2, 3, 7, 9]
1 pt for first problem
2 pt for second problem
2 pt for third problem
-1 for order error (just once)
-1 for duplicates (just once)
-1 for missing number
-1 for extra number
no subproblem can go negative
Problem #4
solutions
public Set<Point> removeDuplicates(List<Point> list) {
Set<Point> result = new HashSet<Point>();
Iterator<Point> itr = list.iterator();
while (itr.hasNext()) {
Point p = itr.next();
if (result.contains(p)) {
itr.remove();
} else {
result.add(p);
}
}
return result;
}
public Set<Point> removeDuplicates(List<Point> list) {
Set<Point> result = new HashSet<Point>();
for (int i = 0; i < list.size(); i++) {
if (result.contains(list.get(i))) {
list.remove(i);
i--;
}
result.add(list.get(i));
}
return result;
}
1 correct header (static is okay)
2 construct and return the set of values from the list
1 reasonable attempt (at least 3 of: constructing a set, HashSet, attempt
to add values from list, return)
1 all correct assuming code to remove duplicates from list is correct
(including Set interface for variable)
2 remove duplicates from the list
1 reasonable attempt
1 correct
Problem #5
solutions
public int oddPathSum() {
return oddPathSum(overallRoot, 0);
}
private int oddPathSum(IntTreeNode root, int sum) {
if (root == null) {
return 0;
} else {
sum += root.data;
int result =
oddPathSum(root.left, sum) + oddPathSum(root.right, sum);
if (sum % 2 != 0) {
result++;
}
return result;
}
}
---------------------------------------------------------------------------
public int oddPathSum() {
return oddPathSum(overallRoot, false);
}
private int oddPathSum(IntTreeNode root, boolean odd) {
if (root == null) {
return 0;
} else {
if (root.data % 2 != 0) {
odd = !odd;
}
int result =
oddPathSum(root.left, odd) + oddPathSum(root.right, odd);
if (odd) {
result++;
}
return result;
}
}
---------------------------------------------------------------------------
public int oddPathSum() {
return oddPathSum(overallRoot, 0, 0);
}
private int oddPathSum(IntTreeNode root, int sum, int count) {
if (root == null) {
return count;
} else {
sum += root.data;
count = oddPathSum(root.left, sum, count);
count = oddPathSum(root.right, sum, count);
if (sum % 2 != 0) {
count++;
}
return count;
}
}
---------------------------------------------------------------------------
public int oddPathSum() {
return oddPathSum(overallRoot, 0);
}
private int oddPathSum(IntTreeNode root, int n) {
if (root == null)
return 0;
n = (n + root.data) % 2;
return n + oddPathSum(root.left, n) + oddPathSum(root.right, n);
}
---------------------------------------------------------------------------
1 public header
1 overall setup: private method returning an int with a root parameter and a
second parameter that can keep track of odd path sum (e.g., sum/boolean),
public method calls private method passing it overallRoot and appropriate
starting value for second parameter, public method returns result of private
method
1 base case for null (tests for this and prevents any NullPointerException)
2 recursive calls
1 their answer includes recursive calls on root.left and root.right that
include some kind of path sum parameter
1 correctly traverses the entire tree
2 correctly computes a value that can be used for odd path sum (for these
points, don't worry about whether their tests for odd path sum are correct;
you want to look at the initial call with overallRoot, how they incorporate
root.data, and the recursive calls they are making to see if the pieces fit
together to produce a value that can be tested for odd/even path sum):
1 reasonable attempt
1 correct (requires a recursive call on both left and right, but assume the
tree is traversed correctly)
3 correctly counts odd path sums
1 reasonable attempt: testing for odd path sum and returning a different
value in that case
2 correct (-1 if minor error like obob or counting even path sums)
notes:
* a count field loses the overall setup point if private method has void return
and always loses the 2 counting correctness points
* give to question leader any solutions that change the tree or use extra data
structures (even a string)
Problem #6
solutions
public void recordGrade(Map<String, Map<String, Double>> grades,
String id, double grade, String course) {
if (!grades.containsKey(id)) {
grades.put(id, new TreeMap<String, Double>());
}
Map<String, Double> next = grades.get(id);
if (next.containsKey(course)) {
grade = Math.max(grade, next.get(course));
}
next.put(course, grade);
}
public void recordGrade(Map<String, Map<String, Double>> grades,
String id, double grade, String course) {
if (!grades.containsKey(id)) {
grades.put(id, new TreeMap<String, Double>());
}
Map<String, Double> map = grades.get(id);
if (!map.containsKey(course) || map.get(course) < grade) {
map.put(course, grade);
}
}
2 header (static is okay, non-void okay if there is a return that is
consistent, interfaces required, -1 if method name is wrong, -1 per
incorrect parameter)
3 adds student to overall map if not seen before
1 reasonable attempt to test whether ID is in the overall map
1 reasonable attempt to construct a student map (string->double) for each
student (can get this point even if they do it every time)
1 all correct (constructs a new TreeMap exactly once each time an ID is
seen for the first time and adds it to the overall map, constructed map
is a TreeMap, syntax is correct; very nitpicky, including "()" in call to
TreeMap constructor)
3 finds the max of new grade and any previously recorded grade
1 reasonable attempt to test whether grade is already in student map
1 reasonable attempt to find max of old grade and new grade
1 all correct (very nitpicky, including using "()" when necessary, but
don't take off for nitpicky syntax twice)
2 records the grade in the student map
1 reasonable attempt
1 all correct
notes:
can't get both "reasonable attempt to test in map" unless there are two maps
Problem #7
solution
public class AdmissionsEntry implements Comparable<AdmissionsEntry> {
private String ID;
private int ratings;
private double total;
private boolean discuss;
public AdmissionsEntry(String ID) {
this.ID = ID;
this.ratings = 0;
this.total = 0.0;
this.discuss = false;
}
public void rate(double rating) {
ratings++;
total += rating;
if (rating >= 4) {
discuss = true;
}
}
public void flag() {
discuss = true;
}
public String getID() {
return ID;
}
public double getRating() {
if (ratings == 0) {
return 0.0;
} else {
return total / ratings;
}
}
public String toString() {
double rating = Math.round(100 * getRating()) / 100.0;
return ID + ": " + rating;
}
public int compareTo(AdmissionsEntry other) {
if (discuss && !other.discuss) {
return -1;
} else if (!discuss && other.discuss) {
return 1;
} else if (getRating() > other.getRating()) {
return -1;
} else if (getRating() < other.getRating()) {
return 1;
} else {
return ID.compareTo(other.ID);
}
}
}
1 class header
4 fields (1 point each, -1 once if not private, okay to have extra field(s)
get 1 of 2 points for list of ratings instead of count/total)
1 constructor (can rely on defaults for ratings, total, discuss; requires
constructing list of ratings if they are using that approach)
2 rate method
1 reasonable attempt to record this rating in a field
1 all correct (requires ratings and total field or list, has to record the
score in such a way that an average can be computed)
2 correctly flagging students to be discussed (requires flag field)
1 correct flag method OR correctly flags ratings > 4 in rate method OR
reasonable attempt at both
1 correct flag method AND correctly flags ratings > 4 in rate method
1 correct getID method
2 getRating method
1 reasonable attempt
1 all correct
2 toString
1 reasonable attempt (4 of the following 7: id, colon, average rating,
dealing with ratings = 0, * 100 / 100, round, return--getRating gets both
average rating and dealing with ratings=0)
1 correct (must work when ratings=0, must round to 2 digits, must guarantee
double division, must include colon but space is not required)
5 compareTo
1 reasonable attempt to put flagged students first
1 correctly puts flagged students first
1 reasonable attempt to reverse order by ratings when flag matches
1 reasonable attempt to order by ID when flag and ratings match
1 correctly reverses order by ratings when flag matches and correctly
orders by ID when flag and ratings match
notes:
give question leader odd solutions like array of ratings
Problem #8
solutions
public void tighten() {
overallRoot = tighten(overallRoot);
}
private IntTreeNode tighten(IntTreeNode root) {
if (root != null) {
root.left = tighten(root.left);
root.right = tighten(root.right);
if (root.left == null && root.right != null) {
root = root.right;
} else if (root.left != null && root.right == null) {
root = root.left;
}
}
return root;
}
private IntTreeNode tighten(IntTreeNode root) {
if (root != null) {
if (root.left == null && root.right != null)
root = tighten(root.right);
else if (root.left != null && root.right == null)
root = tighten(root.left);
else {
root.left = tighten(root.left);
root.right = tighten(root.right);
}
}
return root;
}
private IntTreeNode tighten(IntTreeNode root) {
if (root != null) {
if (root.left == null && root.right != null)
return tighten(root.right);
else if (root.left != null && root.right == null)
return tighten(root.left);
root.left = tighten(root.left);
root.right = tighten(root.right);
}
return root;
}
1 public header
1 overall setup: private header with a root parameter and public method calls
private method passing it overallRoot
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 or modified root in all cases
2 base case for root == null
1 attempt (tested this case)
1 correct: requires test, no NullPointerException, tree not changed in this
case
3 Eliminating 1-child nodes
1 reasonable attempt to replace root with non-null child (other child null)
1 correctly resets root or returns child for one of the two 1-child cases
1 correctly resets root or returns child for other 1-child case
2 2-child case works (recursive calls for both children)
2 leaf case works assuming null test works (unchanged)--requires tests
4 recursive calls are made for 1-child cases
1 exist
3 before assignment or in assignment/return
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
solutions
public LinkedIntList removeFirstOf3() {
LinkedIntList other = new LinkedIntList();
if (front != null) {
other.front = front;
ListNode back1 = other.front;
front = front.next;
ListNode current = front;
while (current != null && current.next != null &&
current.next.next != null) {
current = current.next;
back1.next = current.next;
back1 = back1.next;
current.next = current.next.next;
current = current.next;
}
back1.next = null;
}
return other;
}
---------------------------------------------------------------------------
public LinkedIntList removeFirstOf3() {
LinkedIntList other = new LinkedIntList();
front = recurse(front, other, 1);
return other;
}
private ListNode recurse(ListNode front, LinkedIntList other, int count) {
if (front != null) {
front.next = recurse(front.next, other, count + 1);
if (count % 3 == 1) {
ListNode temp = front.next;
front.next = other.front;
other.front = front;
return temp;
}
}
return front;
}
1 header (lose this if return type is ListNode even if they return a ListNode)
2 constructs and returns other LinkedIntList
1 reasonable attempt (can get this even if they are returning a ListNode)
1 correct (requires call on LinkedIntList constructor, proper return)
2 sets next link of final node moved to list2 to null
1 reasonable attempt to set the next field to null for some node being
moved
1 correctly sets the next field to null for the final node moved in every
case they get credit for below (requires that they get a case that
required setting to null--length 2, 3, 5, 6, 8, 9, 11, 22, etc)
4 basic cases that don't require a loop (assuming final node link set to null)
1 empty list
1 length 1
1 length 2
1 length 3
2 generous pattern match
1 using curr1/curr2 variables to keep track of a position in each of the
two lists (curr2 could be other.front)
1 one of the following:
* loop that moves curr1 forward three positions in list1 (consider the
effect of code that resets current and that removes nodes from list1)
* reasonable attempt to remove from list1, as in:
curr1.next = curr1.next.next;
(requires resetting a next field)
* reasonable attempt to move a node to list2, as in:
curr2.next = curr1;
curr2.next = curr1.next;
(requires resetting a next field)
9 other specific cases (assuming final node link set to null):
1 length 4
1 length 5
1 length 6
1 length 7
1 length 8
1 length 9
1 length 16
1 length 17
1 length 18
Notes:
-1 if they say other when they mean other.front (but only if that raises their
score)
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.
Any O(n^2) solutions or odd solutions (new nodes, changing data) go to the
question leader.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011