<![CDATA[
Problem #1
solution
1. Method Call Value Returned
-----------------------------------------------
mystery(18, 0) 0
mystery(8, 18) 1
mystery(25, 21) 1
mystery(305, 315) 2
mystery(20734, 1724) 2
3 pts each
Problem #2
solution
public static boolean isPalindrome(String s) {
if (s.length() <= 1)
return true;
else
return s.charAt(0) == s.charAt(s.length() - 1) &&
isPalindrome(s.substring(1, s.length() - 1));
}
1 header
2 empty string base case
1 attempt (they test for this case)
1 correct (correct test, return true)--s.equals("") is okay
2 1-char base case
1 attempt (they test for this case)
1 correct (correct test, return true)
10 compare outer chars
1 attempt (they compare first and last chars)
2 correct test (-1 if obob or other minor error)
2 returns false if not equal
1 recursive call if they are equal
2 recursive call is s.substring(1, s.length() - 1), -1 if obob
2 they return result of recursive call
general notes: using extra structure (like String) or using a loop goes to
question leader; extra parameter solutions (index or start/stop)
go to question leader
Problem #3
solution
public int numUnique() {
if (front == null)
return 0;
else {
int count = 1;
ListNode current = front;
while (current.next != null) {
if (current.data != current.next.data)
count++;
current = current.next;
}
return count;
}
}
1 header
2 empty list case is correct
1 does not throw an exception for empty list
1 special case code to have empty return 0 while other cases return >= 1
4 loop to examine list elements
1 attempt ("current" variable initialized to front, test for end of list)
1 moves current (current = current.next)
2 stops one early
8 counting unique values
1 counter variable declared before loop
1 counter variable returned after loop
2 counter initialized properly (-1 if OBOB)
2 basic idea: seeing if current.data != current.next.data
2 increments counter for each unique value seen (requires basic idea)
Problem #5
solution
public int removeMax(Stack<Integer> s) {
if (s.isEmpty())
throw new IllegalArgumentException();
Queue<Integer> q = new LinkedQueue<Integer>();
int max = s.pop();
q.enqueue(max);
while (!s.isEmpty()) {
int next = s.pop();
if (next > max)
max = next;
q.enqueue(next);
}
while (!q.isEmpty()) {
int next = q.dequeue();
if (next != max)
s.push(next);
}
while (!s.isEmpty())
q.enqueue(s.pop());
while (!q.isEmpty())
s.push(q.dequeue());
return max;
}
2 header (-1 per error, non-void return okay if consistent)
2 exception (-1 per error)
2 construct queue (-1 per error)
3 First S -> Q, Q -> S (ignore if max code screws up sequence)
1 attempt
2 correct
2 Second S -> Q, Q -> S (ignore if max code screws up sequence)
1 attempt
1 correct
4 Initialize max
1 attempt (e.g., 0)
3 correct (some value from list, can't screw up order/contents)
4 computes max on some pass
1 attempt
3 correct (can't screw up order/contents)
4 removes max on some pass (can't screw up order/contents)
1 attempt
3 correct (must be separate pass, can't screw up order/contents)
2 returns max at the end
Problem #6
solution
public void collapse() {
for (int i = 0; i < size / 2; i++)
elementData[i] = elementData[2 * i] + elementData[2 * i + 1];
if (size % 2 == 0)
size = size / 2;
else {
elementData[size / 2] = elementData[size - 1];
size = size / 2 + 1;
}
}
1 header (non-void okay if there is a return that is consistent)
5 collapsing loop (even case)
1 attempt (loop that adds consecutive values)
2 loops size/2 times (-1 if obob)
2 copies sums into correct positions
1 attempt (i*2 and i*2+1 or i and j with i++ and j+=2 or equivalent)
1 correct
2 copies final value in odd case
1 attempt
1 correct
2 resets size
1 attempt (size / 2)
1 correct (odd & even)
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