<![CDATA[
Problem #1
Preorder traversal 0, 3, 7, 4, 6, 2, 9, 1, 5, 8
Inorder traversal 4, 7, 6, 3, 0, 1, 9, 2, 8, 5
Postorder traversal 4, 6, 7, 3, 1, 9, 8, 5, 2, 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
2. +------------+
| Picard |
+------------+
/ \
/ \
+------------+ +------------+
| Crusher | | Riker |
+------------+ +------------+
\ \
\ \
+------------+ +------------+
| LaForge | | Worf |
+------------+ +------------+
/ /
/ /
+------------+ +------------+
| Data | | Troi |
+------------+ +------------+
Only partial credit is 2 out of 4 points if just one node is in the wrong
place.
-------------------------------------------------------------------------------
Problem #3
Method Call Contents of Set Returned
-----------------------------------------------
mystery(grid, 1) [1, 2, 3, 4, 5]
mystery(grid, 2) [4, 6, 8, 9]
mystery(grid, 4) [4, 5, 6, 8]
1 pt for first problem
2 pt for second problem
2 pt for third problem
-1 for order error (just once for the entire problem)
-1 for duplicates (just once for the entire problem)
-1 for missing number
-1 for extra number
-0 for no brackets or no commas
no subproblem can go negative
Problem #4
solution
public String acronymFor(List<String> words) {
String acronym = "";
for (String next : words) {
acronym += next.toUpperCase().charAt(0);
}
return acronym;
}
1 correct header (static is okay)
1 loop over list (can be foreach, iterator, get/size, as long as it traverses
the list so that each string is visited once in the loop)
3 construct and return acronym; there are 5 things to do:
declare local String variable and initialize to empty string
return the local String variable at the end
get the first character of each string
convert that character to its capitalized version
concatenate each capital letter to the local string variable
The points are based on how many of the 5 they do right:
1 at least 2 of these
1 at least 4 of these
1 all 5 of these and the pieces fit together
notes:
-1 if they change the list
Problem #5
solutions
public int oddPathSum() {
return oddPathSum(overallRoot, 0);
}
private int oddPathSum(IntTreeNode root, int sum) {
if (root == null) {
return 0;
} else {
sum += root.data;
int result =
oddPathSum(root.left, sum) + oddPathSum(root.right, sum);
if (sum % 2 != 0) {
result++;
}
return result;
}
}
---------------------------------------------------------------------------
public int oddPathSum() {
return oddPathSum(overallRoot, false);
}
private int oddPathSum(IntTreeNode root, boolean odd) {
if (root == null) {
return 0;
} else {
if (root.data % 2 != 0) {
odd = !odd;
}
int result =
oddPathSum(root.left, odd) + oddPathSum(root.right, odd);
if (odd) {
result++;
}
return result;
}
}
---------------------------------------------------------------------------
public int oddPathSum() {
return oddPathSum(overallRoot, 0, 0);
}
private int oddPathSum(IntTreeNode root, int sum, int count) {
if (root == null) {
return count;
} else {
sum += root.data;
count = oddPathSum(root.left, sum, count);
count = oddPathSum(root.right, sum, count);
if (sum % 2 != 0) {
count++;
}
return count;
}
}
---------------------------------------------------------------------------
public int oddPathSum() {
return oddPathSum(overallRoot, 0);
}
private int oddPathSum(IntTreeNode root, int n) {
if (root == null) {
return 0;
}
n = (n + root.data) % 2;
return n + oddPathSum(root.left, n) + oddPathSum(root.right, n);
}
---------------------------------------------------------------------------
1 public header
1 overall setup: private method returning an int with a root parameter and a
second parameter that can keep track of odd path sum (e.g., sum/boolean),
public method calls private method passing it overallRoot and appropriate
starting value for second parameter, public method returns result of private
method
1 base case for null (tests for this and prevents any NullPointerException)
2 recursive calls
1 their answer includes recursive calls on root.left and root.right
1 correctly traverses the entire tree
2 correctly computes a value that can be used for odd path sum (for these
points, don't worry about whether their tests for odd path sum are correct;
you want to look at the initial call with overallRoot, how they incorporate
root.data, and the recursive calls they are making to see if the pieces fit
together to produce a value that can be tested for odd/even path sum):
1 reasonable attempt
1 correct (requires a recursive call on both left and right, but assume the
tree is traversed correctly)
3 correctly counts odd path sums
1 reasonable attempt: testing for odd path sum and returning a different
value in that case
2 correct (-1 if minor error like obob or counting even path sums)
notes:
* a count field loses the overall setup point if private method has void return
and always loses the 2 counting correctness points
* give to question leader any solutions that change the tree or use extra data
structures (even a string)
Problem #6
solution
public Map<String, Set<List<String>>> acronyms(Set<List<String>> lists) {
Map<String, Set<List<String>>> result =
new TreeMap<String, Set<List<String>>>();
for (List<String> words : lists) {
String acronym = acronymFor(words);
if (!result.containsKey(acronym)) {
result.put(acronym, new HashSet<List<String>>());
}
result.get(acronym).add(words);
}
return result;
}
1 header (static is okay)
2 construct and return proper map
1 reasonable attempt: map of strings to sets of lists of strings
1 all correct (correct generics, correct return, map is a TreeMap, used Map
interface for variable, missing parens are a syntax error)
1 loop over set (foreach or iterator)
1 get the acronym for the list (easiest if they call acronymFor)
3 add a new set to map when acronym is first seen
1 reasonable attempt to test for this case
1 reasonable attempt to construct a set that they add to their map (should
be a HashSet, only 1 mistake allowed)
1 all correct (tests whether this acronym is there, adds an entry if it is
new, associates it with a HashSet, correct generics)
2 adds list to existing set assuming key is there
1 reasonable attempt (getting something from the map that they then add to)
1 all correct
Problem #7
solution
public class ClockTime implements Comparable<ClockTime> {
private int hours;
private int minutes;
private String amPm;
public ClockTime(int hours, int minutes, String amPm) {
this.hours = hours;
this.minutes = minutes;
this.amPm = amPm;
}
public int compareTo(ClockTime other) {
if (!amPm.equals(other.amPm)) {
return amPm.compareTo(other.amPm);
} else if (hours != other.hours) {
return hours % 12 - other.hours % 12;
} else {
return minutes - other.minutes;
}
}
public int getHours() {
return hours;
}
public int getMinutes() {
return minutes;
}
public String getAmPm() {
return amPm;
}
public String toString() {
String result = hours + ":";
if (minutes < 10) {
result += "0" + minutes;
} else {
result += minutes;
}
result += " " + amPm;
return result;
}
}
1 class header
3 fields declared correctly (1 point per field, -1 if not private, okay to have
extra fields)
2 constructor
1 reasonable attempt to set fields correctly
1 all correct (header, setting fields)
2 get methods (getHours, getMinutes, getAmPm)
1 at least one corect
1 all correct
8 compareTo
2 correct am/pm test (-1 if == versus equals)
3 correct hours test
1 ignoring 12
2 including 12
1 reasonable attempt to handle this case
1 correctly handles this case
1 correct minutes test
2 correct order (am/pm, then hours, then minutes) and header
1 close (at most one transposition, header problem okay for this point)
1 correct order and header
4 toString
1 includes all 3 fields
1 all correct ignoring extra "0"
2 extra 0 included for 1-digit numbers
1 reasonable attempt to handle this case
1 correctly handles this case
Notes:
Give to question leader any solution that involves storing 0 for hour when
it is equal to 12.
There is a PracticeIt problem where you can test compareTo solutions.
Problem #8
solutions
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;
}
---------------------------------------------------------------------------
public void makeFull() {
overallRoot = makeFull(overallRoot, 1);
}
private IntTreeNode makeFull(IntTreeNode root, int level) {
if (root != null) {
if (root.left == null && root.right != null) {
IntTreeNode temp = makeFull(root.right, level + 1);
root.right = null;
return new IntTreeNode(-level, root, temp);
} else if (root.left != null && root.right == null) {
IntTreeNode temp = makeFull(root.left, level + 1);
root.left = null;
return new IntTreeNode(-level, temp, root);
}
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 returns root or modified root in all cases
1 root == null case (test for it, do nothing, never get a NullPointerException)
2 correctly computes level
1 level parameter in private method
1 correctly computes the level on each call (tend to lose this for ++)
4 adding new nodes: 1-child cases
1 correct test for one 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 test for second 1-child case
1 correct construction for second 1-child case (can get this if there is a
minor error that lost the first node construction point)
3 severing links for old parent nodes
1 reasonable attempt to sever at least one child link
1 correctly sets old child link to null for one case without losing access
to that subtree
1 correctly sets old child link to null for second case without losing
access to that subtree
2 correct recursive calls are made for 2-child case (left and right)
2 recursive calls are made for 1-child cases (lose these if they set children
to null)
notes:
Give to question leader solutions that avoid x=change(x), that have extra
data structures, that change data fields, that might not be O(n).
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
If the severing code doesn't work and causes other problems, give them the
attempt point for severing and then ignore that code.
If they morph nodes, they use both node construction correctness points and all
three severing points.
-------------------------------------------------------------------------------
Problem #9
solution
public LinkedIntList removeAlternatePairs() {
LinkedIntList result = new LinkedIntList();
if (front != null && front.next != null) {
result.front = front;
front = front.next.next;
ListNode current1 = result.front.next;
ListNode current2 = front;
while (current2 != null && current2.next != null &&
current2.next.next != null &&
current2.next.next.next != null) {
current1.next = current2.next.next;
current2.next.next = current2.next.next.next.next;
current2 = current2.next.next;
current1 = current1.next.next;
}
current1.next = null;
}
return result;
}
1 header (lose this if return type is ListNode even if they return a ListNode)
2 constructs and returns other LinkedIntList
1 reasonable attempt (can get this even if they are returning a ListNode)
1 correct (requires call on LinkedIntList constructor, proper return)
2 simples cases: can't get these for no code...each requires a test
1 length 0 case: does nothing and doesn't throw an exception
1 length 1 case: does nothing and doesn't throw an exception
note: should return empty list for each case, -1 once if they return null
3 generous pattern match
1 using curr1/curr2 variables to keep track of a position in each of the
two lists with a loop that changes each
1 resetting at least two "next" fields in a loop
1 a third "next" field is set to null in the loop or a "next" field is set
to null after the loop
12 other cases (could lose 2 points for not setting final node link to null)
2 length 2
1 length 3
1 length 4
1 length 5
2 length 6
1 length 7
1 length 9
1 length 10
1 length 11
1 length 14
notes:
The testing program will tell you if their only mistake is not setting the
final node's link to null for the constructed list (this costs 2 them 2 of the
correctness points).
-1 if they say other when they mean other.front (but only if that raises their
score)
We have a general rule that if you can fix one problem and it suddenly works,
then we make that fix and charge them 5 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. A single correction would involve adding or
deleting a single line of code like curr=curr.next or changing a test for
something like curr!=null to be curr.next!=null
Another example of a change would be if they use a name like "curr" when they
have variables with names like "curr1" and "curr2", so we don't know which one
they mean. That would require a 5-point charge to fix a single boolean
expression or a single line of code (you can't fix multiple things this way).
If they call a size method, that can be their -5 mistake (but they can't have a
second -5 mistake).
Any O(n^2) solutions or odd solutions (new nodes, changing data) go to the
question leader.
]]>
Stuart Reges
Last modified: Wed Jul 24 17:09:52 PDT 2019