<![CDATA[
Problem #1
solution
Method Call Output Produced
------------------------------------------------
mystery(7); .7
mystery(246); 642.
mystery(195); .195
mystery(1234); 42.13
mystery(29548); 842.95
3 points for each
lose 1 point for a character of the output that is missing or an extra
character of output or a pair of transposed characters
-0 for quotes around output
Problem #2
solution
public void printPattern(int n) {
if (n < 0) {
throw new IllegalArgumentException();
} else if (n > 0) {
if (n == 1) {
System.out.print(".");
} else if (n / 2 % 2 == 0) {
System.out.print("[");
printPattern(n - 2);
System.out.print("]");
} else {
System.out.print("(");
printPattern(n - 2);
System.out.print(")");
}
}
}
1 header (non-void return is okay if consistent with a return, static is okay)
1 exception: correct test for n < 0 and correct exception being thrown
3 base cases
1 code to print nothing when n is 0 (requires testing structure)
2 code to print a dot when n is 1
4 basic idea: print ()'s or []'s around a recursive call
2 reasonable attempt: print either ()'s or []'s surrounding a recursive
call (print, recurse, print)
2 correct for either ()'s or []'s (requires a call on n-2)
2 have cases for both (looking for parallel code that does print/recurse/print)
1 parallel code for other
1 code matches first (this means, for example, that if they make a call on
n-1 for both, then they get this point)
3 have code for both ()'s and []'s that uses a correct test to distinguish
1 reasonable attempt involving n%4 or n/2 or n%2
2 correct test (examples below)
n / 2 % 2 == 0
n % 4 / 2 == 0
n % 4 == 0 || n % 4 == 1
n % 4 != 2 && n % 4 != 3
n % 4 < 2
1 pieces fit together with no extraneous code and no minor formatting errors
notes:
* Notice that minor formatting issues like print versus println are included in
the final point.
* All loop, extra data structure, string concatenation solutions go to question
leader.
Problem #3
Statement Output
------------------------------------------------------------
var1.method2(); compiler error
var2.method2(); Can 2/Can 3
var3.method2(); Can 2/Lamp 3
var4.method2(); Can 2/Clock 3
var5.method2(); compiler error
var6.method2(); Can 2/Clock 3
var1.method3(); compiler error
var2.method3(); Can 3
var3.method3(); Lamp 3
var4.method3(); Clock 3
var5.method3(); compiler error
var6.method3(); Clock 3
((Lamp)var6).method1(); runtime error
((Can)var1).method1(); compiler error
((Can)var1).method2(); Can 2/Bear 3/Can 3
((Bear)var1).method3(); Bear 3/Can 3
((Bear)var6).method1(); Bear 1
((Clock)var1).method1(); runtime error
((Clock)var4).method2(); Can 2/Clock 3
((Bear)var3).method1(); runtime error
1 pt each
-1 if no slashes anywhere
-0 if they put quotes around answers
Problem #4
before after code
-----------------------+-----------------------+-------------------------------
p->[1]->[2] | p->[1]->[2]->[3] | p.next.next = q;
| | q = null;
q->[3] | q |
-----------------------+-----------------------+-------------------------------
p->[1]->[2]->[3] | p->[1]->[3] | q = p.next;
| | p.next = p.next.next;
q | q->[2] | q.next = null;
-----------------------+-----------------------+-------------------------------
p->[1]->[2] | p->[2]->[3] | p.next.next = q;
| | ListNode temp = p.next;
q->[3]->[4] | q->[1]->[4] | p.next = q.next;
| | q = p;
| | p = temp;
| | p.next.next = null;
-----------------------+-----------------------+-------------------------------
p->[1]->[2]->[3] | p->[3]->[1] | ListNode temp = p.next.next;
| | temp.next = p;
| | q.next.next = p.next;
q->[4]->[5] | q->[5]->[2]->[4] | p.next = null;
| | p = temp;
| | q.next.next.next = q;
| | q = q.next;
| | q.next.next.next = null;
-----------------------+-----------------------+-------------------------------
2 problem 1
1 attempt: change 2 of (q, 1 ~.next)
1 correct
3 problem 2
1 attempt: change 2 of (q, 2 ~.next)
2 correct
4 problem 3
1 attempt: change 3 of (p, q, 3 ~.next)
1 better attempt: change all 5 of (p, q, 3 ~.next)
2 correct
6 problem 4
1 attempt: change 4 of (p, q, 5 ~.next)
1 better attempt: change 6 of (p, q, 5 ~.next)
4 correct
Notes
correctness is generally atomic except:
-1 per "setting to null" error if otherwise correct
-1 per exception thrown if otherwise correct
-1 if adding or subtracting a single ".next" somewhere makes it work
can lose up to 2 syntax points if they get correctness points, examples:
-1 not declaring temp variable to be of type ListNode (categorical)
-1 saying p.next() instead of p.next (categorical)
-1 per occurrence (max of 2) for "p.data" instead of "p" or equivalent
if they construct new list nodes:
-1 if they don't use them
lose all correctness for any subproblem that relies on the new nodes
if they use more than 2 temp variables:
-2 from correctness per subproblem
Problem #5
solution
public static void mirror2(Stack<Integer> s) {
Queue<Integer> q = new LinkedList<Integer>();
while (!s.isEmpty())
q.add(s.pop());
while (!q.isEmpty())
s.push(q.remove());
while (!s.isEmpty())
q.add(s.pop());
for (int i = 0; i < q.size(); i++) {
int n = q.remove();
s.push(n);
q.add(n);
}
while (!s.isEmpty())
q.add(s.pop());
while (!q.isEmpty())
s.push(q.remove());
}
2 header (-1 per error, non-void return okay if consistent, static is okay)
2 constructs temporary queue using generics correctly (-1 per error)
4 loops that go s->q, q->s
2 reasonable attempt
2 correct ignoring bounds issues (-1 if just one mistake like saying
s.remove instead of s.pop)
4 fixed the problem of reverse order with extra s->q, q->s loops
2 reasonable attempt
2 correct ignoring bounds issues (-1 if just one mistake like saying
s.remove instead of s.pop)
4 expanding loop: some loop doubles the number of values
2 reasonable attempt: removing operation paired with 2 adding operations
2 approach can work, for example:
go through q, doing both an enqueue and a push
go through stack, enqueueing each value twice
go through q, adding each value twice
NOT go through stack, doing both an enqueue and a push
note: loop errors like using size() vs oldSize are okay for these points
9 Actually works. Simulate for:
bottom [1, 2, 3] top
score as follows:
9 [1, 2, 3, 3, 2, 1]--correct answer
6 [3, 2, 1, 1, 2, 3]--reverse but swapped
3 [1, 2, 3, 1, 2, 3]--copy but no reverse
3 [3, 2, 1, 3, 2, 1]--copy but both reversed
note: can fix one error for a cost of -2 if approved by the question leader
using size() vs oldSize in a for loop
Give to question leader all solutions that involve:
peek, foreach loop, iterator, or other illegal stack/queue operations
constructing a temporary structure other than a queue (e.g., a 2nd stack)
nonworking solution that gets 25 points
Problem #6
solutions
public void removeRange(int start, int stop) {
if (start < 0 || stop > size || start > stop) {
throw new IllegalArgumentException();
}
int delta = stop - start;
for (int i = stop; i < size; i++) {
elementData[i - delta] = elementData[i];
}
size -= delta;
}
public void removeRange(int start, int stop) {
if (stop - start < 0 || stop > size || start < 0) {
throw new IllegalArgumentException();
}
int newSize = start;
for (int i = stop; i < size; i++) {
elementData[newSize] = elementData[i];
newSize++;
}
size = newSize;
}
1 header (non-void okay if there is a return that is consistent)
2 exception
1 reasonable attempt
1 correct (all three cases, okay if extra case start==size)
5 loop
1 for loop using size or elementData.length
1 correct # of iterations: size - stop
3 correct copy
1 attempt: elementData[i] = elementData[j]
2 correct: alignment and delta
* alignment--first i is correct: elementData[start]
* delta is correct: j - i = stop - start
2 update size
1 attempt
1 correct (assuming # of iterations was correct)
Correct copying:
for (int i = 0; i < size - stop; i++)
elementData[i + start] = elementData[i + stop];
for (int i = stop; i < size; i++)
elementData[i - stop + start] = elementData[i];
int delta = stop - start;
for (int i = stop; i < size; i++)
elementData[i - delta] = elementData[i];
Notes: -3 if they use an extra structure (array, ArrayList, etc)
Problem #6
solutions
public void removeRange(int start, int stop) {
if (start < 0 || stop > size || start > stop) {
throw new IllegalArgumentException();
}
int delta = stop - start;
for (int i = stop; i < size; i++) {
elementData[i - delta] = elementData[i];
}
size -= delta;
}
public void removeRange(int start, int stop) {
if (stop - start < 0 || stop > size || start < 0) {
throw new IllegalArgumentException();
}
int newSize = start;
for (int i = stop; i < size; i++) {
elementData[newSize] = elementData[i];
newSize++;
}
size = newSize;
}
1 header (non-void okay if there is a return that is consistent)
2 exception
1 reasonable attempt
1 correct (all three cases, okay if extra case start==size)
5 loop
1 for loop using size or elementData.length
1 correct # of iterations: size - stop
3 correct copy
1 attempt: elementData[i] = elementData[j]
2 correct: alignment and delta
* alignment--first one correct: elementData[start]
* delta is correct: stop - start
2 update size
1 attempt
1 correct (assuming # of iterations was correct)
Correct copying:
for (int i = 0; i < size - stop; i++)
elementData[i + start] = elementData[i + stop];
for (int i = stop; i < size; i++)
elementData[i - stop + start] = elementData[i];
int delta = stop - start;
for (int i = stop; i < size; i++)
elementData[i - delta] = elementData[i];
Notes: -3 if they use an extra structure (array, ArrayList, etc)
-1 if they use elementData.length instead of size
4 setting middle range (sublist part)
int delta = stop - start;
for (int i = stop; i < size; i++)
elementData[i - delta] = elementData[i];
for (int i = stop; i < size; i++) {
elementData[i - stop + start] = elementData[i];
for (int i = from; i < to; i++)
result[i + list.length - to - from] = list[i];
1 reasonable attempt:
* separate loop or if/else branch for this case
* assignment and/or index range indicates that they are solving this
part of the problem (must be copying from list to result)
1 correct number of iterations: to - from
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011