1. Recursive Tracing

Method Call                      Output Produced
------------------------------------------------
mystery(1);                      1
mystery(2);                      2, 1
mystery(4);                      4, 2, 1
mystery(8);                      8, 4, 2, 1
mystery(10);                     10, 5, 16, 8, 4, 2, 1

2. Recursive Programming

Two possible solutions are shown below

public static int weave(int x, int y) {
    if (x < 0 || y < 0) {
        throw new IllegalArgumentException();
    }
    if (x == 0 && y == 0) {
        return 0;
    } else {
        return 100 * weave(x / 10, y / 10) + 10 * (x % 10) + y % 10;
    }
}

public static int weave(int a, int b) {
    if (a < 0 || b < 0) {
        throw new IllegalArgumentException();
    }
    if (a < 10 && b < 10) {
        return a * 10 + b;
    } else {
        return weave(a / 10, b / 10) * 100 + weave(a % 10, b % 10);
    }
}

3. ListNode Programming

One possible solution is shown for each problem below

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

4. ArrayIntList Programming

One possible solution are shown below

public void removeMax() {
    if (size == 0) {
        throw new IllegalStateException();
    }
    int maxIndex = 0;
    for (int i = 1; i < size; i++) {
        if (elementData[i] > elementData[maxIndex]) {
            maxIndex = i;
        }
    }
    for (int i = maxIndex; i < size - 1; i++) {
        elementData[i] = elementData[i + 1];
    }
    size--;
}

5. Collections Programming

Two possible solution is shown below.

public static String expensiveRecipe(Map<String, Set<String>> recipes, 
																		 Map<String, Integer> prices) {
		if (recipes.isEmpty()) {
		    throw new IllegalArgumentException();
    }
    Map<String, Integer> recipePrices = new TreeMap<>();
    for (String recipe : recipes.keySet()) {
        Set<String> ingredients = recipes.get(recipe);

        int price = 0;
        for (String ingredient : ingredients) {
				    if (prices.containsKey(ingredient) {
	            price += prices.get(ingredient);
            }
        }

        recipePrices.put(recipe, price);
    }

    String costlyRecipe = null;
    for (String recipe : recipePrices.keySet()) {
        if (costlyRecipe == null || recipePrices.get(recipe) > recipePrices.get(costlyRecipe)) {
            costlyRecipe = recipe;
        }
    }
    return costlyRecipe;
}

public static String expensiveRecipe(Map<String, Set<String>> recipes, 
																		 Map<String, Integer> prices) {
		if (recipes.isEmpty()) {
		    throw new IllegalArgumentException();
    }

		Set<String> recipeNames = new TreeSet<>();
    recipeNames.addAll(recipes.keySet());

    String costlyRecipeName = null;
    int costlyRecipePrice = 0; 
    for (String recipe : recipeNames) {
        int price = 0;
        for (String ingredient : recipes.get(recipe)) {
            if (prices.containsKey(ingredient) {
	              price += prices.get(ingredient);
            }
        }

        if (costlyRecipeName == null || price > costlyRecipePrice) {
            costlyRecipeName = recipe;
            costlyRecipePrice = price;
        }
    }
    return cheapestRecipe;
}

6. Stacks and Queues

One possible solution is shown below

public Stack<Integer> splice(Stack<Integer> s, int start, int stop) {
    if (i < 0 || i > j || j > s.size()) {
        throw new IllegalArgumentException();
    }
    Stack<Integer> s2 = new Stack<>();
    Queue<Integer> q = new LinkedList<>();
    
		s2q(s, q);
    q2s(q, s);
		s2q(s, q);

    int oldSize = q.size();
    for (int k = 0; k < oldSize; k++) {
        if (k < start || k >= stop) {
            s.push(q.remove());
        } else {
            s2.push(q.remove());
        }
    }
    return s2;
}