Session 1 - Solutions

Collatz.java

/**
 * Created by <a href="mailto:[email protected]">Marcus Gabilheri</a>
 *
 * @author Marcus Gabilheri
 * @version 1.0
 * @since 3/16/15
 */
public class Collatz {
    // Consider a sequence of positive integers starting with x.If x is
    // even,the next integer in the sequence is x/2.If x is odd, the
    // next integer in the sequence is 3 * x + 1. The sequence stops when it
    // reaches 1.
    //
    // For example, if x is 7, the sequence is
    //
    // 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
    //
    // Fill in the function loopCount so that it returns the length of
    // the sequence starting from x.
    static int loopCount(int x) {
        //STUDENTS: FILL IN CODE HERE!
        int count = 1;

        while(x != 1) {
            if(x % 2 == 0) {
                x = x / 2;
            } else {
                x = 3 * x + 1;
            }
            count++;
        }

        return count; // Add one to account for the "one" value at the end
    }

    // Using loopCount, fill in the function maxLoop so that it returns
    // the maximum sequence length for any sequence that starts with a
    // number greater than or equal to x and less than y.
    static int maxLoop(int x, int y) {
        //STUDENTS: FILL IN CODE HERE!
        int maxCount = loopCount(x);

        for(int i = x + 1; i < y; i++) {
            int t = loopCount(i);
            maxCount = maxCount > t ? maxCount : t;
        }

        return maxCount;
    }

    public static void main(String[] args) {
        //TODO add more tests
        System.out.println("The count for 7 is: " + loopCount(7));
        System.out.println(maxLoop(1, 100000));
    }
}

Filter.java

import java.util.ArrayList;
import java.util.List;

/**
 * Created by <a href="mailto:[email protected]">Marcus Gabilheri</a>
 *
 * @author Marcus Gabilheri
 * @version 1.0
 * @since 3/16/15
 */
public class Filter {
    // Write a function named "evens" that takes as input an array of
    // ints and returns a different array of ints containing
    // only the even elements of the input.

    public static int[] evens(int[] input) {
        // Here are some reminders:
        //
        // You can find input's length using input.length.
        // You can find the remainder of a division using %. For instance,
        // 11 % 3 ⇒ 2
        // 25 % 4 ⇒ 1
        //
        // You can declare a new array of integers with the syntax:
        // int[]var_name = new int[n];
        //
        // For example:
        // int[] clown = new int[10]; //creates an array named clown of 10 integers(clown[0] through clown[9])
        //
        //STUDENTS,WRITE CODE HERE.

        List<Integer> evenNums = new ArrayList<Integer>();

        for(int i : input) {
            if(i % 2 == 0) evenNums.add(i);
        }

        return convertListToArray(evenNums);
    }

    static int[] convertListToArray(List<Integer> list) {
        int len = list.size();
        int[] arr = new int[len];
        for(int i = 0; i < len; i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }

    public static void main(String[] args) { //
        // Expected output:
        // test1 results:
        // 8
        // 6
        // 0
        // test2 results:
        // 2
        // 18
        // 28
        // 18
        // 28
        // 90
        // //STUDENTS, ADD ADDITIONAL TEST CASES BELOW
        int[] test1 = {8, 6, 7, 5, 3, 0, 9};
        int[] ans = evens(test1);
        System.out.println("test1 results:");
        for (int i = 0; i < ans.length; ++i) {
            System.out.println(ans[i]);
        }
        int[] test2 = {2, 7, 18, 28, 18, 28, 45, 90, 45};
        ans = evens(test2);
        System.out.println("test 2 results:");
        for (int i = 0; i < ans.length; ++i) {
            System.out.println(ans[i]);
        }
    }
}

SparseMatrix.java

/**
 * Created by <a href="mailto:[email protected]">Marcus Gabilheri</a>
 *
 * @author Marcus Gabilheri
 * @version 1.0
 * @since 3/16/15
 */
public class SparseMatrix {

