<![CDATA[
Problem #1
solution
Method Call Output Produced
------------------------------------------------
mystery(2); 2+
mystery(5); 52+-
mystery(7); 731---
mystery(18); 8942++-+
mystery(21); 1052+-+-
1 point per column
Method Call +'s 1st other
----------------------------------------------------------
mystery(2); 2 +
mystery(5); 52 + -
mystery(7); 731 - --
mystery(18); 8942 + +-+
mystery(21); 1052 + -+-
-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) + undouble(s.substring(1));
}
}
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.method2() Box 2
var2.method2() Jar 2
var3.method2() Cup 2/Box 2
var4.method2() Jar 2
var5.method2() compiler error
var6.method2() Pill 2
var1.method3() Box 2/Box 3
var2.method3() compiler error
var3.method3() Cup 2/Box 2/Box 3
var4.method3() Jar 2/Box 3
((Cup)var1).method1() runtime error
((Jar)var2).method1() Jar 1
((Cup)var3).method1() Cup 1
((Cup)var4).method1() runtime error
((Jar)var4).method2() Jar 2
((Box)var5).method2() Box 2
((Pill)var5).method3() compiler error
((Jar)var2).method3() Jar 2/Box 3
((Cup)var3).method3() Cup 2/Box 2/Box 3
((Cup)var5).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]->[2] | p->[1]->[2]->[3] | p.next.next = q;
| | q = null;
q->[3] | q |
-----------------------+-----------------------+-------------------------------
p->[1] | p->[2]->[1] | ListNode temp = q;
| | q = q.next;
q->[2]->[3] | q->[3] | temp.next = p;
| | p = temp;
-----------------------+-----------------------+-------------------------------
p->[1]->[2] | p->[2]->[4] | p.next.next = q.next;
| | q.next = null;
q->[3]->[4] | q->[1]->[3] | ListNode temp = p;
| | p = p.next;
| | temp.next = q;
| | q = temp;
-----------------------+-----------------------+-------------------------------
p->[1] | p->[2]->[1]->[4] | p.next = q.next.next;
| | q.next.next = null;
q->[2]->[3]->[4]->[5] | q->[5]->[3] | ListNode temp = p;
| | p = q;
| | q = temp.next.next;
| | q.next = p.next;
| | p.next = temp;
| | temp.next.next = null;
2 problem 1
1 attempt: change 2 of (q, 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 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
solution
public void removeMax() {
if (size == 0) {
throw new IllegalStateException();
}
int max = 0;
for (int i = 1; i < size; i++) {
if (elementData[i] > elementData[max]) {
max = i;
}
}
for (int i = max; i < size - 1; i++) {
elementData[i] = elementData[i + 1];
}
size--;
}
1 header (non-void okay if there is a return that is consistent)
2 exception
1 reasonable attempt
1 correct (has to prevent ArrayIndexOutOfBoundsException)
4 loop to find index of max value
1 initialize max variable to first array element (could be max value)
1 reasonable attempt to loop over array, looking for the max (could be
max value)
2 correctly computes index of max value (-1 if close as in OBOB)
2 loop to remove max value (must be a second loop, can't be a call on remove)
1 reasonable attempt: must have at least two of:
* loop that starts at max index
* correct shifting code (elementData[i]=elementData[i + 1])
* correct bounds to shift until the end without going out of bounds
1 correct loop (lose this point if the shifting loop is inside the loop to
find the max)
1 decrements size exactly once
Notes: -3 if they use an extra structure (array, ArrayList, etc)
-1 if they use elementData.length instead of size
can get attempt but not correct points for using methods like get/set
-------------------------------------------------------------------------------
Problem #6
solutions
public static void makePalindrome(Stack<Integer> s) {
Queue<Integer> q = new LinkedList<Integer>();
while (!s.isEmpty()) {
q.add(s.pop());
}
for (int i = 0; i < q.size(); i++) {
int n = q.remove();
q.add(n);
s.push(n);
}
int oldSize = q.size();
for (int i = 0; i < oldSize; i++) {
int n1 = q.remove();
int n2 = s.pop();
if (n1 == n2) {
q.add(n1);
}
}
while (!q.isEmpty()) {
s.push(q.remove());
}
}
public static void makePalindrome(Stack<Integer> s) {
Queue<Integer> q = new LinkedList<Integer>();
int size = s.size();
while (!s.isEmpty()) {
q.add(s.pop());
}
for (int i = 0; i < size / 2; i++) {
s.push(q.remove());
}
int middle = 0;
if (size % 2 == 1) {
middle = q.remove();
}
while (!s.isEmpty()) {
int n1 = q.remove();
int n2 = s.pop();
if (n1 == n2) {
q.add(n1);
}
}
int newSize = q.size();
for (int i = 0; i < newSize; i++) {
int n = q.remove();
q.add(n);
s.push(n);
}
while (!s.isEmpty()) {
q.add(s.pop());
}
if (size % 2 == 1) {
q.add(middle);
}
for (int i = 0; i < newSize; i++) {
q.add(q.remove());
}
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)
2 initial s->q loop (ok if it transfers only half of the values)
1 reasonable attempt
1 correct
4 duplicating loop that contains:
int n = q.remove();
q.add(n);
s.push(n);
or loop that transfers just half from one structure to the other, as in:
int size = s.size();
for (int i = 0; i < size / 2; i++) {
s.push(q.remove());
}
5 loop that includes code to compare values looking for palindromic pairs:
int n1 = q.remove();
int n2 = s.pop();
if (n1 == n2) {
q.add(n1); // okay if this is done twice
}
mostly atomic, but -2 if they also add back to stack and -3 if they only add
to the stack; the following is equivalent:
int n = q.remove();
if (n == s.pop()) {
q.add(n);
}
2 ends with a q->s loop (ok if it transfers only half of the values)
1 attempt
1 correct
8 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--see below)
1 works for length 3 test case
1 works for length 4 test case
1 works for length 6 test case
1 works for length 7 test case
2 works for length 14 test case
2 works for length 15 test case
approved deductions for these 8 correctness points (only apply if it gives
them some points)
-2 if in their comparing loop they added the value back to the queue twice
-2 minor loop error (OBOB, oldSize vs size())
-3 major loop error (while-not-empty vs oldSize)
Notes:
-2 from the 8 "actually works" 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()); }
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 from "actually works" for using peek
Give to question leader all solutions that involve: peek, foreach loop,
iterator, other illegal stack/queue operations; extra structure
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011