Key to CSE143 Midterm, Winter 2019

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 void printSequence(int n) {
        if (n < 1) {
            throw new IllegalArgumentException();
        }
        if (n == 1) {
            System.out.print("*");
        } else if (n == 2) {
            System.out.print("**");
        } else if (n % 4 == 0 || n % 4 == 3) {
            System.out.print("<");
            printSequence(n - 2);
            System.out.print(">");
        } else {
            System.out.print(">");
            printSequence(n - 2);
            System.out.print("<");
        }
    }

3.  One possible solution appears below.

   public static String mostCredits(Map<String, Set<String>> enrollments, Map<String, Integer> credits) {
       Map<String, Integer> counts = new TreeMap<>();
       for (String student : enrollments.keySet()) {
           Set<String> courses = enrollments.get(student);

           int count = 0;
           for (String course : courses) {
               count += credits.get(courses);
           }

           counts.put(student, count);.
       }

       String maxStudent = null;
       int maxCount = -1;
       for (String student : counts.keySet()) {
           if (counts.get(student) > maxCount) {
               maxStudent = student;
               maxCount = counts.get(student);
           }
       }
       return maxStudent;
   }

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


5. One possible solution appears below.

    public static void separate(Queue<String> q) {
        Stack<String> s = new Stack<String>();
        int size = q.size();
        // Move length 1 to stack
        for (int i = 0; i < size; i++) {
            String str = q.remove();
            if (str.length() == 1) {
                s.push(str);
            } else {
                q.add(str);
            }
        }
        size = q.size();
        // Move length 2 to stack
        for (int i = 0; i < size; i++) {
            String str = q.remove();
            if (str.length() == 2) {
                s.push(str);
            } else {
                q.add(str);
            }
        }
        // Move length 3 (the rest) to stack
        q2s(q, s);
        // Reverse contents of everything
        s2q(s, q);
        q2s(q, s);
        s2q(s, q);
    }

6. One possible solution appears below.

    public void repeat() {
        for (int i = size - 1; i >= 0; i--) {
            elementData[i * 2] = elementData[i];
            elementData[i * 2 + 1] = elementData[i];
        }
        size *= 2;
    }