<![CDATA[
Problem #1
solution
1. Method Call Output Produced
------------------------------------------------
mystery(1); 1
mystery(3); 3, 10, 5, 16, 8, 4, 2, 1
mystery(4); 4, 2, 1
mystery(5); 5, 16, 8, 4, 2, 1
mystery(20); 20, 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 transposed pair.
-0 for quotes around output
-2 if no commas
Problem #2
solution
public String collapseSequences(String s, char ch) {
if (s.length() < 2) {
return s;
} else {
char first = s.charAt(0);
if (first == ch && first == s.charAt(1)) {
return collapseSequences(s.substring(1), ch);
} else {
return s.charAt(0) + collapseSequences(s.substring(1), ch);
}
}
}
2 header (-1 per error, okay if it's static)
6 generous (don't take off for syntax for these)
1 testing string length of 0 or 1 or testing for equality with empty string
1 testing whether the first or second character is the target character
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 first char with recursive call on substring(1)
1 separate recursive call on either substring(1) or substring(2) without
including first character
7 actually works (see note below about syntax)
1 returns empty string without throwing an exception for empty string
1 returns original string without throwing an exception for 1-char string
1 correctly tests first 2 characters equal AND that they match the target
1 works when first 2 characters are equal and sequence length <= 2 (can
exclude both characters on recursive call)
1 works when first 2 characters are equal for all sequences
2 works correctly when first 2 characters are not equal
syntax deductions (categorical, first mistake is free if there weren't
other syntax problems in their code)
-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
-1 for failing to include target character in 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
3. Statement Output
------------------------------------------------------------
var1.method1(); Soap 1/Dish 3/Soap 3
var2.method1(); Soap 1/Fork 3
var3.method1(); Soap 1/Bowl 3
var4.method1(); Soap 1/Fork 3
var5.method1(); Soap 1/Soap 3
var6.method1(); compiler error
var1.method2(); compiler error
var2.method2(); Fork 2
var3.method2(); compiler error
var1.method3(); Dish 3/Soap 3
var2.method3(); Fork 3
var3.method3(); Bowl 3
((Fork)var6).method1(); runtime error
((Dish)var3).method2(); compiler error
((Fork)var4).method2(); Fork 2
((Fork)var3).method2(); runtime error
((Bowl)var3).method2(); Bowl 2
((Fork)var1).method1(); runtime error
((Dish)var4).method3(); Fork 3
((Soap)var6).method3(); Dish 3/Soap 3
1 pt each
-1 if no slashes anywhere
-0 if they put quotes around answers
Problem #4
before after code
-----------------------+-----------------------+-------------------------------
p->[1]->[2]->[3] | p->[1]->[2] | q = p.next.next;
| | p.next.next = null;
q | q->[3] |
-----------------------+-----------------------+-------------------------------
p->[1]->[3] | p->[1]->[2]->[3] | q.next = p.next;
| | p.next = q;
q->[2] | q | q = null;
-----------------------+-----------------------+-------------------------------
p->[1]->[2] | p->[2]->[4] | p.next.next = q.next;
| | q.next = p;
q->[3]->[4] | q->[3]->[1] | p = p.next;
| | q.next.next = null;
-----------------------+-----------------------+-------------------------------
p->[1]->[2]->[3] | p->[2]->[1]->[4] | p.next.next.next = q.next;
| | ListNode temp = q;
q->[4]->[5] | q->[3]->[5] | q = p.next.next;
| | p.next.next = p;
| | p = p.next;
| | p.next.next = temp;
| | temp.next = null;
-----------------------+-----------------------+-------------------------------
2 problem 1
1 attempt: change 2 of (q, 1 ~.next)
1 correct
3 problem 2
1 attempt: change 2 of (q, 2 ~.next)
2 correct
4 problem 3
1 attempt: change 2 of (p, 3 ~.next)
1 better attempt: change all 4 of (p, 3 ~.next)
2 correct
6 problem 4
1 attempt: change 3 of (p, q, 4 ~.next)
1 better attempt: change 5 of (p, q, 4 ~.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
-1 saying p.next() instead of p.next
-1 per occurrence (max of 2) for "p.data" instead of "p" or equivalent
Problem #5
solution
public int parityMatches(Stack<Integer> s1, Stack<Integer> s2) {
if (s1.size() != s2.size()) {
throw new IllegalArgumentException();
}
Queue<Integer> q = new LinkedList<Integer>();
int count = 0;
while (!s1.isEmpty()) {
int num1 = s1.pop();
int num2 = s2.pop();
if (num1 % 2 == num2 % 2)
count++;
q.add(num1);
q.add(num2);
}
while (!q.isEmpty())
s1.push(q.remove());
while (!s1.isEmpty())
q.add(s1.pop());
while (!q.isEmpty()) {
s2.push(q.remove());
s1.push(q.remove());
}
return count;
}
2 header (-1 per error, okay if it's static)
2 exception
1 attempt
1 correct
2 constructs temporary queue using generics correctly (-1 per error)
1 returns 0 without throwing an exception for empty stacks
3 basic idea: removing values from the two stacks and moving them into queue
1 attempt
2 correct
5 counts number of corresponding values with matching parity
1 counter variable declared and initialized
1 test attempt
1 test correct
1 counter incremented if there is a match
1 counter returned at the end of the method
4 fixed the problem of reverse order with extra s->q, q->s loops
2 attempt
2 correct
6 restores stacks in all cases (normally lose this if they return early)
2 reasonable attempt
2 restores the stacks, but possibly switched
2 restores both stacks
Give to question leader all solutions that involve:
peak, 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
Problem #6
solutions
public void stutter() {
for (int i = size - 1; i >= 0; i--) {
elementData[2 * i + 1] = elementData[i];
elementData[2 * i] = elementData[i];
}
size *= 2;
}
public void stutter() {
size *= 2;
for (int i = size - 1; i >= 0; i--) {
elementData[i] = elementData[i / 2];
}
}
1 header (non-void okay if there is a return that is consistent)
3 loop that executes 2*size times
1 attempt (some kind of for loop involving size or elementData.length)
1 better attempt (size times or obob or off-by-2)
1 iterates exactly 2*size times
4 correctly assigns array elements
2 basic idea (assigning array[2i] to array[i] or array[i] to array[i/2])
2 works correctly (loop has to run backwards, pieces fit together)
2 resets size
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