<![CDATA[
Problem #1
solution
1. Method Call Output Produced
------------------------------------------------
mystery(1); 1
mystery(3); 3, 1, 3
mystery(4); 4, 2, 1, 2, 4
mystery(6); 6, 3, 1, 3, 6
mystery(12); 12, 6, 3, 1, 3, 6, 12
3 points for each row.
First row is all-or-nothing. For others, they lose 1 point for each incorrect
number or missing number or comma error, although they can't go below 0 for any
single row. Don't take off more than two points total for the entire problem
for comma errors (even if they have no commas at all).
Problem #2
solution
public String replace(String s, char target, char replacement) {
if (s.length() == 0)
return "";
else {
String rest = replace(s.substring(1), target, replacement);
if (s.charAt(0) == target)
return replacement + rest;
else
return s.charAt(0) + rest;
}
}
public static String replace(String s, char target, char replacement) {
if (s.length() == 0)
return s;
else {
char last = s.charAt(s.length() - 1);
String rest = replace(s.substring(0, s.length() - 1), target,
replacement);
if (last == target)
last = replacement;
return rest + last;
}
}
public static String replace(String s, char target, char replacement) {
String result = "";
if (s.length() > 0) {
if (s.charAt(0) == target)
result += replacement;
else
result += s.charAt(0);
result += replace(s.substring(1), target, replacement);
}
return result;
}
2 header (-1 per error)
3 empty string base
1 attempt (they tested this case)
2 correct (return original string or an empty string in this case)
4 recurse on substring(1) or substring(0, length-1);
-2 if char parameters are missing or one OBOB
2 testing if first/last char is target
-------------------------------------------------------------------------------
4 constructing/returning correct result
if it's correct, give them 4 points
if not, give it to the question leader if it has these properties:
recursive call on substring
test for first/last char is target
concatenating target char with result of recursion
else give it 0
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 minGap() {
if (front == null || front.next == null) {
return 0;
} else {
int min = front.next.data - front.data;
ListNode current = front.next;
while (current.next != null) {
int gap = current.next.data - current.data;
if (gap < min) {
min = gap;
}
current = current.next;
}
return min;
}
}
1 header
3 empty and 1-element cases are correct
1 tests for one and returns 0
2 tests for both and returns 0 for both
3 properly initializes min to first gap
5 loop to examine pairs of list elements
1 attempt ("current" variable initialized to front, test for end of list)
2 moves current (current = current.next)
2 correctly visits each adjacent pair and nothing more (generally means
stopping one early with current.next or inchwork prev/next)
2 updating min
1 computes next gap properly
1 resets min if next gap is smaller
1 returns min
note: if they switch the order of values, take -1 off the top
Problem #5
solution
public boolean equals(Stack<Integer> s1, Stack<Integer> s2) {
if (s1.size() != s2.size()) {
return false;
} else {
Stack<Integer> s3 = new ArrayStack<Integer>();
boolean same = true;
while (same && !s1.isEmpty()) {
int num1 = s1.pop();
int num2 = s2.pop();
if (num1 != num2)
same = false;
s3.push(num1);
s3.push(num2);
}
same = same && s1.isEmpty();
while (!s3.isEmpty()) {
s2.push(s3.pop());
s1.push(s3.pop());
}
return same;
}
}
2 header (-1 per error)
2 constructs temporary stack using generics correctly (-1 per error)
6 main comparison loop--a loop that removes a value from each stack, compares
them, and pushes the two values onto the temporary stack
1 basic structure: a loop that removes one value from each stack
2 comparison: compares the two values, either terminating the loop if they
aren't equal or remembering that a difference was seen (requires basic
structure)
2 pushes the two values onto the temporary stack (requires basic structure)
1 bounds: stops when one of the stacks becomes empty or when a difference
is seen (can also compare against size with an i++ loop)--here it's okay
for them to loop even after a difference is seen
4 efficiency
1 checks sizes before loop, returning false if not equal
3 stops loop when a difference is seen
8 restoring the stacks
4 basic idea: taking two values from the temporary stack and putting one
each back into the other stacks--can get this even if they return early
4 correct including order (reverse of the order they were added to the
stack)--can't get this if they return early
3 returning a correct answer
2 returns false in all appropriate cases (sizes differ, difference seen,
stacks aren't empty after comparison loop)
1 returns true whenever it doesn't return false
Problem #6
solution
public void removeFront(int n) {
if (n < 0 || n > size)
throw new IllegalArgumentException();
for (int i = n; i < size; i++)
elementData[i - n] = elementData[i];
size -= n;
}
1 header (non-void okay if there is a return that is consistent)
2 exception
1 reasonable attempt (testing negative or bigger than size)
1 correct (testing both)
5 loop
1 attempt (loop with array[something] = array[something else]
2 correct loop bounds (size - n times, -1 if OBOB)
2 correct assignment (-1 if OBOB)
2 reset size
1 attempt (subtract something from size)
1 correct (subtract n from 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