NOTE: This page has sample standalone questions to test your knowledge of core concepts and facts. The exams will also test your knowledge of the homework. To prepare for those questions, practice doing (or redoing) the homework independently from scratch.

1. What is the value of i after this code runs?

   int i = 7 / 2;

2. What is the value of i after this code runs?

   int i = 7 % 2;

3. What is the value of i after this code runs?

   int i = 'C' - 'A';

4. What is the value of i after each line of this code runs?

   int i = 0; // 0
   ++i;       // ?
   i++;       // ?
   i *= 2;    // ?
   i %= 3;    // ?
   i /= i;    // ?

5. What is the value of b after this code runs?

   boolean b = (2 + 2 == 5);

6. What is the value of b after this code runs?

   boolean b = (2 + 2 == 5) || false;
   b = !b;

7. What is the value of b after this code runs?

   boolean b = ('f' >= 'a') && (2 + 2 == 4);
   b = b && b;

8. What is the value of string after this code runs?

   String string = "";
   for (int i = 0; i < 10; ++i) {
       if (i % 3 == 0) {
           string += i;
       }
   }

9. What does this code print?

   for (char c = 'a'; c <= 'f'; ++c) {
       System.out.print(c);
   }

10. Your friend tells you that in Java you can increment a double using either of the ++ operators. Write a small program that you can run to test whether your friend is telling the truth.

11. What does this code print?

    for (int i = 0; i < 10; ++i) {
        if (i == 3) {
            break;
        }
        System.out.println(i);
    }

12. What does this code print?

    for (int i = 0; i < 10; ++i) {
        if (i == 3) {
            continue;
        }
        System.out.println(i);
    }

13. Does this code compile? Why or why not?

    class Main {
        public static void main(String[] arguments) {
            {
                int a = 0;
            }
            System.out.println(a);
        }
    }

1. Write a function double sum(double[] array) { ... } that returns the sum of the elements in array.
2. Write a function int indexOfMaximumElement(double[] array) { ... } that returns the index of the maximum element in array.
   • Note: If array is empty (has length = 0), function should return -1.
   • Hint: Double.POSITIVE_INFINITY
3. Draw the contents of array after this code runs.

   int[] array = new int[5];
   for (int i = 0; i < 7; ++i) {
       array[i % array.length] = i;
   }

4. Write a function void reverseArrayInPlace(double[] array) { ... } which reverses array in-place using swaps.
5. Write a function double[] reverseArrayOutOfPlace(double[] array) { ... } which reverses array out-of-place by copying values into a new array. The input array must not be changed. The new (reversed) array is returned.
6. Write a function void bubbleSort(double[] array) { ... } which sorts array using bubble sort.
   • Hint: Bubble sort is an in-place algorithm; you will need to use swaps.

1. What will this code print?

   int foo = 1;
   int bar = foo;
   ++foo;
   System.out.println(bar);

2. What will this code print? Note: Don't worry about "(x, y)" versus "[x, y]"; just get the numbers right.

   Vector2 foo = new Vector2(0.0, 0.0);
   Vector2 bar = foo;
   foo.x = 1.0;
   System.out.println(bar);

