<![CDATA[
Problem #1
solution
Method Call Value Returned
-----------------------------------------------
mystery(42, 0) 0
mystery(5, 25) 1
mystery(752, 792) 2
mystery(3092, 5028) 1
mystery(61903, 1930) 2
3 points for each
Problem #3
Statement Output
------------------------------------------------------------
var1.method1(); compiler error
var2.method1(); Doll 1
var1.method2(); Truck 2/Ball 2/Truck 3
var2.method2(); Doll 2
var3.method2(); Truck 2/Ball 2/Block 3
var4.method2(); compiler error
var5.method2(); Truck 2/Ball 2/Block 3
var1.method3(); Truck 3
var2.method3(); Ball 3
var3.method3(); Block 3
var4.method3(); compiler error
var5.method3(); Block 3
((Doll)var3).method1(); runtime error
((Block)var5).method1(); Block 1
((Truck)var3).method1(); compiler error
((Truck)var3).method3(); Block 3
((Block)var6).method3(); runtime error
((Ball)var4).method2(); Ball 2
((Truck)var4).method3(); runtime error
((Doll)var6).method3(); Ball 3
1 pt each
-1 if no slashes anywhere
-0 if they put quotes around answers
Problem #4
before after code
-----------------------+-----------------------+-------------------------------
p->[1]->[2] | p->[1] | q.next = p.next;
q->[3] | q->[3]->[2] | p.next = null;
-----------------------+-----------------------+-------------------------------
p | p->[1] | p = q;
| | q = q.next;
q->[1]->[2]->[3] | q->[2]->[3] | p.next = null;
-----------------------+-----------------------+-------------------------------
p->[1]->[2]->[3] | p->[3]->[1] | p.next.next.next = p;
| | p = p.next.next;
q->[4] | q->[2]->[4] | p.next.next.next = q;
| | q = p.next.next;
| | p.next.next = null;
-----------------------+-----------------------+-------------------------------
p->[1] | p->[5]->[1]->[3] | p.next = q.next;
| | q.next.next.next.next = p;
q->[2]->[3]->[4]->[5] | q->[4]->[2] | p = q.next.next.next;
| | q.next.next.next = q;
| | q = q.next.next;
| | q.next.next = null;
| | p.next.next.next = null;
-----------------------+-----------------------+-------------------------------
2 problem 1
1 attempt: change 2 of (2 ~.next)
1 correct
3 problem 2
1 attempt: change 2 of (p, q, 1 ~.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
6 problem 4
1 attempt: change 4 of (p, q, 5 ~.next)
1 better attempt: change 6 of (p, q, 5 ~.next)
4 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 (categorical)
-1 saying p.next() instead of p.next (categorical)
-1 per occurrence (max of 2) for "p.data" instead of "p" or equivalent
if they construct new list nodes:
-1 if they don't use them
lose all correctness for any subproblem that relies on the new nodes
if they use more than 2 temp variables:
-2 from correctness per subproblem
Problem #5
solutions
// loop that executes size/2 times by using i+=2
public ArrayIntList fromCounts() {
ArrayIntList result = new ArrayIntList();
int size2 = 0;
for (int i = 0; i < size; i += 2) {
for (int j = 0; j < elementData[i]; j++) {
result.elementData[size2] = elementData[i + 1];
size2++;
}
}
result.size = size2;
return result;
}
// loop that executes size times using index%2
public ArrayIntList fromCounts() {
ArrayIntList list2 = new ArrayIntList();
int times = 0;
for (int i = 0; i < size; i++) {
if (i % 2 == 0) {
times = elementData[i];
} else {
for (int j = 0; j < times; j++) {
list2.elementData[list2.size] = elementData[i];
list2.size++;
}
}
}
return list2;
}
// loop that executes size/2 times by using size/2
public ArrayIntList fromCounts() {
ArrayIntList other = new ArrayIntList();
int count = 0;
for (int i = 0; i < size / 2; i++) {
int times = elementData[2 * i];
int value = elementData[2 * i + 1];
for (int j = 0; j < times; j++) {
other.elementData[count] = value;
count++;
}
other.size += times;
}
return other;
}
1 header
1 construct a new ArrayIntList
2 loop over pairs
1 attempt (some kind of for loop involving size or elementData.length)
1 iterates exactly (size/2) times or has an if/else based on index%2
4 expanding each (times/value) pair
1 attempt (inner loop whose bounds are related to elementData[i] (or i+1)
1 inner loop with correct loop bounds (# of iterations = times)
2 inner loop correctly adds copies of value to 2nd ArrayIntList in correct
positions (-1 if obob with indexes, no double jeopardy with bounds)
1 correctly sets result.size (no double jeopardy with other mistakes, but
requires loop AND expand attempt)
1 returns their result
Problem #6
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)
2 constructs temporary queue using generics correctly (-1 per error)
1 does nothing and no exception for empty stack based on tests (loop tests ok)
1 does nothing and no exception for size-1 stack based on tests (loop tests ok)
2 initial s->q loop (ok if it transfers only half of the values)
1 reasonable attempt
1 correct
6 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()))
5 correct (-2 if the test is something infinite like !q.isEmpty())
2 ends with a q->s loop (ok if it transfers only half of the values)
1 attempt
1 correct
10 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 -2 for an OBOB)
2 works for length 2
2 works for length 3
1 works for length 4
1 works for length 5
1 works for length 8
1 works for length 9
1 works for length 12
1 works for length 13
Notes:
-3 from the 5 correctness points if it isn't O(n)
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()); }
you can charge them 4 points to reverse their answer at the end of the
method...only apply if their score goes up
testing program has s2q and q2s methods, but ONLY use these for the
simplest of while loops that match exactly, not for for loops
-3 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 25 points
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011