143 Autumn 2013 Final Key

1.

1 Cookie / 1 Pudding
error
3 Puddings
1 Cookie / 1 Pudding / 1 Biscuit
error
2 Biscuits / 2 Cakes / 3 Cakes
error
2 Cakes / 3 Cakes
error
1 Cookie / 1 Pudding
error
2 Biscuits/ 2 Cakes / 3 Cakes
2 Biscuits / 2 Cakes
3 Puddings
error


2.

public class GroceryItem extends StoreItem implements Comparable<GroceryItem>{
	private boolean organic;
	private List<String> ingredients;
	
	public GroceryItem(String name, double price, boolean organic, List<String> ingredients) {
		super(name, price);
                if(ingredients == null || ingredients.isEmpty()) {
			throw new IllegalArgumentException();
		}
		this.organic = organic;
		this.ingredients = ingredients;
	}
	
	public void setDiscount(double discount) {
		if(!organic) {
			super.setDiscount(discount);
		}
	}
	
	public String toString() {
		String s = super.toString();
		if(organic) {
			s += ", organic";
		}
		s += ", ingredients: " + ingredients;
		return s;
	}
	
	public boolean containsAllergens(String ingredient){
		for(String i : ingredients) {
			if(i.contains(ingredient)) {
				return true;
			}
		}
		return false;
	}
	
	public int compareTo(GroceryItem other) {
		if(getCost() != other.getCost()) {
			if(getCost() > other.getCost()) {
				return 1;
			} else {
				return -1;
			}
		} else if(ingredients.size() != other.ingredients.size()) {
			return ingredients.size() - other.ingredients.size();
		} else {
			return getName().compareTo(other.getName());
		}
	}
}


3.

    {b=s, e=t, l=p, o=u, p=l, s=b, t=e, u=o}
    {a=e, e=p, f=e, k=s, p=e, s=k}
    {b=o, e=k, k=e, o=b, r=s, s=r} 


4. 
	public Map<Integer, Set<String>> split(Set<String> words) {
   Map<Integer, Set<String>> buckets = new TreeMap<Integer, Set<String>>();
   for (String word : words) {
      int n = word.length();
      if (!buckets.containsKey(n)) {
         buckets.put(n, new TreeSet<String>());
      }
      buckets.get(n).add(word);
   }
   return buckets;
}


5.

    Pre-order: 3, 2, 4, 5, 7, 0, 1, 6, 9, 8
    In-order: 4, 2, 7, 5, 0, 3, 1, 9, 6, 8
    Post-order: 4, 7, 0, 5, 2, 9, 8, 6, 1, 3 

                                 +------------+
                                 |  Dorothy   |
                                 +------------+
                              /                  \
                           /                        \
                        /                              \
               +------------+                      +------------+
               |CowardlyLion|                      |  Glinda    |
               +------------+                      +------------+
              /                                               \
             /                                                 \
            /                                                   \
     +------------+                                          +------------+       
     |  Billina   |                                          |   Tinman   |
     +------------+                                          +------------+
                                                              /           \         
                                                             /             \        
                                                            /               \       
                                                  +------------+             +------------+
                                                  |   Ozma     |             |   Wizard   |
                                                  +------------+             +------------+
                                                   /       \                      /
                                                  /         \                    /
                                                 /           \                  /
                                   +------------+       +------------+     +------------+
                                   | Munchkins  |       | Scarecrow  |     |    Toto    |
                                   +------------+       +------------+     +------------+


6.

	public boolean isHeap() {
		return isHeap(overallRoot);
	}

	private boolean isHeap(IntTreeNode root) {
		if (root != null) {
			boolean bigger = true;
			if (root.right != null) {
				bigger = root.right.data > root.data; 
			} 
			if(root.left != null) {
				bigger = bigger && root.left.data > root.data;
			}
			return isHeap(root.right) && isHeap(root.left) && bigger;
		}
		return true;
	}


7. 

public void limitPathSum(int max) {
    overallRoot = limitPathSum(overallRoot, max, 0);
}

private IntTreeNode limitPathSum(IntTreeNode root, int max, int current) {
    if (root != null) {
        current += root.data;
        if (current > max) {
            root = null;
        } else {
            root.left = limitPathSum(root.left, max, current);
            root.right = limitPathSum(root.right, max, current);
        }
    }
    return root;
}


8.

	public void markModN(int n) {
    	if(front != null) {
    		ListNode current = front;
    		if(front.data % n == 0) {
    			front = new ListNode(-n, front);
    		}
    		while(current.next != null) {
    			if(current.next.data % n == 0) {
    				current.next = new ListNode(-n, current.next);
    				current = current.next;
    			}
    			current = current.next;
    		}
    	}
    }