1. What will this code print (do NOT include null's / "empty slots")? Note: Don't worry about "(a, b, c, ...)" versus "[a, b, c, ...]"; just get the elements right.

   ArrayList<Integer> foo = new ArrayList<>();
   foo.add(1);
   ArrayList<Integer> bar = foo;
   bar.add(2);
   System.out.println(bar);

2. Assume ArrayList's private array is initially [ null, null, null, null ] (capacity = 4) and its add(ElementType element) method doubles the length of the private array if there's no room to add element. Draw the contents of the private array (including null's / "empty slots") of the array list referenced by foo after this code runs.

   ArrayList<Integer> foo = new ArrayList<>();
   for (int i = 0; i < 9; ++i) {
       foo.add(i);
   }

1. What does this code print?

   Stack<Integer> stack = new Stack<>();
   stack.push(0);
   stack.push(1);
   stack.push(2);
   stack.pop();
   while (!stack.isEmpty()) {
       System.out.println(stack.pop());
   }

   👀

   1
   0
   

2. What does this code print?

   ArrayDeque<Integer> queue = new ArrayDeque<>();
   queue.add(0);
   queue.add(1);
   queue.add(2);
   queue.add(3);
   queue.add(queue.remove());
   while (!queue.isEmpty()) {
       System.out.println(queue.remove());
   }

   👀

   1
   2
   3
   0
   

1. What does this code print?

   HashMap<String, Integer> map = new HashMap<>();
   map.put("Hans", 4);
   map.put("Parrot", 6);
   map.put("Kahoot", 5);
   
   String[] array = { "Hans", "The", "Parrot"};
   
   int result = 0;
   for (int i = 0; i < array.length; ++i) {
       if (map.containsKey(array[i])) {
           result += map.get(array[i]);
       }
   }
   
   System.out.println(result);

   👀

   10
   

2. Here is a hashmap (hashtable) implementation very similar to what we did together in class. ⚠ It uses a custom hashing function.

   static class KeyValuePair {
       String key;
       Integer value;
       KeyValuePair(String key, int value) {
           this.key = key;
           this.value = value;
       }
       public String toString() {
           return key + "=" + value;
       }
   }
   
   static class ToyMap {
       // buckets is an array of ArrayList's of KeyValuePair's.
       // (A "bucket" is an ArrayList<KeyValuePair>.)
       // NOTE: There are 5 buckets in the buckets array.
       //       All buckets start out empty.
       ArrayList<KeyValuePair>[] buckets;
       ToyMap() {
           buckets = (ArrayList<KeyValuePair>[]) new ArrayList[5];
           for (int i = 0; i < buckets.length; ++i) {
               buckets[i] = new ArrayList<>();
           }
       }
   
       void put(String key, Integer value) {
           int bucketIndex = (key.charAt(0) - 'A') % buckets.length;
           ArrayList<KeyValuePair> bucket = buckets[bucketIndex];
           for (KeyValuePair pair : bucket) {
               // update corresponding value if map already contains key
               if (key.equals(pair.key)) {
                   pair.value = value;
                   return;
               }
           }
           bucket.add(new KeyValuePair(key, value));
       }
   }

   What does this code print?

   ToyMap map = new ToyMap();
   map.put("Apple", 1);
   map.put("Banana", 2);
   map.put("Fig", 3);
   map.put("Apple", 4);
   System.out.println(Arrays.toString(map.buckets));

   👀

   [[Apple=4, Fig=3], [Banana=2], [], [], []]
   

1. This problem uses the singly linked list from HW-08. What does this code print? ⚠ Careful, this problem is tricky. NOTE: Print works the same way as on the homework, for example, the list with elements 1, 2, and then 3 would print as 1 -> 2 -> 3.

   LinkedList list = new LinkedList();
   list.head = new Node(5);
   System.out.println(list); // ?
   list.head.next = new Node(6);
   System.out.println(list); // ?
   list.head.next = new Node(7);
   System.out.println(list); // ?
   list.head.next.next = new Node(8);
   System.out.println(list); // ?
   Node node = new Node(9);
   node.next = list.head;
   list.head = node;
   System.out.println(list); // ?

   👀

   5
   5 -> 6
   5 -> 7
   5 -> 7 -> 8
   9 -> 5 -> 7 -> 8
   

1. Consider the following binary tree.

         1
        / \
       /   \
      /     \ 
     2       3
    / \     / \ 
   4   5   6   7
   

   1. What is the order of nodes in a breadth-first (level (row)-order) traversal of this tree?
   2. What is the order of nodes in a pre-order (self, left, right) depth-first traversal of this tree?
   3. What is the order of nodes in a in-order (left, self, right) depth-first traversal of this tree?
   4. What is the order of nodes in a post-order (left, right, self) depth-first traversal of this tree?
   👀

   Breadth-First: 1, 2, 3, 4, 5, 6, 7
   Pre-Order:     1, 2, 4, 5, 3, 6, 7
   In-Order:      4, 2, 5, 1, 6, 3, 7
   Post-Order:    4, 5, 2, 6, 7, 3, 1
   

2. Which depth-first traversal order could be used to convert the following binary tree into the expression 4 + 5 * 6 - 7?

         *
        / \
       /   \
      /     \ 
     +       -
    / \     / \ 
   4   5   6   7
   

1. This problem uses the binary search tree from HW-10.What does this code print?

   BinarySearchTree binarySearchTree = new BinarySearchTree();
   int[] array = { 5, 2, 7, 8, 3, 9, 1, 6, 4 };
   for (int i = 0; i < array.length; ++i) {
       binarySearchTree.add(array[i]);
   }
   printBinaryTree(binarySearchTree.root);

   👀

                 5
                / \
               /   \
              /     \
             /       \
            /         \
           /           \
          /             \
         2               7
        / \             / \
       /   \           /   \
      /     \         /     \
     1       3       6       8
              \               \
               4               9

2. Here is a max binary heap. Draw its state after calling heap.remove().

         9
        / \
       /   \
      /     \ 
     8       5
    / \     / \ 
   2   3   4   1

   👀

         8
        / \
       /   \
      /     \ 
     3       5
    / \     / 
   2   1   4   

3. Here is a max binary heap. Draw its state after calling heap.add(2).

         6
        / \
       /   \
      /     \ 
     5       1
    / \
   4   3

   👀

         6
        / \
       /   \
      /     \ 
     5       2
    / \     /
   4   3   1

1. What is the big O runtime in terms of n? Why?

   int result = 0;
   for (int i = 0; i < n; ++i) {
       result += 1;
   }

   👀

   O(n); Adding two integers is a constant time operation; we do this O(n) times.

2. What is the big O runtime in terms of n? Why?

   String result = "";
   for (int i = 0; i < n; ++i) {
       result += "1";
   }

   👀

   O(n^2); Each += creates a new String of length O(n).

3. What is the big O runtime in terms of n? Why?

   String result = "asdf";
   for (int i = 0; i < n; ++i) {
       result += result;
   }

   👀

   O(2^n); The final += creates a new String of length O(2^n). (The strings before that are so much smaller that they don't actually change the big O runtime; O(2 * 2^n) = O(2^n)

4. What is the big O runtime of calling foo(n)? Why? NOTE: Assume n is positive.

   def void foo(int n){
       if (n > 0) {
           foo(n - 1);
       }
   }

   👀

   O(n); We make O(n) function calls (each function really just subtracts two numbers, which is a constant time operation).