<![CDATA[
Problem #1
solution
1. Method Call Output Produced
------------------------------------------------
mystery(1) 1
mystery(4) 1, 2, 4
mystery(16) 1, 2, 4, 8, 16
mystery(30) 1, 3, 7, 15, 30
mystery(100) 1, 3, 6, 12, 25, 50, 100
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 and the comma errors should be capped at -2 for the entire problem.
Problem #2
solution
public int digitMatch(int x, int y) {
if (x < 0 || y < 0)
throw new IllegalArgumentException();
else if (x < 10 || y < 10) {
if (x % 10 == y % 10)
return 1;
else
return 0;
} else if (x % 10 == y % 10)
return 1 + digitMatch(x / 10, y / 10);
else
return digitMatch(x / 10, y / 10);
}
public int digitMatch(int x, int y) {
if (x < 0 || y < 0)
throw new IllegalArgumentException();
else {
int count = 0;
if (x % 10 == y % 10)
count++;
if (x >= 10 && y >= 10)
count+= digitMatch2(x / 10, y / 10);
return count;
}
}
1 header (okay if it's static)
2 exception
1 attempt
1 correct
6 recursive cases
1 recurse on digitMatch(x / 10, y / 10)
1 comparing x % 10 == y % 10
2 adding 1 when digits match
2 correct
6 base cases
base case on 1-digit numbers
2 attempt to test for 1-digit numbers (something sort of like x < 10
or x/10 == 0)
2 correct structure & tests: base cases for all combinations (both
1-digit, only one 1-digit) and correct tests
2 all correct (correct test, returns 0 or 1 depending upon digit match)
base case on zeros (generally only gets 2 points, show to question leader
if you think it could get more)
2 attempt to test for zero (x==0)
Problem #3
before after code
-----------------------+-----------------------+-------------------------------
| |
p->[1]->[2] | p->[1] | q = p.next;
| | p.next = null;
q | q->[2] |
| |
-----------------------+-----------------------+-------------------------------
| |
p->[1]->[2] | p->[2] | q = p;
| | p = p.next;
q | q->[1] | q.next = null;
| |
-----------------------+-----------------------+-------------------------------
| |
p->[1]->[2]->[3] | p->[1]->[4]->[2]->[5] | ListNode temp = q;
| | q = p.next.next;
q->[4]->[5] | q->[3] | p.next.next = temp.next;
| | temp.next = p.next;
| | p.next = temp;
| |
-----------------------+-----------------------+-------------------------------
4 part 1
1 reset q
1 reset something.next
2 correct
5 part 2
1 reset p
1 reset q
1 reset something.next
2 correct
6 part 3
1 reset q
1 reset two something.next
1 reset a third something.next
3 correct
Notes
can lose up to 2 syntax points if they get correctness points, examples:
-1 not declaring temp variable to be of type ListNode
-1 saying p.next() instead of p.next
Problem #4
Statement Output
------------------------------------------------------------
var1.method2(); compiler error
var2.method2(); Bunch 2/Bunch 3
var3.method2(); Bunch 2/Bit 3
var4.method2(); Bunch 2/Page 3
var5.method2(); compiler error
var6.method2(); Bunch 2/Page 3
var1.method3(); compiler error
var2.method3(); Bunch 3
var3.method3(); Bit 3
var4.method3(); Page 3
var5.method3(); compiler error
var6.method3(); Page 3
((Bit)var6).method1(); runtime error
((Bunch)var1).method1(); compiler error
((Bunch)var1).method2(); Bunch 2/Folder 3/Bunch 3
((Folder)var1).method3(); Folder 3/Bunch 3
((Folder)var6).method1(); Folder 1
((Page)var1).method1(); runtime error
((Page)var4).method2(); Bunch 2/Page 3
((Folder)var3).method1(); runtime error
1 pt each
-1 if no slashes anywhere
-0 if they put quotes around answers
Problem #5
solution
public void compressDuplicates(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());
if (!q.isEmpty()) {
int last = q.remove();
int count = 1;
while (!q.isEmpty()) {
int next = q.remove();
if (next == last)
count++;
else {
s.push(count);
s.push(last);
count = 1;
last = next;
}
}
s.push(count);
s.push(last);
}
}
2 header (-1 per error, okay if it's static)
2 constructs temporary queue using generics correctly (-1 per error)
4 first S -> Q, Q -> S
2 attempt
2 correct
4 second S -> Q, Q -> S
2 attempt
2 correct
2 basic idea: keeping track of a prev value, counting occurrences
1 works (does nothing) for empty stack (requires special test)
10 points correctly compressing (requires basic idea)
2 correct initialization
1 attempt (get one value, initialize counter, or equivalent)
1 correct (just one value, count of 1, correct scope)
4 correct update
1 test each adjacent pair for equality
1 correct when equal (increment counter by 1)
2 correct when not equal:
1 store the 2 values in the structure
1 correctly reset count and prev
2 correctly handles last sequence
1 attempt (trying to handle this case)
1 correct (do it correctly)
2 correct order of value/count pair and all pairs correctly added with
nothing extra (have to be able to tell which is the count and which is
the value)
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
solution
public boolean isConsecutive() {
for (int i = 0; i < size - 1; i++)
if (elementData[i + 1] != elementData[i] + 1)
return false;
return true;
}
1 header
1 some kind of loop that iterates over the array (requires test against
size or elementdata.length and some kind of reference to
elementData[<something>])
2 correct loop bounds to do size-1 comparisons
1 within obob
1 correct
3 correctly compares adjacent values in the array
1 comparison of elementData[i] vs elementData[i + 1] or elementData[i - 1]
2 correct comparison (elementData[i]==1+elementData[i+1], -1 if reversed)
3 return true/false correctly
1 attempt
2 correct (lose these if they reverse or return early)
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011