<![CDATA[
Problem #2
solution
public int digitMatch(int x, int y) {
if (x < 0 || y < 0)
throw new IllegalArgumentException();
else if (x < 10 || y < 10) {
if (x % 10 == y % 10)
return 1;
else
return 0;
} else if (x % 10 == y % 10)
return 1 + digitMatch(x / 10, y / 10);
else
return digitMatch(x / 10, y / 10);
}
1 header
2 exception
1 attempt (some kind of test for negative)
1 correct
5 base case
1 test attempt (some kind of test for 1-digit number)
1 test correct (tests that either x or y is 1-digit)
3 correctly evaluates final digits in this case
1 compares x % 10 and y % 10 in this case
1 returns 1 if equal (requires reasonable comparison)
1 returns 0 if unequal (requires reasonable comparison)
7 recursive case
2 correct recursive call digitMatch(x / 10, y / 10) (-1 if sometimes
correct and sometimes not correct)
5 correctly evaluates final digits in this case (can get points below even
if recursive call is incorrect)
1 compares x % 10 and y % 10 in this case
2 returns 1 + recursive call if equal (requires reasonable comparison)
2 returns recursive call if unequal (requires reasonable comparison)
Problem #3
solution:
public boolean isSortedByN(int n) {
if (n <= 0)
throw new IllegalArgumentException();
ListNode current1 = front;
ListNode current2 = front;
while (current2 != null && n > 0) {
current2 = current2.next;
n--;
}
while (current2 != null) {
if (current1.data > current2.data)
return false;
current1 = current1.next;
current2 = current2.next;
}
return true;
}
1 header
2 exception
1 attempt (some kind of test for zero or negative)
1 correct
1 works (returns true) for empty list (requires if or loop test)
1 first "current1" variable initialized to front
4 second "current2" variable
1 exists
1 loop n times to move it forward n relative to current1
2 correctly positions (requires correct null test)
2 returning true or false
1 if statement returning false if current1.data > current2.data
1 return true after a loop
4 actually works
Problem #5
solution:
public void compressDuplicates(Stack<Integer> s) {
Queue<Integer> q = new LinkedQueue<Integer>();
while (!s.isEmpty())
q.enqueue(s.pop());
while (!q.isEmpty())
s.push(q.dequeue());
while (!s.isEmpty())
q.enqueue(s.pop());
if (!q.isEmpty()) {
int last = q.dequeue();
int count = 1;
while (!q.isEmpty()) {
int next = q.dequeue();
if (next == last)
count++;
else {
s.push(count);
s.push(last);
count = 1;
last = next;
}
}
s.push(count);
s.push(last);
}
}
2 header (-1 per error, non-void return okay if consistent)
1 test to ensure that it works (does nothing) for empty stack
2 construct queue (-1 per error)
4 Basic attempt (generous)
S -> Q
Q -> S
one of these loops is counting duplicates
3 Basic idea (not quite so generous)
compare adjacent elements for equality, incrementing a counter
put the count and the number back into the structure
3 attempt to deal with forwards/reverse (separate from loops above):
S -> Q
Q -> S
10 Otherwise correct: Simulate for:
bottom [10, 10, 10, 20, 20, 20, 30] top
and score as follows:
10 [3, 10, 3, 20, 1, 30]--correct answer
7 [1, 30, 3, 20, 3, 10]--pairs in reverse order
7 [10, 3, 20, 3, 30, 1]--swapped pairs
5 [30, 1, 20, 3, 10, 3]--swapped pairs and in reverse order
If all counts are off by 1 but otherwise match above, extra -3
Classic for loop size bug (goes half way) is -2 (imagine rewriting code)
If you see some bug that isn't caught by this test case, show to leader
Problem #5 Alternate correct solution:
public static void compressDuplicates(Stack<Integer> s) {
Queue<Integer> q = new LinkedQueue<Integer>();
if (!s.isEmpty()) {
int last = s.pop();
int count = 1;
while (!s.isEmpty()) {
int next = s.pop();
if (next == last)
count++;
else {
q.enqueue(last);
q.enqueue(count);
count = 1;
last = next;
}
}
q.enqueue(last);
q.enqueue(count);
while (!q.isEmpty())
s.push(q.dequeue());
while (!s.isEmpty())
q.enqueue(s.pop());
while (!q.isEmpty())
s.push(q.dequeue());
}
}
}
Problem #6
solution:
public boolean isConsecutive() {
for (int i = 0; i < size - 1; i++)
if (elementData[i + 1] != elementData[i] + 1)
return false;
return true;
}
1 header
7 loop over list
1 loop attempt using size
1 loop goes "size - 1" times or otherwise avoids "out of bounds"
1 attempt to compare adjacent elements of elementData
2 correctly tests whether adjacent elements are not consecutive
2 returns false when not consecutive (lose these if they return early)
2 returns true if all consecutive
-1 for list vs elementData, -1 for elementData.length vs size (or similar)
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011