<![CDATA[
Problem #1
solution
1. Method Call Output Produced
------------------------------------------------
mystery(3); 3
mystery(42); 242
mystery(293); 39293
mystery(402); 20402
mystery(2468); 8642468
3 points for each row.
First row is all-or-nothing. For others, they lose 1 point for each incorrect
digit or missing digit, although they can't go below 0 for any single row.
-1 off the top if they introduce spaces
-2 off the top if they introduce commas
Problem #2
solution
public void writeNumbers(int n) {
if (n < 1)
throw new IllegalArgumentException();
else if (n == 1)
System.out.print(1);
else if (n % 2 == 1) {
System.out.print(n + ", ");
writeNumbers(n - 1);
} else {
writeNumbers(n - 1);
System.out.print(", " + n);
}
}
1 header
2 exception
1 attempt
1 correct
3 base case of n == 1
2 attempt (they tested this case)
1 correct (prints 1)
5 recursive case for even values of n
2 attempt: test this case, recurse on n-1 or n-2, print n
1 works for 2 (or has special base case for 2)
2 correct (-1 if minor error like missing comma)
4 recursive case for odd values of n
2 attempt: test this case, recurse on n-1 or n-2, print n
2 correct (-1 if minor error or missing comma)
General Notes: -3 perfectly backwards
Problem #3
solution
public boolean increasingTriples() {
ListNode current = front;
while (current != null && current.next != null &&
current.next.next != null) {
if (current.data >= current.next.data ||
current.next.data >= current.next.next.data)
return false;
current = current.next.next.next;
}
if (current!= null && current.next != null &&
current.data >= current.next.data)
return false;
return true;
}
1 header
3 works for lists of length < 3
1 returns true for empty list based on test
1 returns true for 1-element list based on test
1 returns result of comparing first two values for 2-element list
8 loop that checks triples for lists whose length is a multiple of 3
1 attempt ("current" variable initialized to front, test for end of list)
1 returns false when current.data >= current.next.data
1 returns false when current.next.data >= current.next.next.data
2 correct loop test (-1 if OBOB)
3 current = current.next.next.next or equivalent (-1 if OBOB)
2 correctly handles extras for lists whose length is not a multiple of 3
1 attempt
1 correct
1 return true at the end or equivalent
General notes: solutions that use other methods like size() or that destroy the
list should go to the question leader
Problem #4
1 pt each
-1 if no slashes anywhere
Problem #5
solution
public boolean isConsecutive(Stack<Integer> s) {
if (s.size() <= 1)
return true;
else {
Queue<Integer> q = new LinkedList<Integer>();
int prev = s.pop();
q.add(prev);
boolean ok = true;
while (!s.isEmpty()) {
int next = s.pop();
if (prev - next != 1)
ok = false;
q.add(next);
prev = next;
}
while (!q.isEmpty())
s.push(q.remove());
while (!s.isEmpty())
q.add(s.pop());
while (!q.isEmpty())
s.push(q.remove());
return ok;
}
}
2 header (-1 per error)
2 constructs temporary queue using generics correctly (-1 per error)
2 special test for size < 2 or equivalent
4 basic idea: S -> Q, Q -> S, comparing adjacent values
-------------------------------------------------------------------------------
no more points if student doesn't have basic idea
4 four loops to get correct order: S -> Q, Q -> S, S-> Q, Q -> S
2 attempt
2 correct (can get this even if they return early)
6 compare adjacent values correctly (all pairs)
2 attempt: testing for difference of 1
4 store old value or otherwise generate all pairs (vs comparing sequential
pairs)
4 restores stack in all cases (normally lose this if they return early)
2 attempt (flag or code to restore before returning)
2 correct
1 always returns appropriate values (flag or true/false)
Problem #6
solution
public void insertAt(int index, int n, int value) {
if (index < 0 || index > size || n < 0)
throw new IllegalArgumentException();
for (int i = size - 1; i >= index; i--)
elementData[i + n] = elementData[i];
for (int i = 0; i < n; i++)
elementData[i + index] = value;
size += n;
}
1 header (non-void okay if there is a return that is consistent)
2 exception
1 half right (half of (3 tests + exception))
1 all correct
3 shifting loop
1 attempt (loop with array[changing thing] = array[other changing thing]
1 correct loop bounds (size - index) times
1 correct assignment and correct order
2 inserting loop
1 attempt (loop setting array[changing thing] = value)
1 correct
2 resetting size
1 attempt (subtract something from size)
1 correct (add n to size)
Notes: solutions that are not O(n) should go to question leader
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011