<![CDATA[
Problem #3
Solution:
public boolean equals(IntTree other) {
return equals(overallRoot, other.overallRoot);
}
private boolean equals(IntTreeNode root1, IntTreeNode root2) {
if (root1 == null || root2 == null)
return root1 == null && root2 == null;
else
return root1.data == root2.data
&& equals(root1.left, root2.left)
&& equals(root1.right, root2.right);
}
1 correct public header
1 private header with two tree nodes, call on private, public returns call on
private
3 base case when one of the roots is null
1 attempt (testing each root against null)
1 returns true when both are null (requires test)
1 returns false when only one is null (requires test)
5 recursive case
1 attempt to compare root1.data and root2.data
1 correctly returns false when root1.data != root2.data
1 recursive calls attempt (must see calls on equals(root1.left, root2.left)
and equals(root1.right, root2.right))
2 correct in all cases
Problem #4
Solution:
public class CachedSongList extends SongList {
private List<String> songs;
private Map<String, MP3> mp3s;
public CachedSongList(UserData data) {
super(data);
songs = new LinkedList<String>();
mp3s = new HashMap<String, MP3>();
}
public MP3 get(String name) {
if (mp3s.containsKey(name)) {
songs.remove(name);
songs.add(0, name);
return mp3s.get(name);
} else {
MP3 response = super.get(name);
songs.add(0, name);
if (songs.size() == 11) {
mp3s.remove(songs.get(10));
songs.remove(10);
}
mp3s.put(name, response);
return response;
}
}
public String getRecent(int index) {
return songs.get(index);
}
public int recentSize() {
if (songs.size() != mp3s.size())
throw new IllegalStateException();
return songs.size();
}
}
1 class header
4 fields
2 List<String> for song names (-1 if not interface type)
2 Map<String, MP3> or parallel List<MP3> (-1 if not interface type)
-1 if nonprivate
3 constructor
1 header and super(data)
2 initialize their fields
1 attempt
1 correct
9 get
3 song already in the list
1 correct test for this case
1 moves this song to the top of the recent list
1 correctly returns cached MP3
6 song not in the list
1 correct call on super.get, stores result in a variable
1 adds this song/MP3 to the cache
1 puts this song at the top of the recent list/correctly shifts
1 removes the 11th song from list (if there is one)
1 removes the 11th MP3 from the cache (if there is one)
1 returns stored result
3 getRecent & recentSize
1 getRecent attempt
1 recentSize attempt
1 both correct
Array based solutions go to the question leader.
If they destroy a method they inherited (e.g., put, contains): -1, -2, -3 based
on quality (max -5).
Problem #5
Solution:
public class ItemOrder implements Comparable<ItemOrder> {
private String item;
private int quantity;
private int pricePer;
private String note;
public ItemOrder(String item, int quantity, int pricePer) {
this(item, null, quantity, pricePer);
}
public ItemOrder(String item, String note, int quantity,
int pricePer) {
this.item = item;
this.note = note;
this.quantity = quantity;
this.pricePer = pricePer;
}
public String getItem() {
return item;
}
public int getPrice() {
return quantity * pricePer;
}
public String toString() {
String text = "item #" + item;
if (note != null)
text += " (" + note + ")";
text = text + ": " + quantity + "@" + moneyString(pricePer) +
" = " + moneyString(getPrice());
return text;
}
private String moneyString(int cents) {
return "$" + cents / 100 + "." + cents % 100 / 10 + cents % 10;
}
public int compareTo(ItemOrder other) {
if (!item.equals(other.item))
return item.compareTo(other.item);
else
return other.getPrice() - getPrice();
}
}
1 class header
4 fields (1 point each, -1 if not private, okay to have a 5th field for
hasOptionalText)
3 two constructors
1 reasonable attempt for 3-argument constructor
1 reasonable attempt for 4-argument constructor
1 both correct (assign fields, etc)
1 getItem correct (does NOT include optional text)
2 getPrice
1 attempt
1 correct (not pricePer, but total price)
5 toString
1 properly converts pricePer to dollars/cents ignoring 0 after decimal
1 properly converts total price to dollars/cents ignoring 0 after decimal
1 properly handles 0 after decimal in two previous
1 string also includes item and quantity fields
1 otherwise correct (-1 if System.out)
4 compareTo
1 attempt to compare the item numbers (some kind of test, attempt to call
compareTo on the strings)
1 attempt to compare the prices (could be comparing pricePer, return
some kind of difference)
1 correct order (item numbers first, then price)
1 otherwise correct
Problem #6
Solution:
public IntTree combineWith(IntTree other) {
IntTree result = new IntTree();
result.overallRoot = combine(overallRoot, other.overallRoot);
return result;
}
private IntTreeNode combine(IntTreeNode root1, IntTreeNode root2) {
if (root1 == null)
if (root2 == null)
return null;
else // root2 != null
return new IntTreeNode(2, combine(null, root2.left),
combine(null, root2.right));
else // root1 != null
if (root2 == null)
return new IntTreeNode(1, combine(root1.left, null),
combine(root1.right, null));
else
return new IntTreeNode(3, combine(root1.left, root2.left),
combine(root1.right, root2.right));
}
1 public header (must be IntTree)
1 private header passing two IntTreeNodes and returns an IntTreeNode (or at
least once they construct an IntTreeNode that is passed as a third parameter)
1 constructs IntTree in public
1 call on private method passing both trees and return IntTree from public
(okay to return an IntTreeNode if that's what they said in their public
header)
3 constructs nodes in the private method
1 attempt
2 always constructed when needed and linked into new tree (-1 if close)
2 root1 == null, root2 == null case
1 attempt (requires test)
1 correct (returns null)
4 root1 == null, root2 != null case
1 attempt (requires test)
1 set root data to 2
2 correct assuming node has been constructed
4 root1 != null, root2 == null case
1 attempt (requires test)
1 set root data to 1
2 correct assuming node has been constructed
3 root1 != null, root2 != null case
1 attempt (requires test)
1 set root data to 3
1 correct assuming node has been constructed
Problem #7
Solution:
public void reorder() {
if (front != null) {
ListNode current = front;
while (current.next != null) {
if (current.next.data < 0) {
ListNode temp = current.next;
current.next = current.next.next;
temp.next = front;
front = temp;
} else
current = current.next;
}
}
}
1 header
1 works (does nothing) for empty list
1 works (does nothing) for 1-element list
4 loop
1 assign a current to front
1 loop while current != null or current.next != null
2 somewhere in loop, current = current.next
5 test for negative
1 attempt at test (generous--might be comparing against front.data or
comparing two adjacent values to see if second > first)
2 correct test (<something>.data < 0 or <something>.data <= front.data)
2 test is "one ahead" (comparing current.next.data or comparing
current.data with a prev)
8 move negatives to front of list (requires negative attempt)
2 correctly removes negative node:
current.next = current.next.next
prev.next = current.next
or equivalent
2 stores negative in a temp prior to removing (prev can be temp)
4 negative moved to front of list (could be put in a separate list and
added to front of the list after loop)
2 attempt (requires front = <something>)
2 correct
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011