<![CDATA[
Problem #2
solution:
public String repeat(String s, int n) {
if (n < 0)
throw new IllegalArgumentException();
else if (n == 0)
return "";
else if (n == 1)
return s;
else if (n % 2 == 0) {
String temp = repeat(s, n / 2);
return temp + temp;
// alternative without temp: return repeat(s + s, n / 2);
} else
return s + repeat(s, n - 1);
}
9 correctness
1 header
2 exception
1 attempt
1 correct
3 base case of 0
1 attempt (some base case)
2 correct (-1 if base case is 1 and is correct)
3 general (odd) recursive case
1 attempt (test/else with recursive call involving "s+<call>")
2 correct
6 efficiency (requires recursive case attempt)
6 even case
2 idea (test for even case)
2 recursive call on n/2
2 correct (store in temp or pass s+s)
if no even case, they can get:
2 base case for both 0 and 1
1 attempt
1 correct
Problem #3
solution:
public void removeLast(int n) {
if (front != null) {
ListNode current = front;
ListNode spot = null;
while (current.next != null) {
if (current.next.data == n)
spot = current;
current = current.next;
}
if (spot != null)
spot.next = spot.next.next;
else if (front.data == n)
front = front.next;
}
}
1 header
1 works (does nothing) for empty list
1 works (does nothing) for 1-element list with front.data != n
2 loop over list elements for list size > 1 (current = front; while...)
1 attempt
1 correct
7 removes last occurrence when it's not the front of the list
1 test attempt (something.data == n)
1 remove attempt (something.next = something.next.next)
2 correctly removes exactly one occurrence of n
3 correctly removes last occurrence of n (-2 if O(n^2))
3 handles front of list
1 attempt (requires some test that there are no other occurrences)
2 correct (-1 if close--e.g., works for all but 1-element list)
Problem #5
solution:
public void interleave(Queue<Integer> q) {
if (q.size() % 2 != 0)
throw new IllegalArgumentException();
Stack<Integer> s = new ArrayStack<Integer>();
int halfSize = q.size() / 2;
for (int i = 0; i < halfSize; i++)
s.push(q.dequeue());
while (!s.isEmpty())
q.enqueue(s.pop());
for (int i = 0; i < halfSize; i++)
q.enqueue(q.dequeue());
for (int i = 0; i < halfSize; i++)
s.push(q.dequeue());
while (!s.isEmpty()) {
q.enqueue(s.pop());
q.enqueue(q.dequeue());
}
}
2 header (-1 per error, non-void return okay if consistent)
2 exception
1 attempt
1 correct
2 construct Stack (-1 per error)
6 some version of:
1/2 Q -> S
(Q/S or S/Q) -> Q (-3 if it's instead S -> Q)
3 attempt to deal with forwards/reverse (separate from loops above):
Q or 1/2 Q -> S
S -> Q
10 Otherwise correct: Simulate for
front [1, 2, 3, 4, 5, 6] back
and score as follows:
10 [1, 4, 2, 5, 3, 6]--correct answer
7 [6, 3, 5, 2, 4, 1]--completely backwards
7 [4, 1, 5, 2, 6, 3]--sublists exchanged
5 [3, 4, 2, 5, 1, 6]--one sublist backwards
5 [1, 6, 2, 5, 3, 4]--one sublist backwards
5 [3, 6, 2, 5, 1, 4]--completely backwards and sublists exchanged
2 [4, 3, 5, 2, 6, 1]--one sublist backwards and sublists exchanged
2 [6, 1, 5, 2, 4, 3]--one sublist backwards and sublists exchanged
-5 if loops are 1/4 because of for loop with size bug (or similar error)
Known solutions:
1/2 Q -> S Q -> S 1/2 Q -> Q 1/2 Q -> S 1/2 Q -> S
S -> Q 1/2 S -> Q 1/2 Q -> S S -> Q S -> Q
1/2 Q -> Q (Q/S) -> Q S -> Q 1/2 Q -> S 1/2 Q -> S
1/2 Q -> S Q -> S 1/2 Q -> Q S -> Q (S/Q) -> Q
(S/Q) -> Q S -> Q 1/2 Q -> S 1/2 Q -> S Q -> S
(Q/S) -> Q S -> Q S -> Q
1/2 Q -> S
(Q/S) -> Q
-------------------------------------------------------------------------------
Q -> S 1/2 Q -> Q 1/2 Q -> S 1/2 Q -> S
S -> Q 1/2 Q -> S 1/2 S -> Q S -> Q
Q -> S 1/2 S -> Q 1/2 Q -> S 1/2 Q -> S
1/2 S -> Q 1/2 Q -> S 1/2 S -> Q (S/Q) -> Q
Q/S -> Q (Q/S) -> Q 1/2 Q -> S Q -> S
1/2 S -> Q S -> Q
1/2 Q -> S
(Q/S) -> Q
Problem #6
solution:
public void removeOddPositions() {
size = (size + 1) / 2;
for (int i = 0; i < size; i++)
elementData[i] = elementData[2 * i];
}
1 header
6 loop
1 basic idea:
for (...)
elementData[-] = elementData[-]
2 loop executes size/2 times for even size (-1 if OBOB)
1 loop executes size/2+1 times for odd size
2 correct assignment (-1 if OBOB)
3 reset size
1 attempt
2 correct (-1 if correct for only one of even/odd)
If temp array, -2 off top
Canonical O(n^2) solution
public void removeOddPositions() {
for (int i = 1; i < size; i++) {
for (int j = i; j < size - 1; j++)
elementData[j] = elementData[j + 1];
size--;
}
}
1 header
3 loop
1 basic idea:
for (i < size)
for (j going i to size)
elementData[j] = elementData[j + 1]
1 outer loop bounds/increment
1 inner loop bounds
1 reset size
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011