<![CDATA[
Problem #1
Preorder traversal 3, 5, 9, 6, 0, 2, 7, 8, 4, 1
Inorder traversal 3, 0, 6, 2, 9, 5, 4, 8, 7, 1
Postorder traversal 0, 2, 6, 9, 4, 8, 1, 7, 5, 3
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
+------------+
| Luke |
+------------+
/ \
/ \
+------------+ +------------+
| Kylo | | Poe |
+------------+ +------------+
/ / \
/ / \
+------------+ +------------+ +------------+
| BB8 | | Maz | | Rey |
+------------+ +------------+ +------------+
\
\
+------------+
| Finn |
+------------+
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 problem
2 pt for second problem
2 pt for third problem
-1 for order error (just once for the entire question)
-1 for duplicates (just once for the entire question)
-1 for missing number
-1 for extra number
no subproblem can go negative
Problem #4
solution
public void recordTrip(Map<String, Set<String>> trips,
String person, String place) {
if (!trips.containsKey(person)) {
trips.put(person, new TreeSet<String>());
}
trips.get(person).add(place);
}
1 correct header (static is okay)
3 adds student to overall map if not seen before
1 reasonable attempt to test whether person is in the map
1 reasonable attempt to construct a place-name set that they associate with
the person (can get this point even if they do it every time, can be
HashSet)
1 all correct (constructs a new TreeSet exactly once each time a person is
seen for the first time and adds it to the overall map; very nitpicky,
but missing parens are a syntax error that could be free)
1 correctly adds the place name to the set for the given person
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
solutions
// using a list iterator to remove
public Set<Point> removePoints(Map<Integer, List<Point>> points, int n) {
Set<Point> removed = new HashSet<Point>();
if (points.containsKey(n)) {
Iterator<Point> itr = points.get(n).iterator();
while (itr.hasNext()) {
Point p = itr.next();
if (p.getX() < p.getY()) {
itr.remove();
removed.add(p);
}
}
}
return removed;
}
// standard traversal for loop using get/size calling list remove with i--
public Set<Point> removePoints(Map<Integer, List<Point>> points, int n) {
Set<Point> removed = new HashSet<Point>();
if (points.containsKey(n)) {
List<Point> list = points.get(n);
for (int i = 0; i < list.size(); i++) {
Point p = list.get(i);
if (p.getX() < p.getY()) {
list.remove(i);
removed.add(p);
i--;
}
}
}
return removed;
}
// backwards traversal for loop using get/size calling list remove
public Set<Point> removePoints(Map<Integer, List<Point>> points, int n) {
Set<Point> removed = new HashSet<Point>();
if (points.containsKey(n)) {
List<Point> list = points.get(n);
for (int i = list.size() - 1; i >= 0; i--) {
Point p = list.get(i);
if (p.getX() < p.getY()) {
list.remove(i);
removed.add(p);
}
}
}
return removed;
}
// forward while loop traversal with if/else using get/size/remove
public Set<Point> removePoints(Map<Integer, List<Point>> points, int n) {
Set<Point> removed = new HashSet<Point>();
if (points.containsKey(n)) {
List<Point> list = points.get(n);
int i = 0;
while (i < list.size()) {
Point p = list.get(i);
if (p.getX() < p.getY()) {
list.remove(i);
removed.add(p);
} else {
i++;
}
}
}
return removed;
}
1 header (static is okay)
2 construct and return proper set
1 reasonable attempt to construct a set of points
1 all correct (correct generics, correct return, set is a HashSet, used Set
interface for variable; very nitpicky, but missing parens are a syntax
error that could be free)
1 correctly returning empty set when index is not a key of the map (requires a
test for this case)
1 correctly accessing the list for the given index
5 loop over the list
1 appropriate code to loop over the list examining each point exactly once
(lose this if they skip some values)
1 correct test to see if a point should be removed (requires getX/getY)
1 adds points to the set based on some kind of test
1 correct command to remove points from the list based on some kind of test
(can get this even if they are calling list remove with iterator)
1 handles 2-in-a-row properly and no concurrent modification exception
(usually requires iterator remove, i--, backwards loop, or while/if/else)
notes:
foreach that removes in the loop gets all but the final loop point
foreach that adds to set followed by foreach that removes loses final loop
point (doesn't handle duplicates)
weird solution that works: foreach adding to set, then list.removeAll(set)
array style notation or other odd code goes to question leader
Problem #7
solution
public class ItemOrder implements Comparable<ItemOrder> {
private String item;
private int quantity;
private int pricePer;
private String note;
public ItemOrder(String item, int quantity, int pricePer) {
this(item, null, quantity, pricePer);
}
public ItemOrder(String item, String note, int quantity,
int pricePer) {
this.item = item;
this.note = note;
this.quantity = quantity;
this.pricePer = pricePer;
}
public String getItem() {
return item;
}
public int getPrice() {
return quantity * pricePer;
}
public String toString() {
String text = "item #" + item;
if (note != null) {
text += " (" + note + ")";
}
text = text + ": " + quantity + "@" + moneyString(pricePer) +
" = " + moneyString(getPrice());
return text;
}
private String moneyString(int cents) {
return "$" + cents / 100 + "." + cents % 100 / 10 + cents % 10;
}
public int compareTo(ItemOrder other) {
if (!item.equals(other.item)) {
return item.compareTo(other.item);
} else {
return other.getPrice() - getPrice();
}
}
}
1 class header
4 fields (1 point each, -1 if not private, okay to have extra field(s))
3 two constructors
1 reasonable attempt for 3-argument constructor
1 reasonable attempt for 4-argument constructor
1 both correct (assign fields, etc)
1 getItem correct (does NOT include optional text)
2 getPrice
1 reasonable attempt
1 correct (not pricePer, but total price)
5 toString
3 converting pricePer and total price to a string:
1 reasonable attempt to include pricePer/100 and total/100 in a string
1 reasonable attempt to handle cents with leading or trailing 0 (can
get this for dividing by 100.0, but not for dividing by 100)
1 correctly converts both to text
1 correctly handles optional note (adding parenthesized note in that case
and only that case)
1 otherwise correct (includes all required pieces, correct formatting,
pieces fit together, string is returned, correct header, etc)
4 compareTo
1 attempt to compare the item numbers (some kind of test, attempt to call
compareTo on the strings)
1 attempt to compare the prices (could be comparing pricePer, return
some kind of difference)
1 correct order (item numbers first, then price)
1 all correct including header
notes:
when they call a method like getPrice(), we assume it works, but if they repeat
a mistake from getPrice in a method like toString, then they lose correctness
in both places
Problem #8
solution
public void makeFull() {
overallRoot = makeFull(overallRoot, 1);
}
private IntTreeNode makeFull(IntTreeNode root, int level) {
if (root != null) {
if (root.left == null && root.right != null) {
root = new IntTreeNode(-level, root, root.right);
root.left.right = null;
} else if (root.left != null && root.right == null) {
root = new IntTreeNode(-level, root.left, root);
root.right.left = null;
}
root.left = makeFull(root.left, level + 1);
root.right = makeFull(root.right, level + 1);
}
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) (if you think they didn't need it, show to quest 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 (test for it, do nothing, never get a NullPointerException)
2 correctly computes level
1 level parameter in private method
1 correctly computes the level on each call (tend to lose this for ++)
4 adding new nodes: 1-child cases
1 correct test for one of the 1-child cases
1 correctly constructs a node with the same child as the old root and with
the old root as a child where there was an empty subtree for one case
(should have data that is minus level, but no double jeopardy with level
computation)
1 correct test for second 1-child case
1 correct construction for second 1-child case (can get this if there is a
minor error that lost the first node construction point)
3 severing links for old parent nodes
2 correctly sets old child link to null for one case
1 correctly sets old child link to null for second case
2 correct recursive calls are made for 2-child case (left and right)
2 recursive calls are made for 1-child cases (lose these if they set children
to null)
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.
If they call 0-argument or 1-argument node constructor, that is a syntax error
first syntax error is free, then -1 per syntax category, max -2
Problem #9
solutions
public void switchEvens(LinkedIntList other) {
if (front != null && other.front != null) {
ListNode temp = other.front;
other.front = front;
front = temp;
temp = front.next;
front.next = other.front.next;
other.front.next = temp;
ListNode curr1 = front.next;
ListNode curr2 = other.front.next;
while (curr1 != null && curr2 != null && curr1.next != null &&
curr2.next != null) {
temp = curr2.next;
curr2.next = curr1.next;
curr1.next = temp;
temp = curr2.next.next;
curr2.next.next = curr1.next.next;
curr1.next.next = temp;
curr1 = curr1.next.next;
curr2 = curr2.next.next;
}
}
}
---------------------------------------------------------------------------
public void switchEvens(LinkedIntList other) {
if (front != null && other.front != null) {
ListNode temp = other.front;
other.front = front;
front = temp;
ListNode curr1 = front;
ListNode curr2 = other.front;
int count = 0;
while (curr1.next != null && curr2.next != null) {
count++;
temp = curr2.next;
curr2.next = curr1.next;
curr1.next = temp;
curr1 = curr1.next;
curr2 = curr2.next;
}
if (count % 2 == 0) {
temp = curr2.next;
curr2.next = curr1.next;
curr1.next = temp;
}
}
}
1 header (lose this if return type is ListNode even if they return a ListNode)
2 testing for empty lists
1 reasonable attempt to test whether this list or other list is empty
1 correctly tests for either list being empty, doing nothing in those cases
2 generous pattern match
1 using curr1/curr2 variables to keep track of a position in each of the
two lists
1 resetting at least two "next" fields in a loop
15 other specific cases
2 length 1/1
1 length 2/2
1 length 3/3
1 length 4/4
1 length 5/5
1 length 6/6
1 length 7/7
1 length 1/2
1 length 2/3
1 length 3/4
1 length 8/12
1 length 10/15
1 length 9/13
1 length 11/14
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. A single correction would involve adding or
deleting a single line of code like curr=curr.next or changing a test for
something like curr!=null to be curr.next!=null (this could be a double-change
to parallel curr1/curr2). Another change to consider is calling a special
method included in the grading program called switchFronts that switches the
fronts of the lists. Any such change costs 5 points and we are willing to make
only ONE such change.
Another example of a change would be if they use a name like "curr" when they
have variables with names like "curr1" and "curr2", so we don't know which one
they mean. That would require a 5-point charge.
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