Key to CSE143 Midterm, Autumn 2018

1.      Method Call                      Output Produced
        ------------------------------------------------
        mystery(7);                      7
        mystery(38);	                 838
        mystery(194);	                 49194
        mystery(782);	                 28782
        mystery(3842);	                 2483842

2. Three possible solution appears below.

    public static boolean sameDashes(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() != s2.length())
            throw new IllegalArgumentException();
        if (s1.length() == 0) {
            return true;
        }
        if (s1.charAt(0) == '-' && s2.charAt(0) != '-') {
            return false;
        }
        if (s2.charAt(0) == '-' && s1.charAt(0) != '-') {
            return false;
        }
        return sameDashes(s1.substring(1), s2.substring(1));
    }

    public static boolean sameDashes(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() != s2.length())
            throw new IllegalArgumentException();
        if (!s1.contains("-") && !s2.contains("-")) {
            return true;
        } else {
            return (s1.substring(0, 1).equals("-") && s2.substring(0, 1).equals("-") ||
                    !s1.substring(0, 1).equals("-") && !s2.substring(0, 1).equals("-")) &&
                    sameDashes(s1.substring(1), s2.substring(1));
        }
    }

    public static boolean sameDashes(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() != s2.length())
            throw new IllegalArgumentException();
        int index1 = s1.indexOf("-");
        int index2 = s2.indexOf("-");
        if (index1 == index2) {
            if (index1 == -1) {
                return true;
            }
            return sameDashes(s1.substring(index1 + 1), s2.substring(index2 + 1));
        }
        return false;
    }

3.  One possible solution appears below.

     public Map<String, Integer> computeTotalCredits(Map<String, Set<String>> enrollments,
                                                     Map<String, Integer> credits) {
         Map<String, Integer> result = new TreeMap<String, Integer>();

         for (String student : enrollments.keySet()) {
             int total = 0;
             for (String course : enrollments.get(student)) {
                 total += credits.get(course);
             }
             result.put(student, total);
         }

         return result;
     }

4.      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->[2]                | q                     | q = null;
-----------------------+-----------------------+-------------------------------
 p->[1]->[2]           | p->[2]->[4]           | p.next.next = q.next;
                       |                       | q.next = p;
 q->[3]->[4]           | q->[3]->[1]           | p = p.next;
                       |                       | q.next.next = null;
-----------------------+-----------------------+-------------------------------
 p->[1]->[2]->[3]      | p->[2]->[1]->[4]      | p.next.next.next = q.next;
                       |                       | ListNode temp = q;
 q->[4]->[5]           | q->[3]->[5]           | 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 sortPairsSolution(Stack<Integer> s) {
       Queue<Integer> q = new LinkedList<Integer>();
       s2q(s, q);
       q2s(q, s);

       while (s.size() >= 2) {
           int n1 = s.pop();
           int n2 = s.pop();
           int min = Math.min(n1, n2);
           int max = Math.max(n1, n2);

           q.add(min);
           q.add(max);
       }

       if (!s.isEmpty()) {
           q.add(s.pop());
       }
       q2s(q,s);

    }

6. One possible solution appears below.

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