1. Recursive Tracing

Method Call                      Output Produced
------------------------------------------------
mystery(5);                      +*
mystery(15);                     ++**
mystery(304);                    +++*--
mystery(9247);                   ++++*--*
mystery(43269);                  +++++-*--*

2. Recursive Programming

Two possible solutions are shown below

public int doubleDigit(int n, int d) {
	if (d < 0 || d > 9) {
		throw new IllegalArgumentException();
	}
	
	if (n < 0) {
		return -doubleDigit(-n, d);
	} else if (n == 0) {
		return 0;
	} else if (n % 10 == d) {
		return doubleDigit(n / 10, d) * 100 + d * 11;
	} else {
		return doubleDigit(n / 10, d) * 10 + n % 10;
	}
}

public int doubleDigit(int n, int d) {
	if (d < 0 || d > 9) {
		throw new IllegalArgumentException();
	}
	if (n < 0) {
		return -doubleDigit(-n, d);
	} else if (n == d) {
		return d * 11;
	} else if (n < 10) {
		return n;
	} else if (n % 10 == d) {
		return doubleDigit(n / 10, d) * 100 + doubleDigit(n % 10, d);
	} else {
		return doubleDigit(n / 10, d) * 10 + n % 10;
	}
}

3. ListNode Programming

One possible solution is shown for each problem below

before                   after                      code
-----------------------+-----------------------+-------------------------------
 p->[1]                | p                     | q.next.next = p;
                       |                       | p = null;
 q->[2]->[3]           | q->[2]->[3]->[1]      |
-----------------------+-----------------------+-------------------------------
 p->[1]->[2]->[3]      | p->[2]->[3]           | q = p;
                       |                       | p = p.next;
 q                     | q->[1]                | q.next = null;
-----------------------+-----------------------+-------------------------------
 p->[1]->[2]           | p->[2]                | q.next.next = q;
                       |                       | q = q.next;
 q->[3]->[4]           | q->[4]->[3]->[1]      | q.next.next = p;
                       |                       | p = p.next;
                       |                       | q.next.next.next = null;
-----------------------+-----------------------+-------------------------------
 p->[1]->[2]           | p->[4]->[2]->[3]      | q.next.next.next = p;
                       |                       | ListNode temp = q;
 q->[3]->[4]->[5]      | q->[5]->[1]           | q = q.next.next;
                       |                       | temp.next.next = q.next.next;
                       |                       | p.next.next = temp;
                       |                       | p = temp.next;
                       |                       | p.next.next.next = null;
                       |                       | q.next.next = null;
-----------------------+-----------------------+-------------------------------

4. ArrayIntList Programming

Two possible solutions are shown below

public void removeRange(int start, int stop) {
	if (start < 0 || stop > size || start > stop) {
		throw new IllegalArgumentException();
	}
	int delta = stop - start;
	for (int i = stop; i < size; i++) {
		elementData[i - delta] = elementData[i];
	}
	size -= delta;
}

public void removeRange(int start, int stop) {
	if (stop - start < 0 || stop > size || start < 0) {
		throw new IllegalArgumentException();
	}
	int newSize = start;
	for (int i = stop; i < size; i++) {
		elementData[newSize] = elementData[i];
		newSize++;
	}
	size = newSize;
}

5. Collections Programming

One possible solution is shown below.

public static Set<String> whatToCook(Map<String, Set<String>> recipes, Set<String> pantry) {
	if (recipes.size() == 0) {
		throw new IllegalArgumentException();
	}
	Set<String> result = new HashSet<>();

	// Lower case all items in pantry for lookup later
	Set<String> lowercasePantry = new HashSet<>();
	for (String ingredient : pantry) {
		lowercasePantry.add(ingredient.toLowerCase());
	}
	
	// Go through each recipe
	for (String recipe : recipes.keySet()) {
		Set<String> ingredients = recipes.get(recipe);
		boolean canMake = true;
	
		for (String ingredient : ingredients) {
			if (!lowercasePantry.contains(ingredient.toLowerCase())) {
				canMake = false;
			}
		}
		if (canMake) {
			result.add(recipe);
		}
	}
	return result;
}

6. Stacks and Queues

One possible solution is shown below

public static void expand(Stack<Integer> s1, Stack<Integer> s2) {
	if (s1.size() != s2.size()) {
		throw new IllegalArgumentException();
	}
	Queue<Integer> q = new LinkedList<Integer>();

	// merge the values into the q
	while (!s1.isEmpty()) {
		q.add(s2.pop());
		q.add(s1.pop());
	}

	// split the values up and make duplicates as you go
	while (!q.isEmpty()) {
		int n2 = q.remove();
		int n1 = q.remove();
		for (int i = 0; i < n2; i++) {
			s1.push(n1);
		}
		s2.push(n2);
	}

	// fix order
	s2q(s2, q);
	q2s(q, s2);
	s2q(s1, q);
	q2s(q, s1);
}