<![CDATA[
Problem #1
solution
1. Method Call Output Produced
------------------------------------------------
mystery(5); *
mystery(15); **
mystery(304); *--
mystery(9247); *--*
mystery(43269); -*--*
reverse strings was 9/15 (3 cases correct, 2 wrong)
common wrong answer */*/*/*/- (answer if code was if/else if/else): 6
Problem #2
solution
public String substring(String s, int i, int j) {
if (i < 0 || i > j || j > s.length())
throw new IllegalArgumentException();
else if (i == j)
return "";
else
return s.charAt(i) + substring(s, i + 1, j);
}
2 header (-1 per error)
3 exception
1 attempt (at least one case)
1 at least 2 cases right
1 all correct
4 start==end base case
1 attempt to test start==end
1 correct test
2 returns "" in this case
note: if their only base case is a 1-char string, then they can get up to
2 points (1 point for attempt, 1 point for correct)
if they have an EXTRA base case for 1-char string, grade it below
6 recursive case
1 attempt (combination of s.charAt and recursive call on substring--can
also get this if no charAt but recursive call involves both
start and stop with either or both of start+1 or stop-1)
1 basic idea: s.charAt(start) + recurse on (start+1) or
recurse on (stop-1) + s.charAt(stop-1)
recurse on (stop-1) + s.charAt(stop)
2 recursive call includes the other index
2 all correct (-1 if minor error like an extra base case that doesn't work)
syntax errors (off the top assuming their code accumulated points, max -3):
-1 if s.charAt is treated as a String
-1 for charAt without "s." or as static charAt(s, i)
-1 for missing String parameter
note: if they use a while with recursion, change while to if with -3 off top
if they use illegal constructs (other String methods, loop), give to
question leader to grade
Problem #3
solution
public boolean isConsecutive() {
if (front == null) {
return true;
} else {
ListNode current = front;
while (current.next != null) {
if (current.next.data != current.data + 1) {
return false;
}
current = current.next;
}
return true;
}
}
1 header
1 works (returns true) for empty list (requires if or loop test)
1 works (returns true) for 1-element list (requires if or loop test)
5 loop
1 attempt ("current" variable initialized to front, goes to end of list)
1 moves current (current = current.next)
3 stops one early
3 test for consecutive (requires loop attempt)
2 attempt to test difference of 1 between current.data, current.next.data
1 correct test
4 correctly returns true or false (requires loop AND test attempt)
2 returns false if test fails (lose this if they return early)
2 returns true after loop
Problem #5
solution
public void reverseByN(Queue<Integer> q, int n) {
Stack<Integer> s = new ArrayStack<Integer>();
int times = q.size() / n;
int extra = q.size() % n;
for (int i = 0; i < times; i++) {
for (int j = 0; j < n; j++)
s.push(q.dequeue());
while (!s.isEmpty())
q.enqueue(s.pop());
}
for (int i = 0; i < extra; i++)
s.push(q.dequeue());
while (!s.isEmpty())
q.enqueue(s.pop());
}
2 header (-1 per error, non-void return okay if consistent)
2 construct stack (-1 per error)
15 works when q.size() is a multiple of n
5 outer loop related to q.size()
2 attempt (some kind of loop related to q.size()
3 correct (executes q.size()/n times, -1 if obob)
5 inner loop to move n values Q -> S (-1 if obob)
5 then inner loop to move n values S -> Q (-1 if obob)
6 works when q.size() is not a multiple of n
2 attempt to handle this case
4 correctly handles this case
Problem #6
solution
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;
}
1 header
1 construct a new ArrayIntList
3 loop over pairs
1 attempt (some kind of for loop involving size or elementData.length)
2 iterates exactly (size/2) times (-1 if obob)
3 expanding each pair
1 attempt (inner loop whose bounds are related to elementData[i] (or i+1)
2 correct (-1 if obob or they switch the pair)
1 correctly sets result.size (no double jeopardy with other mistakes, but
requires loop AND expand attempt)
1 returns their result
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011