Key to CSE143 Sample Midterm, Winter 2019 1. Method Call Value Returned ----------------------------------------------- mystery(42, 0) 0 mystery(5, 25) 1 mystery(752, 792) 2 mystery(3092, 5028) 1 mystery(61903, 1930) 2 2. One possible solution appears below. public String groupChars(String s) { if (s.length() == 0) { return "*"; } else if (s.length() < 3) { return "[" + s + "]"; } else { int last = s.length() - 1; return "(" + s.charAt(0) + groupChars(s.substring(1, last)) + s.charAt(last) + ")"; } } 3. before after code -----------------------+-----------------------+------------------------------- p->[1]->[2] | p->[1] | q.next = p.next; | | p.next = null; q->[3] | q->[3]->[2] | -----------------------+-----------------------+------------------------------- p | p->[1] | p = q; | | q = q.next; q->[1]->[2]->[3] | q->[2]->[3] | p.next = null; -----------------------+-----------------------+------------------------------- p->[1]->[2]->[3] | p->[3]->[1] | p.next.next.next = p; | | p = p.next.next; q->[4] | q->[2]->[4] | p.next.next.next = q; | | q = p.next.next; | | p.next.next = null; -----------------------+-----------------------+------------------------------- p->[1] | p->[5]->[1]->[3] | p.next = q.next; | | q.next.next.next.next = p; q->[2]->[3]->[4]->[5] | q->[4]->[2] | p = q.next.next.next; | | q.next.next.next = q; | | q = q.next.next; | | q.next.next = null; | | p.next.next.next = null; -----------------------+-----------------------+------------------------------- 4. One possible solution appears below. public Set cancelCourse(String course, Map> schedules) { Set affected = new TreeSet(); for (String student : schedules.keySet()) { Set courses = schedules.get(student); if (courses.contains(course)) { courses.remove(course); affected.add(student); } } return affected; } 5. One possible solution appears below. public static void mirrorCollapse(Stack s) { Queue q = new LinkedList(); while (!s.isEmpty()) { q.add(s.pop()); } int oldSize = q.size(); for (int i = 0; i < oldSize / 2; i++) { s.push(q.remove()); } if (oldSize % 2 == 1) { q.add(q.remove()); } while (!s.isEmpty()) { q.add(q.remove() + s.pop()); } while (!q.isEmpty()) { s.push(q.remove()); } } 6. One possible solution appears below. public ArrayIntList fromCounts() { ArrayIntList result = new ArrayIntList(); int size2 = 0; for (int i = 0; i < size; i += 2) { for (int j = 0; j < elementData[i]; j++) { result.elementData[size2] = elementData[i + 1]; size2++; } } result.size = size2; return result; }