Friday, December 11, 2009

Final Test

145 Final Test

  1. (10%) Implement a method which takes as input two Strings and returns one String which is formed by interleaving the two arguments. Assume that the two input strings have the same length. For example, if given the input
    "abcde"
    "12345"
    
    then it should return a String with the value:
    "a1b2c3d4e5"
    
    Answer:
      /**
       * Interleaves the letters of first and second. Assumes that first and second have the same length.
       * @return the interleaved string
       */
      public static String interleave(String first, String second){
        String result = "";
        for (int i =0; i < first.length(); i++){
          result += first.substring(i, i+1) + second.substring(i,i+1);
        }
        return result;
      }
    

  2. (10%) Implement a method that takes an array of long values representing phone numbers and prints out how many of those phone numbers are in Columbia (803), Greenville (864), and Charleston (843). You must use a switch statement in your method.
    For example, if we call your method with the following array n as input:
    long[] n = {8031234567l, 8649878787l, 8031223456l, 8034543212l, 8642323214l, 8432341231l};
    
    you will print out:
    Columbia:3
    Greenville:2
    Charleston:1
    
    Answer:
      public static void countAreaCodes (long[] phoneNumber){
        int columbia = 0;
        int greenville = 0;
        int charleston = 0;
        for (int i =0; i < phoneNumber.length;i++){
          int areaCode = (int) (phoneNumber[i] / 10000000);
          switch (areaCode) {
          case 803: 
            columbia++;
            break; //Don't forget the breaks!
          case 864:
            greenville++;
            break;
          case 843:
            charleston++;
          }
        }
        System.out.println("Columbia:" + columbia);
        System.out.println("Greenville:" + greenville);
        System.out.println("Charleston:" + charleston);
      }
    

  3. (10%) What does the following program print out?
    public class Enigma {
      
      private static int x;
      
      protected String s; 
      
      public Enigma(int x, String s){
        System.out.println("Creating an Engima");
        this.x = x;
        this.s = s;
      }
      
      public void addItUp(int z){
        x = x + z;
      }
      
      public void merge(Enigma e){
        s = s + "+" +  e.s;
      }
      
      public String toString(){
        return "s=" + s + " x=" + Integer.toString(x);
      }
    
    }
    
    public class Mystery extends Enigma {
      
      private int y;
      
      public Mystery (int x, int y, String s){
        super(x,s);
        System.out.println("Creating a Mystery");
        this.y = y;
      }
      
      public void addItUp(int z){
        y = y + z;
      }
      
      public String toString(){
        return super.toString() + " y=" + Integer.toString(y);
        
      }
      
    }
    
    public class Paradox extends Mystery {
    
      public Paradox(int x, int y, String s) {
        super(x, y, s);
        System.out.println("Creating a Paradox");
      }
      
      public void merge (Paradox p){
        s = "Do not cross the paradoxes!";
      }
    }
    
    public class Main {
    
      public static void main(String[] args) {
        Paradox p = new Paradox (5,10,"This sentence is false");
        Enigma e = new Enigma(33, "Black hole");
        System.out.println(p);
        System.out.println(e);
        e.merge(p);
        System.out.println(e);
        p.merge(p);
        System.out.println(p);
        e.merge(p);
        System.out.println(e);
        p.addItUp(100);
        System.out.println(p);
        Enigma e2 = (Enigma)p;
        e2.addItUp(500);
        System.out.println(e2);
      }
    }
    
    Answer:
    Creating an Engima
    Creating a Mystery
    Creating a Paradox
    Creating an Engima
    s=This sentence is false x=33 y=10
    s=Black hole x=33
    s=Black hole+This sentence is false x=33
    s=Do not cross the paradoxes! x=33 y=10
    s=Black hole+This sentence is false+Do not cross the paradoxes! x=33
    s=Do not cross the paradoxes! x=33 y=110
    s=Do not cross the paradoxes! x=33 y=610
    

  4. (10%) A diagonal matrix is a 2-dimensional square array of integers where the numbers on the diagonal are all 1 and the rest are 0. For example, the following is a 1x1 diagonal matrix:
    1
    
    and this is a 4x4 diagonal matrix:
    1 0 0 0
    0 1 0 0
    0 0 1 0
    0 0 0 1
    
    Implement a method that takes an integer n and returns an n x n array of integers that is a diagonal matrix.
    Answer:
      public static int[][] makeDiagonalMatrix (int size){
        int [][] result = new int[size][size];
        for (int i = 0; i<size; i++ ){
          result[i][i] = 1;
        }
        return result;
      }
    



  5. (10%) Implement a class called Tracker which keeps track (in variables) of
    1. how many times each instance's toString() method has been called
    2. the total number of times all instances of the class have had their toString() invoked.



    Answer:
    public class Tracker {
      
      private static int totalCount = 0;
      
      private int count;
      
      public Tracker(){
        count = 0;
      }
      
      public String toString() {
        count++;
        totalCount++;
        
        return "";
      }
    }
    

  6. (10%) Implement an Exception called SilentException such that a we do not have to place within a try.catch block a method that throws SilentException.


    Answer:
    public class SilentException extends RuntimeException {
    }
    

  7. (10%) Implement a method that calculates the shipping and handling costs of an Order, which has methods (these exists, you don't have to write them):
    1. boolean oversized(): returns true if this order is for an oversized item.
    2. CARRIER getCarrier(): where CARRIER is defined as enum CARRIER {UPS, FEDEX, USPS}, returns the carrier. (A carrier is a company that ships packages. UPS, FEDEX, and USPS are the names of three different carrier companies.)
    3. boolean rush(): return true if this a rush order.
    The method you will implement is called double getShippingCosts(Order o) and it will calculate the the shipping and handling costs. The shipping costs for the different carries are given in this table:



    UPS
    FEDEX
    USPS
    Regular
    $10
    $12
    $9
    Oversized
    $15
    $22
    $9


    The is also a standard handling fee of $4 for all packages. Also, if it is a rush order then you must add an extra 10% to the regular shipping costs.


    Answer:
      public static double getShippingCosts(Order o){
        double basePrice = 0;
        switch (o.getCarrier()) {
        case UPS:
          if (o.oversized())
            basePrice = 15;
          else 
            basePrice = 10;
          break;
        case FEDEX:
          if (o.oversized())
            basePrice = 22;
          else
            basePrice = 11;
          break;
        case USPS:
          basePrice = 9;
        }
        if (o.rush())
          basePrice = basePrice * 1.10;
        basePrice += 4;
        return basePrice;
      }
    

  8. (15%) Implement a method that takes a String input which represents a DNA sequence and returns the index of the start of longest string of 'A' letters in the sequence. If there are no A's then return -1. For example,

    given input "ACTAAAGA" you return 3,
    given input "AAAAGA" you return 0,
    given input "CTGATTAAAA" you return 6,
    given input "CTG" you return -1


    Answer:
      /**
       * This solution is good enough for 145*/
      public static int longestRepeatA(String dna){
    
        int longestIndex = -1;
        int longestCount = 0;
        for (int i =0; i < dna.length(); i++){
          int lengthA = 0;
          while (i + lengthA < dna.length() && dna.charAt(i+lengthA) == 'A'){
            lengthA++;
          };
          if (lengthA > longestCount){
            longestCount = lengthA;
            longestIndex = i;
          }
        }
        return longestIndex;
      }
    
      /** More experienced developers realize that the above is O(N^2) and that 
       * there is a way to implement it in linear time, like this: */ 
      public static int longestRepeatB(String dna){
        int longestIndex = -1;
        int longestCount = 0;
        int count = 0;
        for (int i = 0; i < dna.length(); i++){
          if (dna.charAt(i) == 'A') {
            count++;
          }
          if (count > longestCount) {
            longestCount = count;
            longestIndex = i - count + 1;
          }
          if (dna.charAt(i) != 'A'){
            count = 0;
          }
        }
        return longestIndex;
      }
    

  9. (15%) Implement a method that calculates the average of an array of grades after first dropping the lowest 4 grades. That is, implement:
    double getAverageDropFourLowest(double [] grade)
    
    Assume that grades.length >= 5. For example, when given
    double[] grade = {100,0,0,0,5,80,90};
    
    as input, your method should return
    90.0
    Alert: Notice that this has to work when the lowest grades match, like in the example above where 3 of them where 0.


    Answer:
      /** Returns an an array identical to grades but without the lowest number in grades dropped.
       * if there are more than one minimum we only drop the first one.
       * @param gradesthe array of grades
       * @return a new array of size 1 less than grades.
       */
      public static double[] dropMin(double [] grade){
        double minval = grade[0];
        double[] result = new double[grade.length - 1];
        for (double i : grade){
          if (i < minval)
            minval = i;
        }
        int j = 0; //index into result
        for (int i = 0; i < grade.length; i++){
          if (j < i){ //already dropped min, so just copy the rest of the array
            result[j++] = grade[i];
          }
          else if (grade[i] > minval) { //not the min
            result[j++] = grade[i];
          }
          //if j==i and grades[i] == minval we do nothing, so i increases while j stays the same, 
          // thus ignoring this grade[i]        
        }
        return result;
      }
      
      /** Returns the average after dropping the lowest 2 grades. */  
      public static double getAverageDropFourLowest(double [] grades){
        double[] g = FinalTest.dropMin(grades);
        g = FinalTest.dropMin(g);
        g = FinalTest.dropMin(g);
        g = FinalTest.dropMin(g);
        
        double sum = 0;
        for (double i : g){
          sum += i;
        }
        return sum / (double) g.length;
        
      }
      
    

No comments: