<![CDATA[
Problem #1
solution
1. Method Call Output Produced
------------------------------------------------
mystery(1); 1
mystery(2); 2, 1
mystery(4); 4, 2, 1
mystery(8); 8, 4, 2, 1
mystery(10); 10, 5, 16, 8, 4, 2, 1
3 points for each row.
First row is all-or-nothing. For others, they lose 1 point for each incorrect
number or missing number or comma error, although they can't go below 0 for any
single row and the comma errors should be capped at -2 for the entire problem.
Problem #2
solution
public static void printDashed(int n) {
if (n < 0) {
System.out.print("-");
printDashed(-n);
} else if (n < 10) {
System.out.print(n);
} else {
printDashed(n / 10);
System.out.print("-" + n % 10);
}
}
1 header (okay if it's static, non-void return okay if consistent)
4 recursive case for n < 0
1 attempt (some test explicitely tests for negative or they use Math.abs)
3 correct:
recursive call on negation of n
base case handles negatives as well and recursive call uses Math.abs
-1 if close (e.g., correct test and recurse on -n but don't print dash)
4 base case of one-digit number
2 attempt (test that seems to be testing for one-digit or base case of 0)
2 correct (-1 if obob)
6 recursive case for greater-than-2-digit numbers
1 attempt: recursive call on n/10 or n % 10
1 prints dash (requires recursive call)
1 prints n % 10 or n/10 (requires recursive call)
3 correct: recursive call on n/10, print n % 10, print dash in between,
correct order (-1 if minor, e.g. switch dash/digit)
Notes:
-1 if they use println
transformation:
-3 if they compute and return a String instead of printing (only apply this
rule if their score goes up)
-3 if they include recursive calls on their method inside of a print
Problem #3
solution
public int removeLast() {
if (front == null) {
throw new NoSuchElementException();
} else if (front.next == null) {
int result = front.data;
front = null;
return result;
} else {
ListNode current = front;
while (current.next.next != null) {
current = current.next;
}
int result = current.next.data;
current.next = null;
return result;
}
}
1 header
2 empty list case
1 attempt: test for this case
1 throws NoSuchElementException for this case
5 works for 1-element list
1 attempt: test for this case explicitly
2 sets front to null (requires test attempt)
2 returns front.data (requires test attempt and no NullPointerException)
7 works for 2-or-more-element list
1 attempt: loop over list using current
4 removes last value
2 returns last value of the list (-1 if it returns penultimate value)
notes:
-1 if they use list.isEmpty()
solutions with size() should go to question leader
Problem #4
Statement Output
------------------------------------------------------------
var1.method1(); Peak 1/Cliff 3/Peak 3
var2.method1(); Peak 1/Gorge 3
var3.method1(); Peak 1/Hill 3
var4.method1(); Peak 1/Gorge 3
var5.method1(); Peak 1/Peak 3
var6.method1(); compiler error
var1.method2(); compiler error
var2.method2(); Gorge 2
var3.method2(); compiler error
var1.method3(); Cliff 3/Peak 3
var2.method3(); Gorge 3
var3.method3(); Hill 3
((Gorge)var6).method1(); runtime error
((Cliff)var3).method2(); compiler error
((Gorge)var4).method2(); Gorge 2
((Gorge)var3).method2(); runtime error
((Hill)var3).method2(); Hill 2
((Gorge)var1).method1(); runtime error
((Cliff)var4).method3(); Gorge 3
((Peak)var6).method3(); Cliff 3/Peak 3
1 pt each
-1 if no slashes anywhere
Problem #5
solution
public static int removeMin(Stack<Integer> s) {
Queue<Integer> q = new LinkedList<Integer>();
int min = s.pop();
q.add(min);
while (!s.isEmpty()) {
int next = s.pop();
if (next < min)
min = next;
q.add(next);
}
while (!q.isEmpty()) {
int next = q.remove();
if (next != min)
s.push(next);
}
while (!s.isEmpty())
q.add(s.pop());
while (!q.isEmpty())
s.push(q.remove());
return min;
}
2 header (-1 per error)
2 constructs temporary queue using generics correctly (-1 per error)
4 first S -> Q, Q -> S
2 attempt
2 correct
4 second S -> Q, Q -> S
2 attempt
2 correct
4 initialize min
1 attempt (e.g., 0)
1 correct value (typically first value)
2 preserves sequence
3 computes min on some pass
1 attempt
2 correct
4 removes min on some pass (only if they remove after computing min)
1 attempt
1 removes the min at least once
2 removes all occurrences of the min
2 returns min at the end
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)
computing and removing the min on the same pass
Problem #6
solution
public void mirror() {
int last = 2 * size - 1;
for (int i = 0; i < size; i++) {
elementData[last - i] = elementData[i];
}
size = size * 2;
}
1 header (non-void return type okay if consistent with a return)
2 for loop that executes size times (-1 if obob)
5 assigning mirror image
1 elementData[expr1] = elementData[expr2]
2 expr1 ranges from size to (2 * size - 1)
-1 if the expression has an obob
no double jeopardy with loop obob
2 expr2 matches expr1 (-1 if obob)
2 resets size to 2*size
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011