<![CDATA[
Problem #1
Preorder traversal 0, 3, 2, 9, 4, 1, 6, 5, 7, 8
Inorder traversal 2, 9, 3, 0, 6, 1, 5, 4, 7, 8
Postorder traversal 9, 2, 3, 6, 5, 1, 8, 7, 4, 0
2 points each, only partial credit is if the sequence matches the right answer
other than one single error (missing number, wrong number, transposed pair)
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)
1 exception
4 recursive cases
1 recurse on digitMatch(x / 10, y / 10)
1 comparing x % 10 == y % 10
1 adding 1 when digits match
1 correct (pieces fit together for recursive case)
3 base cases
base case on 1-digit numbers
1 attempt to test for 1-digit numbers (something sort of like x < 10
or x/10 == 0)
1 correct structure & tests: base cases for all combinations (both
1-digit, only one 1-digit) and correct tests
1 all correct (correct test, returns 0 or 1 depending upon digit match)
base case on zeros (generally only gets 1 point, show to question leader
if you think it could get more)
1 attempt to test for zero (x==0)
Problem #3
Statement Output
------------------------------------------------------------
var1.method1(); Scoop 1
var2.method1(); Spoon 1/Cone 1
var3.method1(); Cone 1
var4.method1(); compiler error
var5.method1(); Scoop 1
var6.method1(); compiler error
var1.method2(); Cone 2/Scoop 1
var2.method2(); Cone 2/Spoon 1/Cone 1
var3.method2(); Cone 2/Cone 1
var4.method2(); compiler error
var5.method2(); Cone 2/Scoop 1
var6.method2(); compiler error
((Spoon)var1).method3(); compiler error
((Cup)var6).method3(); Cup 3
((Scoop)var4).method1(); runtime error
((Cone)var6).method2(); Cone 2/Cone 1
((Cone)var4).method1(); Spoon 1/Cone 1
((Scoop)var6).method3(); runtime error
((Scoop)var3).method3(); runtime error
((Scoop)var5).method3(); Scoop 3
1/2 each, round up
Problem #4
solution
public void reverseByN(Queue<Integer> q, int n) {
Stack<Integer> s = new ArrayStack<Integer>();
int times = q.size() / n;
int extra = q.size() % n;
for (int i = 0; i < times; i++) {
for (int j = 0; j < n; j++)
s.push(q.remove());
while (!s.isEmpty())
q.add(s.pop());
}
for (int i = 0; i < extra; i++)
s.push(q.remove());
while (!s.isEmpty())
q.enqueue(s.pop());
}
1 header (-1 per error, non-void return okay if consistent)
1 construct stack (-1 per error)
6 works when q.size() is a multiple of n
2 outer loop related to q.size()
1 attempt (some kind of loop related to q.size()
1 correct (executes q.size()/n times, -1 if obob)
2 inner loop to move n values Q -> S (-1 if obob)
2 then inner loop to move n values S -> Q (-1 if obob)
2 works when q.size() is not a multiple of n
1 attempt to handle this case
1 correctly handles this case
Problem #5
solution
public void printLevel(int target) {
if (target < 1)
throw new IllegalArgumentException();
printLevel(overallRoot, target, 1);
}
private void printLevel(IntTreeNode root, int target, int level) {
if (root != null)
if (level == target)
System.out.println(root.data);
else {
printLevel(root.right, target, level + 1);
printLevel(root.left, target, level + 1);
}
}
1 overall setup: correct public/private headers, public method passes
overallRoot to private method
1 correct exception
1 base case for null
2 recursive calls on root.left and root.right
1 attempt: both calls exist
1 correct: recurse on right before left
3 correctly computes level information (recurse on level + 1 vs target or
recurs on level - 1 vs 1)
1 attempt
2 correct (-1 if minor error like obob)
2 prints data for target level (requires "compute level" attempt)
1 attempt
1 correct
Problem #6
solution
public static int recordDate(Map<String, List<String>> dates,
String name1, String name2) {
if (!dates.containsKey(name1)) {
dates.put(name1, new LinkedList<String>());
}
if (!dates.containsKey(name2)) {
dates.put(name2, new LinkedList<String>());
}
dates.get(name1).add(0, name2);
dates.get(name2).add(0, name1);
int n = 0;
for (String s : dates.get(name1)) {
if (s.equals(name2)) {
n++;
}
}
return n;
}
1 header
3 constructs new LinkedList the first time names are seen
1 reasonable attempt for one name: testing for name not in map, adding a
new linked list if not
1 reasonable attempt for both names
1 correct code for one name (very nitpicky, including "()" in call to
LinkedList constructor)
3 adding to lists
1 reasonable attempt for one name: requires a call on get for the map and a
call on add with the other name
1 reasonable attempt for both names
1 correct code for one name (very nitpicky)
3 returning date #
1 basic idea: loop through one list searching for the other name
1 correct loop over one list, testing for the other name (requires call on
String equals method)
1 counter setup: initialize counter, increment in a loop, return after
loop, correct value of n
Problem #7
solution
public class TeamData implements Comparable<TeamData> {
private String name;
private int solved;
private int totalTime;
private int problems;
public TeamData(String name, int problems) {
this.name = name;
this.problems = problems;
this.totalTime = 0;
this.solved = 0;
}
public void success(int problem, int time) {
solved++;
totalTime += time;
}
public String toString() {
return name + " solved " + solved + " of " + problems + " in "
+ totalTime + " minutes";
}
public int solved() {
return solved;
}
public int time() {
return totalTime;
}
public double percentCorrect() {
return 100.0 * solved / problems;
}
public int compareTo(TeamData other) {
if (solved != other.solved)
return other.solved - solved;
else
return totalTime - other.totalTime;
}
}
1 class header
3 fields (-1 per missing field, -1 once if not private, okay to have extra)
1 constructor
2 solved and time methods
1 reasonable attempt (at least one method completely correct or two methods
that are each partially correct)
1 all correct
2 percentCorrect method
1 reasonable attempt (exists, divides solved by problems)
1 correct
1 success method
1 toString
4 compareTo
1 primary comparison is for problems solved
1 compares times when problems solved is equal
1 correct comparison for problems solved (most people will miss this)
1 all other aspects correct (header, time comparison)
Problem #8
solution
public void makeFull() {
overallRoot = makeFull(overallRoot, 1);
}
private IntTreeNode makeFull(IntTreeNode root, int level) {
if (root != null) {
if (root.left == null && root.right != null) {
root = new IntTreeNode(-level, root, root.right);
root.left.right = null;
} else if (root.left != null && root.right == null) {
root = new IntTreeNode(-level, root.left, root);
root.right.left = null;
}
root.left = makeFull(root.left, level + 1);
root.right = makeFull(root.right, level + 1);
}
return root;
}
1 overall setup: public header (return is not okay) and private header with a
root parameter and public method calls private method passing it overallRoot
5 used x = change(x) (if you think they didn't need it, show to quest leader)
1 overallRoot = recurse(overallRoot)
1 private method has return type IntTreeNode
1 root.left = recurse(root.left) (at least 1 && all left are like this)
1 root.right = recurse(root.right) (at least 1 && all right are like this)
1 private method returns an IntTreeNode in at least one case
1 root == null case
1 correctly computes level
3 adding new nodes: 1-child cases
1 correct tests for both of the 1-child cases
1 correctly constructs a node with the same child as the old root and with
the old root as a child where there was an empty subtree for one case
(should have data that is minus level, but no double jeopardy with level
computation)
1 correct construction for second 1-child case (can get this if there is a
minor error that lost the first node construction point)
2 severing links for old parent nodes
1 correctly sets old child link to null for one case
1 correctly sets old child link to null for second case
1 correct recursive calls are made for 2-child case (left and right)
1 recursive calls are made for 1-child cases
notes:
attempt to change data fields or iterative or constructing too many nodes go to
Question Leader
if they call 0-argument or 1-argument node constructor, that is a syntax error
first syntax error is free
then -1 per syntax category, max -2
Problem #9
solutions
public void interleave(LinkedIntList other) {
if (front == null) {
front = other.front;
} else if (other.front != null) {
ListNode current1 = front;
ListNode current2 = other.front;
while (current1.next != null && current2.next != null) {
ListNode temp = current1.next;
current1.next = current2;
current2 = current2.next;
current1.next.next = temp;
current1 = temp;
}
if (current1.next == null)
current1.next = current2;
else {
current2.next = current1.next;
current1.next = current2;
}
}
other.front = null;
}
1 header
3 front == null
1 test for it
1 sets front = other.front
1 sets other.front to null in this case (might not need special test)
1 works when other.front == null (does nothing)
9 both nonempty, no excess
12 sets other.front to null in this case
1 using curr1/curr2 variables (curr2 might be other.front)
1 some kind of "while not null" loop
3 basic idea: 4 of 5 steps
3 correct (ignoring last pair if code to handle it after loop)
6 code to handle excess (requires 4 of 5 steps)
3 idea: stops curr1 early, test which went null, at least one correct
assignment
3 all correct
1 header
2 generous pattern matching
1 attempt to rearrange links for first 3 values:
requires resetting front
requires resetting at least two ".next" fields
normally comes before loop
1 attempt at a loop to rearrange links for later sequences (or recursive
equivalent):
requires a current, test on current or current... becoming null
requires resetting at least two ".next" fields
3 Simple cases
1 works (does nothing) for empty list (requires test)
1 works (does nothing) for 1-element list (requires test)
1 works (does nothing) for 2-element (requires test)
7 Works for specific cases (if you think they have a bug that is not caught by
the test cases, ask the question leader what points to deduct)
1 3-element list
1 4-element list
1 5-element list
1 6-element list (0.5 pt if just first triple is bad)
1 7-element list (0.5 pt if just first triple is bad)
1 9-element list (0.5 pt if just first triple is bad)
1 11-element list (0.5 pt if just first triple is bad)
We have a general rule that if you can fix one problem and it suddenly works,
then we make that fix and charge them 4 points. If this gives someone a higher
score, you can grade it that way. But don't spend too much time trying to
figure out their mistakes.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011