<![CDATA[
Problem #1
solution
1. Method Call Output Produced
------------------------------------------------
mystery(7); 7
mystery(38); 838
mystery(194); 49194
mystery(782); 28782
mystery(3842); 2483842
3 points for each row.
First row is all-or-nothing. For others, they lose 1 point for each incorrect
digit or missing digit.
-0 for quotes around output
Problem #2
solution
public void showSplit(int n) {
if (n < 0) {
throw new IllegalArgumentException();
} else if (n <= 1) {
System.out.print(n);
} else {
System.out.print(n + " = (");
showSplit(n / 2 + n % 2);
System.out.print(", ");
showSplit(n / 2);
System.out.print(")");
}
}
1 header (okay if it's static, non-void return okay if consistent with code)
1 exception
4 base cases
1 testing for at least one of these
1 printing n for at least one of these
2 testing and printing for both of these
3 recursive calls for even n
1 recursive call on n / 2
2 second recursive call on n / 2
3 recursive calls for odd n
1 reasonable attempt: test for it, different calls for even/odd
2 two recursive calls that pass correctly split values (-1 if it's the
second value that gets the extra)
3 text surrounding recursive calls (has to be correct for both even and odd)
1 print statements for at least three of the four elements:
n = ( , )
1 prints all four elements in correct order with two recursive calls for
either even or odd
1 prints all four elements in correct order with two recursive calls for
both even and odd
notes
all loop or extra data structure solutions go to question leader
-1 if any prints are printlns
-3 for treating a void method as if it could print (only apply this rule if
it increases their score)
Problem #3
before after code
-----------------------+-----------------------+-------------------------------
p->[1]->[2] | p->[2] | q.next = p;
| | p = p.next;
q->[3] | q->[3]->[1] | q.next.next = null;
-----------------------+-----------------------+-------------------------------
p->[1] | p->[3] | p.next = q;
| | q = p;
| | p = p.next.next;
q->[2]->[3] | q->[1]->[2] | q.next.next = null;
-----------------------+-----------------------+-------------------------------
p->[1]->[2] | p->[3]->[2]->[1] | p.next.next = p;
| | ListNode temp = q.next;
| | q.next = p.next;
q->[3]->[4] | q->[4] | p.next = null;
| | p = q;
| | q = temp;
-----------------------+-----------------------+-------------------------------
p->[1]->[2] | p->[1]->[3]->[5] | ListNode temp = p.next;
| | p.next = q;
| | temp.next = q.next;
q->[3]->[4]->[5] | q->[2]->[4] | q.next = q.next.next;
| | q = temp;
| | q.next.next = null;
-----------------------+-----------------------+-------------------------------
3 problem 1
1 attempt: change 2 of (p, 2 ~.next)
2 correct
3 problem 2
1 attempt: change 3 of (p, q, 2 ~.next)
2 correct
4 problem 3
1 attempt: change 3 of (p, q, 3 ~.next)
1 better attempt: change 4 of (p, q, 3 ~.next)
2 correct
5 problem 4
1 attempt: change 3 of (q, 4 ~.next)
1 better attempt: change 4 of (q, 4 ~.next)
3 correct
Notes
correctness is generally atomic except:
-1 per "setting to null" error if otherwise correct
-1 per exception thrown if otherwise correct
-1 if adding or subtracting a single ".next" somewhere makes it work
can lose up to 2 syntax points if they get correctness points, examples:
-1 not declaring temp variable to be of type ListNode
-1 saying p.next() instead of p.next
-1 per occurrence (max of 2) for "p.data" instead of "p" or equivalent
Problem #4
Statement Output
------------------------------------------------------------
var1.method2(); Neck 2
var2.method2(); Leg 2
var3.method2(); Leg 2
var4.method2(); compiler error
var5.method2(); Head 2
var6.method2(); Neck 2
var1.method3(); Arm 3/Neck 2
var2.method3(); compiler error
var3.method3(); compiler error
var4.method3(); compiler error
var5.method3(); Arm 3/Head 2
var6.method3(); Arm 3/Neck 2
((Neck)var5).method1(); runtime error
((Arm)var3).method3(); Arm 3/Leg 2
((Arm)var4).method1(); compiler error
((Neck)var1).method1(); Head 1/Leg 2
((Head)var4).method1(); Head 1/Leg 2
((Arm)var2).method3(); runtime error
((Head)var3).method1(); runtime error
((Leg)var4).method2(); Head 2
1 pt each
-1 if no slashes anywhere
-0 if they put quotes around answers
Problem #5
solution
public static void rearrangeDuplicates(Queue<Integer> q) {
Stack<Integer> s = new Stack<Integer>();
if (q.size() > 1) {
int oldSize = q.size();
int prev = q.remove();
q.add(prev);
for (int i = 0; i < oldSize - 1; i++) {
int n = q.remove();
if (n != prev)
q.add(n);
else
s.push(n);
prev = n;
}
int newCount = q.size();
while (!s.isEmpty())
q.add(s.pop());
for (int i = 0; i < newCount; i++)
q.add(q.remove());
for (int i = 0; i < oldSize - newCount; i++)
s.push(q.remove());
while (!s.isEmpty())
q.add(s.pop());
}
}
1 header (-1 per error, okay if it's static)
2 constructs temporary stack using generics correctly (-1 per error)
1 test to avoid removing from an empty queue (requires separate if, loop test
doesn't count)
9 loop over values with some values going back into queue and some going into
the stack
2 reasonable attempt: attempt to remove values one or two at a time and
send some to the stack and others to the queue
1 reasonable attempt at test for duplicates: they manage to compare
adjacent pairs of values for equality (either using a prev or by always
getting a new pair)
3 correctly processes each value exactly once (requires that they are
removing from the queue and saving old queue size, -1 if obob)
3 correctly moving duplicates to one structure and unique values to the
other (requires that they are removing one value at a time from the queue
and keeping track of a previous value, -1 if their only mistake is to
fail to put the first value into the appropriate structure)
12 combination of stack/queue loops leads to correct sequence (if you can infer
what they intended for the splitting operation, then assume the split works
unless they were splitting from a stack). Simulate this case:
front [1, 1, 2, 3, 3] back
12 [1, 2, 3, 1, 3] F1 F2
10 [3, 1, 3, 2, 1] R2 R1
8 [1, 3, 1, 2, 3] F2 F1
6 [3, 2, 1, 3, 1] R1 R2
6 [3, 1, 1, 2, 3] R2 F1
4 [3, 2, 1, 1, 3] R1 F2
4 [1, 2, 3, 3, 1] F1 R2
4 [1, 3, 3, 2, 1] F2 R1
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 25 points
-12 for extra stack or other structure
-8 for temp queue instead of temp stack (pretended their structure was a stack)
Problem #6
solutions
public void removeLast(int n) {
int index = -1;
for (int i = 0; i < size; i++) {
if (elementData[i] == n) {
index = i;
}
}
if (index != -1) {
for (int j = index; j < size - 1; j++) {
elementData[j] = elementData[j + 1];
}
size--;
}
}
public void removeLast(int n) {
for (int i = size - 1; i >= 0; i--) {
if (elementData[i] == n) {
for (int j = i; j < size - 1; j++) {
elementData[j] = elementData[j + 1];
}
size--;
return;
}
}
}
1 header (non-void okay if there is a return that is consistent)
5 finding last occurrence of target value
1 loop attempt: within OBOB of examining size values or all values
1 loop with correct bounds
1 test whether elementData[i] == target value
2 finds last occurrence
1 reasonable attempt (going backwards or setting a local variable)
1 correct
4 removing target value
1 correct shifting code (elementData[i]=elementData[i + 1])
1 reasonable attempt at loop (from index to size or end of array, has to be
a separate loop from the loop to find the occurrence)
1 correct loop bounds
1 resets size in this case and only this case
Notes: -3 if they use an extra structure (array, ArrayList, etc)
-1 if they use elementData.length instead of size
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011