Sorting Test

  1. Suppose that I have a String[] containing names of candidates that voters voted for. So, for example, my list might look like this:

    ["Bush", "Bush", "Kerry", "Bush", "Kerry", "Kerry", "Bush"]

    Assume that one of the candidates received a majority of the votes. I can find out what candidate that is, as follows:Fill in the method below to return the name of the winner.

    public String majority(String[] votes) {
       
       
       
       
       
       
       
       
       
       
       
       
       
       
    }



  2. The sort below should hopefully be recognizable to you as a mergesort. But somehow, it works without needing two lists. Explain how it works.

    public void sort(Sortable[] list) {
       for(int size = 1; size < list.length; size *= 2) {
          for(int i = 0; i < list.length; i += 2*size) {
             merge(list, i, i + size, i + 2*size);
          }
       }
    }

    public void merge(Sortable[] list, int left, int right, int end) {
       while(left < right && right < end) {
          if(list[right].compareTo(list[left]) < 0) {
             Sortable moving = list[right];
             for(int i = right; i > left; i--) {
                list[i] = list[i - 1];
             }
             list[left] = moving;
             right++;
          }
          left++;
       }
    }








  3. I have three search methods that have orders O(N²), O(log N), and O(√N), respectively. They all take the same amount of time - one minute - to sort 100 items. How long will each take to search 1,000,000 items?

    (You can answer in minutes, even though some of your answers will be big enough to be measured in years)





  4. Suppose that you have an array of ints that are sorted, and you want to determine whether there is a pair of them that adds up to a given number. So, for example, if my list were this:

    2 5 9 17 22 41

    ... then I would return true if you asked if I can add up to 26 (because I could add 9 and 17) but false if you asked if I could add up to 20. You may add a number to itself - so, for example, I would return true for 34 in the list above because I can add 17 and 17 to get 34. You must add exactly two numbers - so, for example, I would return false for 17 (even though it is in the list) or for 15 (5 + 5 + 5).

    Fill in the method below.
    Challenge: Do it in a way that is O(n).

    public boolean canAdd(int[] list, int sum) {
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
    }

  5. One common task you need to do with arrays is to join two arrays into a single, new array. So, for example:

    join([2, 5, 7], [1, 9, 3]) &RArr; [2, 5, 7, 1, 9, 3]

    For each of the versions of the join() method below, tell me if it does its task properly.

    public Object[] join(Object[] start, Object[] end) {
       Object[] join = new Object[start.length + end.length];
       for(int i = 0; i < start.length; i++) {
          join[i] = start[i];
       }
       for(int i = 0; i < end.length; i++) {
          join[i + start.length] = end[i];
       }
       return join;
    }

    public Object[] join(Object[] start, Object[] end) {
       Object[] join = new Object[start.length + end.length];
       for(int i = 0; i < join.length; i++) {
          if(i < start.length) {
             join[i] = start[i];
          } else {
             join[i] = end[i - start.length];
          }
       }
       return join;
    }

    public Object[] join(Object[] start, Object[] end) {
       Object[] join = new Object[start.length + end.length];
       int i = 0;
       int j = join.length - 1;
       for(int i = 0; i < join.length / 2; i++) {
          join[i] = start[i];
          join[join.length - 1 - i] = end(end.length - i);
       }
       return join;
    }