Q2.1
0 1 1 2 2 3
1 2 3 4 5 6 <-- top
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; }
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); }
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); }