Key to CSE143 Midterm, Summer 2022

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

2. One possible solution appears below.

    public boolean startsWith(String s1, String s2) {
        if (s2.length() == 0) {
            return true;
        } else if (s1.length() == 0) {
            return false;
        } else {
            return s1.charAt(0) == s2.charAt(0) &&
                startsWith(s1.substring(1), s2.substring(1));
        }
    }

3. One possible solution appears below.

    public Map<Integer, Integer> convert(List<Integer> data) {
        if (data.isEmpty()) {
            throw new IllegalArgumentException();
        }
        Map<Integer, Integer> result = new TreeMap<>();
        for (int i = 0; i < data.size(); i++) {
            if (data.get(i) != 0) {
                result.put(i, data.get(i));
            }
        }
        return result;
    }

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

5. One possible solution appears below.

    public void removeLast(int n) {
        int index = -1;
        for (int i = 0; i < size; i++) {
            if (elementData[i] == n) {
                index = i;
            }
        }
        if (index != -1) {
            for (int j = index; j < size - 1; j++) {
                elementData[j] = elementData[j + 1];
            }
            size--;
        }
    }

6. One possible solution appears below.

    public static void splitStack(Stack<Integer> s) {
        Queue<Integer> q = new LinkedList<>();
        while (!s.isEmpty()) {
            q.add(s.pop());
        }
        int oldSize = q.size();
        for (int i = 0; i < oldSize; i++) {
            int n = q.remove();
            if (n % 2 == 0) {
                q.add(n);
            } else {
                s.push(n);
            }
        }
        while (!q.isEmpty()) {
            s.push(q.remove());
        }
        while (!s.isEmpty()) {
            q.add(s.pop());
        }
        while (!q.isEmpty()) {
            s.push(q.remove());
        }
    }