<![CDATA[
Problem #1
solution
Method Call Output Produced
------------------------------------------------
mystery(9); =9
mystery(42); 24=
mystery(703); 30=7
mystery(5821); 12=58
mystery(83105); 013=85
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
solutions
public static int weave(int x, int y) {
if (x < 0 || y < 0) {
throw new IllegalArgumentException();
}
if (x == 0 && y == 0) {
return 0;
} else {
return 100 * weave(x / 10, y / 10) + 10 * (x % 10) + y % 10;
}
}
public static int weave(int a, int b) {
if (a < 0 || b < 0) {
throw new IllegalArgumentException();
}
if (a < 10 && b < 10) {
return a * 10 + b;
} else {
return weave(a / 10, b / 10) * 100 + weave(a % 10, b % 10);
}
}
ways to test if a non-negative integer x is a 1-digit number:
x < 10
x / 10 == 0
x % 10 == x
1 header
2 exception
1 reasonable attempt
1 correct
5 base case
1 reasonable attempt to test x or y for 0 or 1-digit
1 reasonable attempt to test x and y for 0 or 1-digit
2 correct test: either both 0 or both 1-digit or equivalent
1 correct return (requires correct test):
if (x == 0 && y == 0) { return 0; }
if (x < 10 && y < 10) { return 10 * x + y; }
note: -1 from correctness if there are extra base cases that don't work
7 recursive case
6 correct expression elements:
100 * weave(x / 10, y / 10) + 10 * (x % 10) + y % 10;
+---+ +-------------------+ +--+ +------+ +----+
1 2 1 1 1
1 pieces fit together:
* this is in an else branch relative to a base case or has a test that
makes some kind of sense
* they are adding together at least 2 of these elements
* they are returning the sum of the elements they are adding together
* no extraneous code or other recursive cases that don't work
notes:
* All loop, extra data structure, string solutions go to question leader.
* If they have 2 or more recursive cases, give them the max of the "correct
expression elements" rather than the sum
Problem #3
Statement Output
------------------------------------------------------------
var1.method1(); Cat 1
var2.method1(); Bell 1/Candle 1
var3.method1(); Bell 1/Candle 1
var1.method2(); Candle 2/Cat 1
var2.method2(); Book 2
var3.method2(); Candle 2/Bell 1/Candle 1
var4.method2(); compiler error
var5.method2(); Candle 2/Cat 1
var6.method2(); Book 2
var1.method3(); compiler error
var2.method3(); Book 3
var3.method3(); compiler error
((Cat)var5).method3(); Cat 3
((Bell)var1).method3(); compiler error
((Bell)var4).method1(); runtime error
((Cat)var1).method3(); Cat 3
((Candle)var4).method1(); Candle 1
((Book)var5).method3(); runtime error
((Bell)var6).method3(); compiler error
((Candle)var4).method2(); Candle 2/Candle 1
1 pt each
-1 if no slashes anywhere
-0 if they put quotes around answers
Problem #4
before after code
-----------------------+-----------------------+-------------------------------
p->[1] | p->[1]->[3] | p.next = q.next;
| | q.next = null;
q->[2]->[3] | q->[2] |
-----------------------+-----------------------+-------------------------------
p->[1] | p->[2]->[1] | ListNode temp = p;
| | p = q;
q->[2]->[3] | q->[3] | q = q.next;
| | p.next = temp;
-----------------------+-----------------------+-------------------------------
p->[1] | p->[1]->[3] | p.next = q.next;
| | q.next.next.next = q;
q->[2]->[3]->[4] | q->[4]->[2] | q = q.next.next;
| | q.next.next = null;
| | p.next.next = null;
-----------------------+-----------------------+-------------------------------
p->[1]->[2] | p->[2]->[4] | p.next.next = q.next;
| | q.next.next.next = q;
q->[3]->[4]->[5] | q->[5]->[3]->[1] | q.next = p;
| | q = p.next.next.next;
| | p = p.next;
| | p.next.next = null;
| | q.next.next.next = null;
-----------------------+-----------------------+-------------------------------
2 problem 1
1 attempt: change 2 of (2 ~.next)
1 correct
3 problem 2
1 attempt: change 2 of (p, q, 1 ~.next)
2 correct
4 problem 3
1 attempt: change 3 of (q, 4 ~.next)
1 better attempt: change all 5 of (q, 4 ~.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
solutions
// shifting loop going forwards, decrementing size, decrementing i
public void removeAll(int n) {
for (int i = 0; i < size; i++) {
if (elementData[i] == n) {
for (int j = i; j < size - 1; j++) {
elementData[j] = elementData[j + 1];
}
size--;
i--;
}
}
}
// shifting loop going forwards, decrementing size, if/else for i
public void removeAll(int n) {
int i = 0;
while (i < size) {
if (elementData[i] == n) {
for (int j = i + 1; j < size; j++) {
elementData[j - 1] = elementData[j];
}
size--;
} else {
i++;
}
}
}
// nice O(n) solution that moves values not equal to n earlier in array
public void removeAll(int n) {
int newSize = 0;
for (int i = 0; i < size; i++) {
if (elementData[i] != n) {
elementData[newSize] = elementData[i];
newSize++;
}
}
size = newSize;
}
// shifting loop going backwards, handles 2-in-a-row even with count
public void removeAll(int n) {
int count = 0;
for (int i = size - 1; i >= 0; i--) {
if (elementData[i] == n) {
for (int j = i; j < size - 1; j++) {
elementData[j] = elementData[j + 1];
}
count++;
}
}
size -= count;
}
1 header (non-void return type okay if consistent with a return)
3 finding values to be removed
1 loop attempt: within OBOB of examining size values or all values
1 loop with correct bounds
1 test whether elementData[i] == target value
6 correctly removes values with an inner loop
1 reasonable attempt to shift a new value into elementData[i] (doesn't
require a loop)
1 inner loop that correctly shifts if array has excess capacity (correct
bounds, pieces fit together)
1 reasonable attempt to reset size for values it finds
1 inner loop works correctly when array is full and resetting of size is
done correctly (resets size in this case and only this case and in a way
that causes the outer loop to examine one fewer element)
2 correctly handles the two-in-a-row case (as in i-- or while/if/else)
Notes: -3 if they use an extra structure (array, ArrayList, etc)
single loop solutions that might work graded separately
Problem #6
solution
public void makeSortedSequence(Queue<Integer> q) {
Stack<Integer> s = new Stack<Integer>();
if (!q.isEmpty()) {
int last = q.remove();
s.push(last);
int oldSize = q.size();
for (int i = 0; i < oldSize; i++) {
int next = q.remove();
if (next < last) {
q.add(next);
} else {
s.push(next);
last = next;
}
}
while (!q.isEmpty()) {
s.push(q.remove());
}
while (!s.isEmpty()) {
q.add(s.pop());
}
while (!q.isEmpty()) {
s.push(q.remove());
}
while (!s.isEmpty()) {
q.add(s.pop());
}
}
}
1 header (non-void return okay if consistent, static is okay)
2 constructs temporary stack using generics correctly (-1 per error)
3 basic loops (generous)
1 a loop that goes q->s and a later loop that goes s->q
1 a later loop that goes q->s
1 a later loop that goes s->q
3 correctly handles first value and empty queue
1 special test for empty queue (loop test is not enough) so that the method
does nothing in that case and doesn't throw an exception
1 reasonable attempt to remove first value and store it in a variable
1 correctly removes first value, stores it in a variable, and places it
where the sequence goes (either to the stack or the end of the queue)
note: they get these points if they initialize last to Integer.MIN_VALUE
and don't generate an exception for the empty list
1 one of their loops over the queue makes a reasonable attempt to send some
values to the stack and some values to the end of the queue
5 correctly identifies the sequence
1 reasonable attempt to see if next value is greater than or equal to the
last sequence value (not enough to test adjacent values)
2 they are looping over the queue using the old size value so that they
know when to stop or equivalent (-1 if OBOB)
2 pieces fit together for their code to correctly identify the sorted
sequence and to process each value of the queue exactly once (requires
that they are removing one value at a time from the queue and correctly
updating a previous value, but no double jeopardy with processing of
first value and using size instead of old size; -1 if minor error like
greater-than versus greater-than-or-equal)
10 combination of stack/queue loops leads to correct sequence (requires that
they have a loop over the queue that reads one value at a time and sends
that value either to the stack or to the end of the queue...fix errors they
have already lost points for). Simulate this case:
front [100, 1, 200, 2, 300, 3, 400, 4] back
10 [100, 200, 300, 400, 1, 2, 3, 4] F1 F2
8 [4, 3, 2, 1, 400, 300, 200, 100] R2 R1
6 [1, 2, 3, 4, 100, 200, 300, 400] F2 F1
4 [400, 300, 200, 100, 4, 3, 2, 1] R1 R2
4 [4, 3, 2, 1, 100, 200, 300, 400] R2 F1
2 [400, 300, 200, 100, 1, 2, 3, 4] R1 F2
2 [100, 200, 300, 400, 4, 3, 2, 1] F1 R2
2 [1, 2, 3, 4, 400, 300, 200, 100] F2 R1
Notes:
-3 from the 10 correctness points if it isn't O(n)
no parens for calls like q.remove() is a syntax mistake (could be free)
naming errors where you can infer what they meant are -1 each, max -2:
while (!s.isEmpty()) { q.add(s.remove()); }
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
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011