<![CDATA[
Problem #1
Preorder traversal 2, 0, 5, 1, 7, 6, 3, 4, 9, 8
Inorder traversal 1, 5, 0, 7, 6, 2, 3, 9, 4, 8
Postorder traversal 1, 5, 6, 7, 0, 9, 8, 4, 3, 2
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 #3
Statement Output
------------------------------------------------------------
var1.method1(); Blue 1/Blue 2
var2.method1(); Green 1
var3.method1(); compiler error
var4.method1(); Green 1
var1.method2(); Blue 2
var2.method2(); Red 2/Blue 2
var3.method2(); compiler error
var4.method2(); Red 2/Blue 2
var1.method3(); compiler error
var2.method3(); Green 3
var3.method3(); compiler error
var4.method3(); compiler error
((Blue)var3).method1(); Blue 1/White 2
((Red)var3).method2(); White 2
((White)var3).method3(); White 3
((White)var4).method3(); runtime error
((Green)var5).method3(); runtime error
((Red)var5).method1(); Blue 1/Red 2/Blue 2
((Blue)var6).method3(); compiler error
((Green)var6).method3(); runtime error
1/2 each (half points okay)
-1/2 if no slashes anywhere
-0 if they put quotes around answers
problem #2
solutions
public int weave(int x, int y) {
if (x < 0 || y < 0) {
throw new IllegalArgumentException();
}
if (x == 0 && y == 0) {
return 0;
} else {
return 100 * weave(x / 10, y / 10) + 10 * (x % 10) + y % 10;
}
}
public int weave(int a, int b) {
if (a < 0 || b < 0) {
throw new IllegalArgumentException();
}
if (a < 10 && b < 10) {
return a * 10 + b;
} else {
return weave(a / 10, b / 10) * 100 + weave(a % 10, b % 10);
}
}
ways to test if a non-negative integer x is a 1-digit number:
x < 10
x / 10 == 0
x % 10 == x
1 header (static is okay)
1 correct exception
3 base case
1 reasonable attempt to test x and y for 0 or 1-digit
1 correct test: either both 0 or both 1-digit or equivalent
1 correct return (requires correct test):
if (x == 0 && y == 0) { return 0; }
if (x < 10 && y < 10) { return 10 * x + y; }
note: -1 from correctness if there are extra base cases that don't work
4 recursive case
3 correct expression elements:
100 * weave(x / 10, y / 10) + 10 * (x % 10) + y % 10;
+---+ +-------------------+ +--+ +------+ +----+
0.5 1 0.5 0.5 0.5
1 pieces fit together:
* this is in an else branch relative to a base case or has a test that
makes some kind of sense
* they are adding together at least 2 of these elements
* they are returning the sum of the elements they are adding together
* no extraneous code or other recursive cases that don't work
notes:
* All loop, extra data structure, string solutions go to question leader.
* If they have 2 or more recursive cases, give them the max of the "correct
expression elements" rather than the sum
Problem #4
solution
public void mirrorCollapse(Stack<Integer> s) {
Queue<Integer> q = new LinkedList<Integer>();
while (!s.isEmpty()) {
q.add(s.pop());
}
int oldSize = q.size();
for (int i = 0; i < oldSize / 2; i++) {
s.push(q.remove());
}
if (oldSize % 2 == 1) {
q.add(q.remove());
}
while (!s.isEmpty()) {
q.add(q.remove() + s.pop());
}
while (!q.isEmpty()) {
s.push(q.remove());
}
}
// correct solution, but is O(n^2)
public static void mirrorCollapse(Stack<Integer> s) {
Queue<Integer> q = new LinkedList<Integer>();
while (!s.isEmpty()) {
q.add(s.pop());
}
int loop = q.size() / 2;
for (int i = 0; i < loop; i++) {
int sum = q.remove();
int count = q.size() - 1;
for (int k = 0; k < count; k++) {
q.add(q.remove());
}
sum = sum + q.remove();
s.push(sum);
}
while (!s.isEmpty()) {
q.add(s.pop());
}
while (!q.isEmpty()) {
s.push(q.remove());
}
}
example of a solution that gets everything right other than the fact that
it adds together the wrong pairs:
public static void mirrorCollapse(Stack<Integer> s) {
Queue<Integer> q = new LinkedList<Integer>();
for (int i = 0; i < s.size(); i++) {
q.add(s.pop());
}
while (!s.isEmpty()) {
q.add(q.remove() + s.pop());
}
while (!q.isEmpty()) {
s.push(q.remove());
}
}
1 header (static okay, non-void okay if there is a return that is consistent)
1 constructs temporary queue using generics correctly
1 simple cases
0.5 does nothing, no exception for empty stack based on tests
0.5 does nothing, no exception for size-1 stack based on tests
1 initial s->q loop (ok if it transfers only half of the values)
2 collapsing loop that contains:
q.add(q.remove() + s.pop());
be on the lookout for equivalent approaches, as in weaving pairs of values
together with a loop that does something like this:
q.add(q.remove())
q.add(s.pop());
and then another loop that adds successive pairs from the queue, putting them
either back into the queue or into the stack
1 reasonable attempt (e.g., s.push(q.remove() + q.remove()))
1 correct (lose this if the test is something infinite like !q.isEmpty())
1 ends with a q->s loop (ok if it transfers only half of the values)
3 actually works (no double jeopardy with initial/final loops, but they can't
get full credit for those loops if you have to change them to get them
points here...take off the points there instead if it leads to a higher
score; question leader can authorize lesser deductions like -1 for an OBOB)
0.5 works for length 2
0.5 works for length 3
0.5 works for length 4
0.5 works for length 5
0.5 works for length 8
0.5 works for length 9
Notes:
no parens for calls like q.remove() is a syntax mistake (could be free)
naming errors where you can infer what they meant are -1 each, max -2:
while (!s.isEmpty()) { q.add(s.remove()); }
testing program has s2q and q2s methods, but ONLY use these for the
simplest of while loops that match exactly, not for for loops
-2 if it isn't O(n)
-2 for using peek
Give to question leader all solutions that involve:
peek, foreach loop, iterator, or other illegal stack/queue operations
constructing a temporary structure other than a queue (e.g., a 2nd stack)
nonworking solution that gets 10 points
Problem #5
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 #6
solutions
public List<Integer> inorderList() {
List<Integer> result = new ArrayList<Integer>();
inorderList(overallRoot, result);
return result;
}
private void inorderList(IntTreeNode root, List<Integer> result) {
if (root != null) {
inorderList(root.left, result);
result.add(root.data);
inorderList(root.right, result);
}
}
public List<Integer> inorderList() {
List<Integer> result = new ArrayList<Integer>();
return inorderList(overallRoot, result);
}
private List<Integer> inorderList(IntTreeNode root, List<Integer> list) {
if (root != null) {
if (root.left == null && root.right == null) {
list.add(root.data);
} else {
list = inorderList(root.left, list);
list.add(root.data);
list = inorderList(root.right, list);
}
}
return list;
}
3 public method
1 correct header (ArrayList<Integer> okay for this point) and method calls
private method passing overallRoot
1 constructs an ArrayList and stores it in a local variable (lose this if
they try to construct a List<Integer> or if they try to have a field)
1 other details correct: header and local variable are of type
List<Integer>, list is constructed before call on private method and
returned after call on private method
1 private header correct (passing a root parameter and a List<Integer>
parameter but they can use ArrayList<Integer> if they already lost a point
for not using List<Integer> as a type in the public method)
1 base case for null (tests for this, does nothing, always avoids exception)
2 recursive calls
1 reasonable attempt to recurse on left and right subtrees (can get this
even without list being a parameter)
1 correct recursive calls (requires list parameter, traverses entire tree
in correct order, not doing odd things like destructive x=change(x))
3 adding root data to list
1 reasonable attempt to add root.data to list
2 correctly adds (has to be done once in between recursive calls on left
and right; can get this even if they don't have a list parameter)
Problem #7
solutions:
public static void printDuplicates(Scanner input) {
String prevToken = input.next();
int count = 1;
while (input.hasNext()) {
String nextToken = input.next();
if (nextToken.equals(prevToken)) {
count++;
} else if (count > 1) {
System.out.println(prevToken + "*" + count);
count = 1;
}
prevToken = nextToken;
}
if (count > 1) {
System.out.println(prevToken + "*" + count);
}
}
public static void printDuplicates(Scanner input) {
String prev = input.next();
int counter = 1;
while (input.hasNext()) {
String curr = input.next();
if (prev.equals(curr)) {
counter++;
}
if (counter > 1 && (!prev.equals(curr) || !input.hasNext())) {
System.out.println(prev + "*" + counter);
counter = 1;
}
prev = curr;
}
}
public static void printDuplicates(Scanner input) {
String prev = input.next();
int count = 1;
while (input.hasNext()) {
String next = input.next();
while (input.hasNext() && next.equals(prev)) {
count++;
next = input.next();
}
if (next.equals(prev)) {
count++;
}
if (count > 1) {
System.out.println(prev + "*" + count);
}
count = 1;
prev = next;
}
}
1 header (non-void return type ok if consistent with a return statement)
1 correct loop (testing on hasNext)
6 counting sequences
1 reasonable attempt for two of these three:
* initialize a counter
* increment counter in a loop
* compare two consecutive tokens for equality
2 count is updated correctly (initially 1, reset to 1 when change is seen,
-1 if OBOB)
1 correctly testing if two consecutive tokens are equal (requires equals)
2 correct setup to recognize sequences (read one token outside loop, read
exactly one inside the loop, remember previous token)
2 printing sequences other than a sequence at the end
1 reasonable attempt to print duplicate once inside loop when count is
greater than 1
1 all printing correct and done at the correct time (correct format, prints
once when transition is seen assuming consecutive token test worked)
1 correctly handles last sequence and all printing is done correctly (generally
requires correct setup)
Problem #8
solutions
public class USCurrency implements Comparable<USCurrency> {
private int totalCents;
public USCurrency(int dollars, int cents) {
totalCents = dollars * 100 + cents;
}
public int dollars() {
return totalCents / 100;
}
public int cents() {
return totalCents % 100;
}
public String toString() {
int cents = Math.abs(totalCents);
String s = cents / 100 + "." + cents % 100 / 10 + cents % 10;
if (totalCents < 0) {
return "-$" + s;
} else {
return "$" + s;
}
}
public int compareTo(USCurrency other) {
return totalCents - other.totalCents;
}
}
public class USCurrency implements Comparable<USCurrency> {
private int dollars;
private int cents;
public USCurrency(int dollars, int cents) {
int totalCents = 100 * dollars + cents;
this.dollars = totalCents / 100;
this.cents = totalCents % 100;
}
public int dollars() {
return dollars;
}
public int cents() {
return cents;
}
public String toString() {
String s = Math.abs(dollars) + ".";
if (Math.abs(cents) < 10) {
s += "0" + Math.abs(cents);
} else {
s += Math.abs(cents);
}
if (dollars < 0 || cents < 0) {
return "-$" + s;
} else {
return "$" + s;
}
}
public int compareTo(USCurrency other) {
return dollars * 100 + cents - other.dollars * 100 - other.cents;
}
}
1 correct class header and correct constructor (header,, sets fields
appropriately)
1 fields (okay to have extra field(s), -1 if any aren't private or if they are
using a totalCents approach and have no field)
3 proper conversion of dollars/cents
dollars/cents approach: correctly changes dollars/cents in constructor or
computes in dollars/cents methods
1 attempt: recognized this issue and attempted to correct
1 correct when both positive or both negative
1 correct in all cases
total cents approach: computing total cents and converting in dollars/cents
methods
1 correctly computes total cents
1 attempt to convert: using %10 and /10 to compute separate values in
dollars/cents methods
1 correct
1 dollars and cents methods (correct headers, appropriate return value, no
double jeopardy with conversion)
3 toString
1 separate code for negative values based on a test or use of Math.abs
1 separate case for single digit cents or use of mod to generate two
individual digits
1 all correct (-1 if minor formatting error)--note that the totalCents
solutions can lose this if they have incorrect expressions even if they
lost the points under conversion (but no double jeopardy if they call the
dollars and cents methods)
1 correct compareTo
Problem #9
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.
Problem #10
solutions
// like switchPairs, one temp, 3 assignments to .next in loop
public void switchPairsOfPairs() {
if (front != null && front.next != null &&
front.next.next != null && front.next.next.next != null) {
ListNode current = front.next.next;
front.next.next = current.next.next;
current.next.next = front;
front = current;
current = current.next.next.next;
while (current.next != null && current.next.next != null &&
current.next.next.next != null &&
current.next.next.next.next != null) {
ListNode temp = current.next.next.next;
current.next.next.next = temp.next.next;
temp.next.next = current.next;
current.next = temp;
current = temp.next.next.next;
}
}
}
// solution that changes just 2 .next fields in the loop with a final
// .next set after the loop
public void switchPairsOfPairs() {
if (front != null && front.next != null &&
front.next.next != null && front.next.next.next != null) {
ListNode current = front.next.next;
ListNode temp1 = current.next.next;
current.next.next = front;
front = current;
current = current.next.next.next;
while (temp1 != null && temp1.next != null &&
temp1.next.next != null &&
temp1.next.next.next != null) {
ListNode temp2 = temp1.next.next;
ListNode temp3 = temp1;
temp1 = temp2.next.next;
temp2.next.next = temp3;
current.next = temp2;
current = temp2.next.next.next;
}
current.next = temp1;
}
}
// solution with two temps
public void switchPairsOfPairs() {
if (front != null && front.next != null &&
front.next.next != null && front.next.next.next != null) {
ListNode temp1 = front.next.next;
ListNode temp2 = temp1.next.next;
temp1.next.next = front;
front.next.next = temp2;
ListNode current = front.next;
front = temp1;
while (current.next != null && current.next.next != null &&
current.next.next.next != null &&
current.next.next.next.next != null) {
temp1 = current.next.next.next;
temp2 = temp1.next.next;
temp1.next.next = current.next;
current.next.next.next = temp2;
current.next = temp1;
current = current.next.next.next.next;
}
}
}
// recursive solution
public void switchPairsOfPairs() {
front = switchPairsOfPairs(front);
}
public ListNode switchPairsOfPairs(ListNode list) {
if (list != null && list.next != null &&
list.next.next != null && list.next.next.next != null) {
ListNode temp = list.next.next;
list.next.next = temp.next.next;
temp.next.next = list;
list = temp;
list.next.next.next.next =
switchPairsOfPairs(list.next.next.next.next);
}
return list;
}
1 header (non-void okay if there is a return that is consistent)
2 simples cases: can't get these for no code...each requires a test
0.5 length 0 case: does nothing and doesn't throw an exception
0.5 length 1 case: does nothing and doesn't throw an exception
0.5 length 2 case: does nothing and doesn't throw an exception
0.5 length 3 case: does nothing and doesn't throw an exception
2 generous pattern match
1 using a "current" variable in a loop to keep track of a position in the
list
1 resetting at least three "next" fields in a loop or resetting two in a
loop and resetting one after the loop
10 other specific cases
2 length 4
1 length 5
1 length 6
1 length 7
1 length 8
0.5 length 9
0.5 length 10
0.5 length 11
0.5 length 12
1 length 16
1 length 20
notes:
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). 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