Key to CSE143 Midterm, Summer 2018

1.      Method Call                      Output Produced
        ------------------------------------------------
        mystery(0, 90);                  !
        mystery(12, 2);                  *!
        mystery(12, 22);                 !*!
        mystery(555, 666);               !***
        mystery(582, 1522);              *!*!

2. One possible solution appears below.

    public static String pattern(int n, int m) {
        if (n < 0 || m < 0) {
            throw new IllegalArgumentException();
        }
        if (n == 0 && m == 0) {
            return "";
        } else if (n == 0) {
            return "." + pattern(0, m - 1);
        } else {
            return "[" + pattern(n - 1, m) + "]";
        }
    }

3.  One possible solution appears below.

    public Map<String, List<String>> commonHobbies(Map<String, 
                                                       List<String>> tas) {
        Map<String, List<String>> result = new TreeMap<String, List<String>>();
        for (String ta : tas.keySet()) {
            for (String hobby : tas.get(ta)) {
                if (!result.containsKey(hobby)) {
                    result.put(hobby, new ArrayList<String>());
                }
                result.get(hobby).add(ta);
            }
        }
        return result;
    }

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

5. One possible solution appears below.

    public ArrayIntList makePalindrome() {
        ArrayIntList other = new ArrayIntList();
        int shift = size % 2;
        for (int i = 0; i < size; i++) {
            other.elementData[i] = elementData[i];
        }
        for (int i = 0; i < size - shift; i++) {
            other.elementData[size + i] = elementData[size - i - 1 - shift];
        }
        other.size = size * 2 - shift;
        return other;
    }

6. One possible solution appears below.

    public Stack<Integer> spliceStack(Stack<Integer> s, int i, int j) {
        if (i < 0 || i > j || j > s.size()) {
            throw new IllegalArgumentException();
        }
        Stack<Integer> s2 = new Stack<Integer>();
        Queue<Integer> q = new LinkedList<Integer>();
        while (!s.isEmpty()) {
            q.add(s.pop());
        }
        while (!q.isEmpty()) {
            s.push(q.remove());
        }
        while (!s.isEmpty()) {
            q.add(s.pop());
        }
        int oldSize = q.size();
        for (int k = 0; k < oldSize; k++) {
            if (k < i || k >= j) {
                s.push(q.remove());
            } else {
                s2.push(q.remove());
            }
        }
        return s2;
    }