<![CDATA[
Problem #1
solution
Method Call Output Produced
------------------------------------------------
mystery(3, 3); =3=
mystery(5, 1); *
mystery(1, 5); 5 4 =3= 2 1
mystery(2, 7); 7 6 5 * 4 3 2
mystery(1, 8); 8 7 6 5 * 4 3 2 1
3 points for each
lose 1 point for a character of the output that is missing or an extra
character of output or a pair of transposed characters
-0 for quotes around output
Problem #2
solution
public String undouble(String s) {
if (s.length() < 2) {
return s;
} else if (s.charAt(0) == s.charAt(1)) {
return s.charAt(0) + undouble(s.substring(2));
// could instead be: return undouble(s.substring(1));
} else {
return s.charAt(0) + s.charAt(0) + undouble(s.substring(2));
}
}
1 header (static okay)
4 base cases
1 attempt to test string length of 0 or 1 or testing for equality with
empty string (can get this even if syntax is bad)
1 returns empty string without throwing an exception for empty string
2 returns original string without throwing an exception for 1-char string
4 basic idea (don't take off for syntax for these)
1 testing whether the first and second characters are equal
1 recurse with a shorter string by calling substring(1) or substring(2)
1 correctly combines one of the 2 chars with recursive call on substring(1)
or substring(2)
1 separate recursive call on either substring(1) or substring(2) without
including one of the 2 chars
6 correct for strings of length 2 or more
2 correctly tests whether first 2 characters are equal
2 works when first 2 characters are equal
2 works when first 2 characters are not equal (must be a call using
substring(1))
syntax deductions (categorical, first 2 could be their one free syntax mistake)
-1 for confusing equals and == on string/char
-1 for confusing length/length()/size/size()
-1 for failing to say "return" with a recursive call
notes: All loop or extra data structure solutions go to question leader. The
criteria assume students are looking at the front characters of a
string, but you should adjust appropriately for other approaches that
work (e.g., they look at the last characters or they introduce a private
method with an index parameter).
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 pt each
-1 if no slashes anywhere
-0 if they put quotes around answers
Problem #4
before after code
-----------------------+-----------------------+-------------------------------
p->[1] | p | q.next.next = p;
| | p = null;
q->[2]->[3] | q->[2]->[3]->[1] |
-----------------------+-----------------------+-------------------------------
p->[1]->[2]->[3] | p->[2]->[3] | q = p;
| | p = p.next;
q | q->[1] | q.next = null;
-----------------------+-----------------------+-------------------------------
p->[1]->[2] | p->[2] | q.next.next = q;
| | q = q.next;
q->[3]->[4] | q->[4]->[3]->[1] | q.next.next = p;
| | p = p.next;
| | q.next.next.next = null;
-----------------------+-----------------------+-------------------------------
p->[1]->[2] | p->[4]->[2]->[3] | q.next.next.next = p;
| | ListNode temp = q;
q->[3]->[4]->[5] | q->[5]->[1] | q = q.next.next;
| | temp.next.next = q.next.next;
| | p.next.next = temp;
| | p = temp.next;
| | p.next.next.next = null;
| | q.next.next = null;
-----------------------+-----------------------+-------------------------------
2 problem 1
1 attempt: change 2 of (p, 1 ~.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 all 5 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
solution
public void insertAt(int index, int n, int value) {
if (index < 0 || index > size || n < 0) {
throw new IllegalArgumentException();
}
for (int i = size - 1; i >= index; i--) {
elementData[i + n] = elementData[i];
}
for (int i = 0; i < n; i++) {
elementData[i + index] = value;
}
size += n;
}
1 header (non-void okay if there is a return that is consistent)
3 exception and resetting size
1 reasonable attempt for exception (two of (3 tests + exception))
1 reasonable attempt to reset size
1 exception correct and reset size is correct (adds n to size if inserting
loop executes n times--can't be the same loop as the shifting loop)
4 shifting loop
1 attempt (loop with array[changing thing] = array[other changing thing]
1 correct loop bounds (size - index) times
1 correct assignment OR correct order
1 correct assignment AND correct order
for (int i = size - 1; i >= index; i--)
elementData[i + n] = elementData[i];
for (int i = 0; i < size - index; i++)
elementData[size + n - i - 1] = elementData[size - i - 1];
for (int i = size + n - 1; i >= index + n; i--)
elementData[i] = elementData[i - n];
* values reset are [size + n - 1] through [n + index]
* values copied from are [size - 1] through [index]
* delta is n
2 inserting loop
1 attempt (loop setting array[changing thing] = value)
1 correct
for (int i = 0; i < n; i++)
elementData[i + index] = value;
for (int i = index; i < index + n; i++)
elementData[i] = value;
Notes: solutions that are not O(n) should go to question leader
Problem #6
solution
public static void alternatingReverse(Stack<Integer> s) {
if (s.size() % 2 != 0) {
throw new IllegalArgumentException();
}
Queue<Integer> q = new LinkedList<Integer>();
int oldSize = s.size();
while (!s.isEmpty()) {
q.add(s.pop());
}
for (int i = 0; i < oldSize / 2; i++) {
s.push(q.remove());
q.add(q.remove());
}
while (!s.isEmpty()) {
q.add(q.remove());
q.add(s.pop());
}
while (!q.isEmpty()) {
s.push(q.remove());
}
}
alternative ways to write splitting loop:
// using i%2 to make different choices for even/odd values of i
for (int i = 0; i < oldSize; i++) {
if (i % 2 == 0) {
q.add(q.remove();
} else {
s.push(q.remove());
}
}
// using i+=2 to account for two values having been removed
for (int i = 0; i < oldSize; i += 2) {
s.push(q.remove());
q.add(q.remove());
}
// looks like a bug, but works because size is changing
for (int i = 0; i < q.size(); i++) {
s.push(q.remove());
q.add(q.remove());
}
1 header (non-void okay if there is a return that is consistent)
2 exception
1 reasonable attempt
1 correct
2 constructs temporary queue using generics correctly (-1 per error)
1 handles empty stack based on tests (can be loop tests)
4 initial s->q loop
2 reasonable attempt
2 correct
6 splitting/weaving loops (ignore OBOBs for these points)
1 reasonable attempt at splitting loop (alternates between 2 q.remove
operations sending values to either stack or queue)
1 reasonable attempt at weaving loop (alternates between q.remove and s.pop
operations sending values to queue)
1 reasonable attempt to iterate oldSize/2 times (or use i%2 or i+=2)
3 uses oldSize for one of the splitting/weaving loops or loop structure
doesn't need it (requires one of the two split/weave attempts)
1 attempt to store this (or equivalent)
2 correctly stores and uses this (or equivalent)
equivalent would be regular loop testing q.size with 2 q.remove calls
3 ends with a q->s loop
1 attempt
2 correct
6 actually works (no double jeopardy with initial/final loops and using
oldSize, but -1 if there is an OBOB up to -2 for OBOBs); partial credit based
on this example:
bottom [400, 11, 300, 12, 200, 13, 100, 14] top
6 [100, 11, 200, 12, 300, 13, 400, 14] correct
4 [14, 400, 13, 300, 12, 200, 11, 100] reversed, switch 2 split lines
4 [11, 100, 12, 200, 13, 300, 14, 400] switch 2 lines in weaving loop
2 [400, 14, 300, 13, 200, 12, 100, 11] switch 2 lines in both loops
Notes:
-3 from the 6 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()); }
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