    static void outputNonZero(int[][] matrix) {
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[i].length; j++) {
                if(matrix[i][j] != 0) System.out.printf("[%d, %d]: %d\n", i, j, matrix[i][j]);
            }
        }
    }

    static void printMatrix(int[][] matrix) {
        for(int i = 0; i < matrix.length; i++) {
            System.out.print("[");
            for(int j = 0; j < matrix[i].length; j++) {
                System.out.printf("%3d", matrix[i][j]);
            }
            System.out.println(" ]");
        }
    }

    public static void main(String[] args) {
        int[][] matrix = new int[3][4];
        //TODO add more tests
        matrix[1][1] = 6;
        matrix[2][0] = 8;
        matrix[2][3] = 4;
        printMatrix(matrix);
        outputNonZero(matrix);
    }
}

Zip.java

/**
 * Created by <a href="mailto:[email protected]">Marcus Gabilheri</a>
 *
 * @author Marcus Gabilheri
 * @version 1.0
 * @since 3/16/15
 */
public class Zip {

    // Fill in the method "join". It returns a boolean array. The ith
    // value is that array(i.e.,array[i]) should be true if the ith
    // value in the first argument to join is divisible by the ith value
    // in the second argument to join. The returned boolean array should
    // be exactly as long as the shorter of the two arguments.
    //
    // Reminders:
    //
    // 1.An integer p is said to be "divisible by" an integer q when there
    // is some integer k such that q * k = p. This is the same as saying
    // "the remainder of p when divided by q is 0".
    // The remainder operator in Java is written with a percent sign:
    // "a%b" is the remainder of a when divided by b.
    //
    // 2.The length of an array bar is stored in bar.length.
    //
    // 3.New arrays are declared with the syntax:
    // float[]foo = new float[8];
    //

    static boolean[] join(int[] y, int[] z) {
        //STUDENTS: WRITE YOUR CODE HERE!
        int len = y.length  < z.length ? y.length : z.length;

        boolean[] jointArr = new boolean[len];

        for(int i = 0; i < len; i++) {
            try {
                jointArr[i] = y[i] % z[i] == 0;
            } catch (ArithmeticException ex) {
                jointArr[i] = false;
            }

        }
        return jointArr;
    }

    public static void main(String[] args) {

        //Expected output:
        // false
        // false
        // false
        // false
        // true
        // false
        // true
        //

        //STUDENTS, ADD ADDITIONAL TEST CASES BELOW

        int euler[] = {2, 7, 18, 28, 18, 28, 45, 90, 45};

        int jenny[] = {8, 6, 7, 5, 3, 0, 9};

        boolean divisibles[] = join(euler, jenny);

        for (int i = 0; i < divisibles.length; ++i) {

            System.out.println(divisibles[i]);

        }

    }
}

Looks pretty good; a few comments, though.

1. Filter.java; it seems a bit redundant to import ArrayList, convert a new ArrayList into a List and then write a helper to convert a List back into an array. Just use an ArrayList the entire time and call ArrayList.toArray() at the end.
2. Zip.java:32, I love the ternary operator, too, but just use Math.min if your goal is to find the minimum of two numbers. Same for Collatz.java:46, but with Math.max.
3. Zip.java:37-41, drop the exception and just say what you mean. It's clear that the only way modulo arithmetic can throw an exception is if the dividend is zero, so just add a case for that and a explanatory comment.

To be clear, I'm suggesting that block become

// Make sure not to divide by zero.
if (z[i] == 0) {
    jointArr[i] = false;
    continue;
}
jointArr[i] = (y[i] % z[i] == 0);

1. Nitpick: be consistent with your formatting. At Filter.java:35 and SparseMatrix.java:13 you elect to use a single line if statement and block. Since this is a single line if statement, the for statement could also be single line as well. Choose one. For readability, I like the Google Java coding guidelines of Use braces even when they are optional.

Thanks for the comments. Here is my reasons of why I made those choices.

• I don't think there's any penalty conversion on using List to declare an Array and I just got used of using List for many method just because of the flexibility of converting to another type of List such a LinkedList more info in this stack overflow post.
  As for writing a helper is because the toArray() method would return a Object[] forcing me to have a Integer[] rather than a int[].
• The choice of using a ternary over Math.min() is because the actual implementation of Math.min() in Java is exactly what I had. Same for Math.max

// Math.min implementantion
    /**
     * Returns the most negative (closest to negative infinity) of the two
     * arguments.
     */
    public static int min(int i1, int i2) {
        return i1 < i2 ? i1 : i2;
    }

• As for the exception It's mainly because I like using exceptions in general.