Spring 2021 [Bono]

CS 455 Midterm 2 Solution

Q1 (Student statement agreement)


Q2.1 

0 1 1 2 2 3

Q2.2 

1 2 3 4 5 6 <-- top

Q3 The only true statement is: 
mySet.contains(s);


Q4

A. O(1)
B. O(n)
C. O(n)
D. O(n)
E. O(1)
F. O(1)
G. O(1)


Q5.1 BookshelfKeeperProg

Q5.2 Bookshelf

Q5.3 none

Q5.4 BookshelfKeeperProg, BookshelfKeeper

Q5.5 BookshelfKeeper

Q5.6 BookshelfKeeperProg

Q5.7 BookshelfKeeperProg, BookshelfKeeper

Q5.8 BookshelfKeeper

Q5.9 BookshelfKeeperProg

Q5.10 BookshelfKeeper

Q5.11 BookshelfKeeperProg


Q6 

public static void sortByArea(ArrayList<Rectangle> boxes) {
   Collections.sort(boxes, new AreaComp());
   // OR:  boxes.sort(new AreaComp());
}


class AreaComp implements Comparator<Rectangle> {
   public int compare(Rectangle r1, Rectangle r2) {
      int r1Area = (int) (r1.getWidth() * r1.getHeight());
      int r2Area = (int) (r2.getWidth() * r2.getHeight());
      return r2Area - r1Area;
}


Q7.1 Liu, Min, Umesh, Peng

Q7.2 Liu, Izzy

Q7.3 Liu, Min


Q8

Solution 1 (most common solution) 

public static Map<String, Boolean> wordsMoreThanOnce(ArrayList<String> words) {

   Map<String, Boolean> result = new HashMap<>();
   for(String word: words) {
      if(result.containsKey(word)) {
         result.put(word, true);
      }
      else {
         result.put(word, false);
      }
   }
   return result;
}

Solution 2 (clever shorter solution given by a few students) 
public static Map<String, Boolean> wordsMoreThanOnce(ArrayList<String> words) {
    
   Map<String, Boolean> result = new HashMap<>();
   for (String str : words) {
      result.put(str, result.containsKey(str));
   }
   return result;

}


Q9
These were the two most common approaches. They are both tail-recursive.

Solution with 3-parameter helper (visits Right to Left)
This one can return as soon as we see the first instance of target. 

public static int findLast(int[] nums, int target) {
   return findLastH(nums, nums.length-1, target);
}

// findLastH: returns the index of the last instance of target found in the subarray
// from the start of nums to loc, or returns -1 if target not found in this subarray  
// PRE: loc is in range [-1, nums.length-1]
private static int findLastH(int[] nums, int loc, int target){

   if ((loc == -1) || (nums[loc] == target)) {    // short-circuit or
      return loc;
   }

   return findLastH(nums, loc - 1, target);
}

Solution with 4-parameter helper (visits Left to Right)
This one has to traverse all the way to the end every time. It saves the last position of target found so far (result var below), updates it when we find target at a later location, and returns it when we get to the end of nums 
public static int findLast(int[] nums, int target) {
   return findLastH(nums, target, 0, -1);
}

// findLastH: returns the index of the last instance of target found in the subarray
// from position loc to the end of nums, or returns result if target is not found in this subarray
// PRE: loc is in the range [0, nums.length]
private static int findLastH(int[] nums, int loc, int target, int result) {

   if (loc == nums.length) {
      return result;
   }

   if (nums[loc] == target) {
      result = loc;
   }

   return findLastH(nums, loc + 1, target, result);
}