Practice exam Spring 2016

exam.md

Please Read

These questions are representative of the ones that will be on the final exam. We will select around 10% to 20% of them for the exam. Note that we will possibly tweak the questions a little so some may not be not identical.

Here are the resources you should use for studying in addition to these sample questions:

The source code from the class demonstrations which you can find here: https://github.com/Cosi-12b

The complete set of slides from class: https://drive.google.com/a/brandeis.edu/folderview?id=0B2SSgva8RXyFNDdTY2hFeDNNRG8&usp=sharing

True / false

1. Abstract classes can have constructors
2. It is possible for an interface to have more than one constructor
3. It is possible for a class to have more than one constructor
4. int and Integer are both examples of primitive values
5. You can instantiate a new instance of an interface
6. Interfaces can extend other interfaces
7. An abstract class can implement more than one interface
8. A class can extend at most two other classes
9. A method that returns a value of type boolean must always return either true or false
10. A method that returns a value of type Integer must always return a valid number
11. In general, for loops should be preferred over while loops
12. An immutable object is an object that cannot be changed after it is created.
13. Abstract classes can have main methods.
14. A non-static variable is associated with the class as a whole rather than with specific instances of a class.
15. Non-static variables take on unique values with each object instance.
16. An object may implement multiple abstract classes
17. Object is the supertype of all classes
18. Three sequential for loops will always run faster than three nested for loops
19. A LinkedList has faster insertion time than an ArrayList
20. A LinkedList has faster access time for arbitrary indexes than an ArrayList

Data structures

You want to store information about ZIP codes in states. Specifically, you want to be able to lookup which state a particular ZIP code is in. Assume that ZIP codes are stored as integers, and that states are stored as Strings. Which data structure should you use?

1. List<String>
2. Map<String, Integer>
3. Map<Integer, String>
4. Set<Integer>

You want to store all the moves two players have currently made within a Chess game. Assume that a move is represented via the Move class. Which data structure should you use?

1. Move[]
2. Map<Integer, Move>
3. Set<Move>
4. List<Move>

You want to write code to figure out how many unique lines there are in a particular file. Which data structure should you use?

1. String[]
2. List<String>
3. Set<String>
4. Map<String, String>

You want to store information about ZIP codes and states. You want to be able to get all of the ZIP codes within a given state. Assume that ZIP codes are ints and states are Strings. Which data structure should you use?

1. Set<String>
2. Map<String, List<Integer>>
3. List<Map<String, Integer>>
4. Map<List<Integer>, String>

You want to store information about professors and departments. A department has multiple professors, and a professor may work in multiple departments. You want to be able to get all of the professors inside of a department. Assume that professors are represented by the Professor class and departments are represented by the Department class. Which data structure should you use?

1. Map<Department, Professor>
2. Map<Department, List<Professor>>
3. Map<List<Professor>, Department>
4. Map<Department, Set<Professor>>

Which of the following statements is false?

1. A Set is an interface
2. Proper implementations of Set cannot contain duplicates
3. A HashSet is an implementation of Set
4. One can assume that a Set's iterator will return items in some order

Which of the following statements is true?

1. A Map can have duplicate keys
2. A Map can map Strings to primitive types
3. A Map can have duplicate values
4. A Map does not have to have a proper ordering

You are designing an application to hold a list of orders for a particular product. You expect orders to be quickly added or canceled. Which class implementing List should you use to store the orders?

1. LinkedList<Order>
2. ArrayList<Order>
3. List<Order>
4. Stack<Order>

You are designing an application to hold a collection of documents, and each document has a sequential ID number starting from 0. You need to be able to retrieve an item based on its ID. Which data structure should you use?

1. LinkedList<Order>
2. HashSet<Order>
3. ArrayList<Order>
4. Deque<Order>

In designing a simple game, you want to keep track of a score count integer for each user, with all users identified by a unique username. Which of the following data structures would you use for keeping track of scores?

1. Map<String,Integer>
2. Map<Integer,String>
3. List<String>
4. Map<List<String>,Integer>

What is a binary search tree?

1. An acyclic binary tree, organized so that all the values contained in a left subtree are less than the values contained in the right subtree.
2. A Java built-in class used for storing binary data
3. None of the above

What is a stack?

1. A data structure that imlements a last-in first-out (LIFO) access pattern
2. A data structure that implements a first-in first-out (FIFO) access pattern
3. None of the above

What is a Queue?

1. A data structure that imlements a last-in first-out (LIFO) access pattern
2. A data structure that implements a first-in first-out (FIFO) access pattern
3. A data structure that allows an indefinite number of entries
4. A data structure for short-lived information

What is an ArrayList?

1. A list that contains arrays
2. A Java class that implements a variable length list
3. An array that contains lists
4. A Java collection that is used to store for very large multi dimenstional arrays efficiently.

Recursion

The following method below should calculate the number of times a character "x" appears in a string. Select the line that will make the program function correctly.

public int countX(String s) {
    if (s.length() == 0)
        return 0;

    if (s.charAt(0) == 'x')
        MISSING LINE

    return countX(s.substring(1));
}

1. return 1 + s.substring(1);
2. return countX(s.substring(1)) + 1;
3. return countX(s) + 1;
4. return countX(s.substring(1));

The following method should move all lowercase "x" characters to the end of the string, such that the string hxexllo becomes helloxx. Select the line that will make the program function correctly.

public String endX(String s) {
    if (s.length() == 0)
        return "";

    if (s.charAt(0) == 'x')
        return endX(s.substring(1)) + "x";

    MISSING LINE
}

1. return endX(s.substring(0, 1)) + s.substring(1);
2. return s.charAt(0) + endX(s.substring(1));
3. return endX(s.substring(1));
4. return s + endX(s.substring(1));

Consider the following method:

public static void mystery3(int n) {
  if (n <= 0) {
    System.out.print("*");
  } else if (n % 2 == 0) {
    System.out.print("("); mystery3(n - 1); System.out.print(")");
  } else {
    System.out.print("["); mystery3(n - 1); System.out.print("]");
  }
}

For each of the following calls, indicate the output that is produced by the method:

1. mystery3(0);
2. mystery3(1);
3. mystery3(2);
4. mystery3(4);
5. mystery3(5);

Consider the following method:

public static int mystery4(int x, int y) {
  if (x < y) {
    return x;
    } else {
  return mystery4(x - y, y);
  }
}

For each of the following calls, indicate the value that is returned:

1. mystery4(6, 13); :
2. mystery4(14, 10); :
3. mystery4(37, 10); :
4. mystery4(8, 2); :
5. mystery4(50, 7); :

True or false: any recursive algorithm can be rewritten as a non-recursive algorithm.

With Trees

Consider the following tree node class:

class TreeNode {
    private TreeNode left;
    private TreeNode right;
    private int value;

    public TreeNode(TreeNode left, TreeNode right, int value) {
        this.left = left;
        this.right = right;
        this.value = value;
    }


    public void print() {
        if (left != null) left.print();
        System.out.println(value);
        if (right != null) right.print();
    }
}

What is the output (newlines replaced with commas) of the following code?

TreeNode tn = new TreeNode(null, null, 3);
TreeNode tn1 = new TreeNode(null, null, 5);
TreeNode tn2 = new TreeNode(tn, tn1, 8);
TreeNode tn3 = new TreeNode(null, null, 10);
TreeNode tn4 = new TreeNode(tn2, tn3, 9);

tn4.print();

1. 3, 8, 5, 9, 10
2. 8, 3, 5, 9, 10
3. 5, 3, 8, 9, 10
4. 10, 9, 8, 5, 3

In the code below, the hasChild(int val) method is supposed to determine if a particular tree node has value == val or if any of its children have value = val. Select the correct code for the missing line.

class TreeNode {
    private TreeNode left;
    private TreeNode right;
    private int value;

    public TreeNode(TreeNode left, TreeNode right, int value) {
        this.left = left;
        this.right = right;
        this.value = value;
    }


    public boolean hasChild(int val) {
        if (value == val)
            return true;

        MISSING LINE

        return false;
        
    }

 
}

1. if (left.hasChild(val) == right.hasChild(val)) return true;
2. if (left.hasChild(val - 1) && right.hasChild(val + 1)) return true;
3. if (! (left.hasChild(val) || right.hasChild(val)) ) return false;
4. if (left.hasChild(val) || right.hasChild(val)) return true;

In the code below, the hasEvenOdd(int val) method is supposed to return true if every even node (a node with an even value) has only odd children and if every odd node (a node with an odd value) has only even children, and should return false otherwise. Select the correct missing line.

class TreeNode {
    private TreeNode left;
    private TreeNode right;
    private int value;

    public TreeNode(TreeNode left, TreeNode right, int value) {
        this.left = left;
        this.right = right;
        this.value = value;
    }


    public boolean isEvenOdd() {
        if (left != null && left.value % 2 == value % 2)
            return false;
        
        if (right != null && right.value % 2 == value % 2) 
            return false;
            
        MISSING LINE
    }
 
}

1. return ((left == null || left.isEvenOdd()) && (right == null || right.isEvenOdd()));
2. return ((left != null && left.isEvenOdd()) && (right != null && right.isEvenOdd()));
3. return (left != null || right != null) && (left.isEvenOdd() || right.isEvenOdd());
4. return left.value % 2 == right.value % 2;

A tree is balanced if the left and right subtrees' heights differ by at most one, and both the left and right subtrees are themselves balanced. For example, these three trees are balanced:

        a
     /    \ 
    b      f
  /  \    /  \  
 c    d  e    g

       a
     /   \ 
    b     f
  /  \   /  
 c    d  e

       a
     /   \ 
    f      b    
         /  \     
        c    d     

... but this tree is not:

        a
      /   \ 
     b     f
   /  \     
  c    d  
 /
e

Which statement is true?

1. It is easier to search an unbalanced binary tree because more values are concentrated in specific branches
2. It is easier to search a balanced binary tree because each decision eliminates more possibilities
3. It takes the same amount of time to search a tree regardless of if the tree is balanced or not
4. None of the above

Evaluation

What is the output of the following program, replacing newlines with commas?

class Test {
    public static boolean f1() {
        System.out.println("hello");
        return false;
    }

    public static boolean f2() {
        System.out.println("world");
        return true;
    }

    public static void main(String[] args) {
        System.out.println(f1() && f2());
    }
        
}

1. hello, true
2. hello, world, true
3. world, true
4. hello, false

What is the output of the following program, replacing newlines with commas?

class Test {
    public static boolean f1() {
        System.out.println("hello");
        return false;
    }

    public static boolean f2() {
        System.out.println("world");
        return true;
    }

    public static void main(String[] args) {
        System.out.println(f1() || f2());
    }
        
}

1. hello, true
2. hello, world, true
3. world, true
4. hello, false

What is the output of the following code?

class Test {
    public static void main(String[] args) {
        ArrayList<Integer> hi = new ArrayList<Integer>();
        hi.add(1); hi.add(2);
        for (int i : hi) {
            hi.add(2);
        }
    }
}

1. The list will contain 1, 2
2. The list will contain 1, 2, 2, 2
3. The list will contain 1, 2, 2
4. None of the above

What does the following code print out?

import java.util.*;

public class Test{
	public static void main(String[] args){
		Deeue<String> queue = new LinkedList<String>();
		queue.add("first");
		queue.add("second");
		queue.remove();
		queue.add("third");
		System.out.println(queue.remove());
	}
}

1. first
2. second
3. third
4. System will throw an exception

What does the following code print out?

public class Test{
	public static void main(String[] args){
		int x = 0;
		for(int i = 0; i< 5; i++){
			for(int j = 3; j< i; j++){
				for(int k = 0; k< 3*j-2; k++){
					x += 1;
				}
			}
		}
		System.out.println(x);
	}
}
    

1. 3
2. 7
3. 8
4. 9

What does the following code print out?

public class Test{
	public static void main(String[] args){
		Deque<Integer> que = new LinkedList<Integer>();
		Deque<Integer> stac = new LinkedList<Integer>();
		for(int i = 10; i>=0 ; i--){
			if(i%2==0){
				que.add(i);
			}else{
				stac.push(i);
			}	
		}
		que.remove();
		for(int i = 0; i<3; i++){
			stac.push(que.remove());
		}
		System.out.println(stac.pop());
	}
}

1. 4
2. 7
3. 9
4. System will throw an exception

You have an object x of type Example, with field y, which is of type HashMap<String,ArrayList<String>>, as shown here:

public class Example{
	public HashMap<String,ArrayList<String>> y;
	
	public Example(){
		y = new HashMap<Integer,ArrayList<String>>();
		y.put(1,new ArrayList<String>());
	}
}

public class Test{
	public static void main(String[] args){
		Example x = new Example();	
	}
}

Which of the following lines, executed in the Test class above, will place a string "Hello" into one of the ArrayLists in x?

1. x.y.get(1).put(1,"Hello");
2. y.get(1).add("Hello");
3. x.y.get(1).add("Hello");
4. x.y.put(1,"Hello");

Consider the following code:

public class Example {
	public static int x = 1;
	public int y = 1;
	public int[] z = {1};
	
	public void increment(int i){
		x++;
		y++;
		z[0]++;
		i++;
	}
	
	public int returnSum(){
		return x + y + z[0];
	}
	public static void main(String[] args){
		int i = 0;

		Example m = new Example();
		System.out.println(m.returnSum());
		m.increment(i);
		System.out.println(m.returnSum());
		
		Example n = new Example();
		System.out.println(n.returnSum());
		n.increment(i);
		System.out.println(m.returnSum());
		System.out.println(i);
	}
}

What is the correct output?

1. 4, 7, 5, 8, 1
2. 3, 6, 4, 7, 0
3. 2, 8, 4, 5, 2
4. None of the above

Consider the following method:

public boolean mystery1 (int num) {
	return (num % 3 == 0 && num % 5 != 0);
}

What does this method do?

1. Determines whether a number is a multiple of 15.
2. Determines whether a number is a multiple of 3 or 5, but not both.
3. Determines whether a number is a multiple of 3, but not a multiple of 5.
4. Determines whether a number is a multiple of 5, but not a multiple of 3.

Consider the following code:

public String mystery2(int num) {
	String s = "";
	for (int i = 1; i < num; i++) {
		s += Integer.toString(i) + ", ";
	}
	s += Integer.toString(num);
	return s;
}

What would be the String returned by calling mystery2(5)?

1. 1 2 3 4 5
2. 5 4 3 2 1
3. 1, 2, 3, 4, 5
4. 5, 4, 3, 2, 1

Consider the following code:

public static void main(String[] args) {
    Map<String, Integer> m = new HashMap<String, Integer>();
    for(int i = 0; i < 10; i++) {
        m.put("key + i", i);
    }
}

Which statement is true?

1. The key 3 has value 3, and the size of m.keySet() is 1
2. The key 3 has value 3, and the size of m.keySet() is 10
3. The key 3 is not in the map, and the size of m.keySet() is 1
4. None of the above

Consider the following code:

public class Exam {
    private int score;
    private String courseName;
    private double gradeWeight;
    
    public Exam(int s, String cN, double gW) {
        this.score = s;
        this.courseName = cN;
        this.gradeWeight = gW;
    }

    public int getScore() { return this.score; }
    public String getCourseName() { return this.courseName; }
    public double getGradeWeight() { return this.gradeWeight; }
    public void setScore(int newScore) { this.score = newScore; }

    public static void main(String[] args) {
        Exam e1 = new Exam(100, "COSI 12b", 0.25);
        Exam e2 = new Exam(100, "COSI 12b", 0.25);
        System.out.println(e1.equals(e2));
        System.out.println(e1 == e2);
    }
}

What is the output?

1. true, false
2. true, true
3. false, true
4. false, false

Consider the following code:

public static void main(String[] args) {
    Set<String> s = new HashSet<String>();
    s.add("hello");
    s.add("world");
    s.add("hello");
}

What is s.size()?

1. 1
2. 2
3. 3
4. It cannot be determined at compile time

Consider the following variable declarations:

Integer n1 = 15;
Integer n2 = 7;
Integer n3 = 15;
String s1 = "computer";
String s2 = "soda";
String s3 = "pencil";

Indicate whether the result of each of the following comparisons is positive, negative, or 0:

1. n1.compareTo(n2)
2. n3.compareTo(n1)
3. n2.compareTo(n1)
4. s1.compareTo(s2)
5. s3.compareTo(s1)
6. s2.compareTo(s2)

Consider the following method:

public static void mystery(int[] a) {
    for (int i = 1; i < a.length - 1; i++) {
        a[i] = (a[i - 1] + a[i + 1]) / 2;
    }
}

Indicate in your response what would be stored in the array after the method mystery executes given the following code:

// Response A
int[] a1 = {1, 1, 3};
mystery(a1);

// Response B
int[] a2 = {2, 1, 2, 4};
mystery(a2);

// Response C
int[] a3 = {6, 13, 0, 3, 7};
mystery(a3);

// Response D
int[] a5 = {7, 2, 3, 1, -3, 12};
mystery(a5);

1. Response A:
2. Response B:
3. Response C:
4. Response D:

Assume the following four classes have been defined:

public class Tulip extends Rose {
   public void verse1() {
      System.out.print("Tulip 1 ");
   }
}

public class Violet {
   public void verse1() {
      System.out.print("Violet 1 ");
   }

   public void verse2() {
      System.out.print("Violet 2 ");
   }

   public String toString() {
      return "Violet";
   }
}

class Rose extends Lily {
   public String toString() {
      return "Rose " + super.toString();
   }
}

class Lily extends Violet {
   public void verse1() {
      super.verse1();
      System.out.print("Lily 1 ");
   }

   public void verse2() {
      System.out.print("Lily 2 ");
      verse1();
   }

   public String toString() {
      return "Lily";
   }
}

Given the classes above, what output is produced by this code:

pretty = { new Tulip(), new Lily(), new Violet(), new Rose() };

for (int i = 0; i < pretty.length; i++) {
   System.out.println(pretty[i]);
   pretty[i].verse1();
   System.out.println();
   pretty[i].verse2();
   System.out.println();
   System.out.println();
}

1. Line 1:
2. Line 2:
3. Line 3:
4. Line 4:

Given this program:

public class MyStuff {
  MyStuff(String n) {
    name = n;
  }

  String name;

  public static void main(String[] args) {
    MyStuff m1 = new MyStuff("guitar");
    MyStuff m2 = new MyStuff("tv");
    System.out.println(m2.equals(m1));
  }

  public boolean equals(Object o) {
    MyStuff m = (MyStuff) o;
    if (m.name != null)
      return true;
    return false;
  }
}

What is the result?

1. The output is "true" and MyStuff fulfills the Object.equals() contract.
2. The output is "false" and MyStuff fulfills the Object.equals() contract.
3. The output is "true" and MyStuff does NOT fulfill the Object.equals() contract.
4. The output is "false" and MyStuff does NOT fulfill the Object.equals() contract
5. Compilation fails

Given this program:

import java.util.*;
public class Primes {
  public static void main(String[] args) {
    List p = new ArrayList();
    p.add(7);
    p.add(2);
    p.add(5);
    p.add(2);
    p.sort(null);
    System.out.println(p);
  }
}

What is the result?

1. [2, 5, 7]
2. [2, 2, 5, 7]
3. [7, 2, 5, 2]
4. [7, 5, 2, 2]
5. Compilation fails

Given this program:

interface Rideable {
  String getGait();
}

public class Camel implements Rideable {
  int weight = 2;

  public static void main(String[] args) {
    new Camel().go(8);
  }

  void go(int speed) {
    ++speed;
    weight++;
    int walkrate = speed * weight;
    System.out.print(walkrate + getGait());
  }

  public String getGait() {
    return " mph, lope";
  }
}

What is the result?

1. 16 mph, lope
2. 18 mph, lope
3. 24 mph, lope
4. 27 mph, lope
5. Compilation fails.
6. An exception is thrown at run time.

Given this program:

class Alpha {
  String getType() {
    return "alpha";
  }
}

class Beta extends Alpha {
  String getType() {
    return "beta";
  }
}

class Gamma extends Beta {
  String getType() {
    return "gamma";
  }

  public static void main(String[] args) {
    Gamma g1 = new Alpha();
    Gamma g2 = new Beta();
    System.out.println(g1.getType() + " " + g2.getType());
  }
}

What is the result?

1. alpha beta
2. beta beta
3. gamma gamma
4. alpha alpha
5. Compilation fails.

In this expression:

museum.getFloor(3).getExhibit(5).getCurator().name.toUpper();

What is the (probable) datatype of each subexpression?

1. museum
2. museum.getFloor(3)
3. museum.getFloor(3).getExhibit(5)
4. museum.getFloor(3).getExhibit(5).getCurator()
5. museum.getFloor(3).getExhibit(5).getCurator().name
6. museum.getFloor(3).getExhibit(5).getCurator().name.toUpper()

Streams

Java 8 Streams are also a new feature of Java 8. What will each of these programs print out?

// What gets printed out?
List<String> strings = Arrays.asList("abc", "", "bc", "efg", "abcd", "", "jkl");
long count = strings.stream().filter(string -> string.isEmpty()).count();
System.out.println(count);

// What gets printed out?
Stream.of("Edgecomb", "Fan", "Felig", "Flores", "Gold", "Goncalves Dos Santos",
    "Hakakian", "Hechtman")
  .map(s -> s.toUpperCase())
  .filter(s -> (s.length() > 5))
  .sorted()
  .forEach(s -> System.out.println(" " + s));

// What gets printed out?
System.out.println(
    Arrays.asList(12, 100, 41, 9, -5, 3001)
    .stream()
    .reduce(Integer.MAX_VALUE, (accum, val) -> (val < accum) ? val : accum));```

Software design

A student creates a class to represent a list of integer values with methods for average, sum, and median. When the student realizes that they also need to compute these things for Doubles, they copy/paste their class and change each instance of Integer to Double. What principle of good software engineering is being most violated?

1. DRY (do not repeat yourself)
2. YAGNI (you ain't gonna need it)
3. PLS (principle of least surprise)
4. KISS (keep it stupidly simple)

In order to calculate the sum of all positive even integers below one billion, a student writes three classes, one to represent even integers, another to represent positive integers, and another to represent integers less than a billion. What principle of good software engineering is being most violated?

1. DRY (do not repeat yourself)
2. YAGNI (you ain't gonna need it)
3. KISS (keep it stupidly simple)

While designing a system to allow students to enroll in summer courses, a software developer spends time ensuring that their code can be expanded to allow students to find fun places to eat. What principle of good software engineering is being most violated?

1. DRY (do not repeat yourself)
2. YAGNI (you ain't gonna need it)
3. PLS (principle of least surprise)
4. KISS (keep it stupidly simple)

For the Library programming assignment, a student implemented all their code in one class called MyLibrary, storing books into a 4D arary. What principle of good software engineering is being most violated?

1. DRY (do not repeat yourself)
2. YAGNI (you ain't gonna need it)
3. PLS (principle of least surprise)
4. KISS (keep it stupidly simple)

You are designing a system to represent simple geometric systems containing squares, circles, and trapezoids. To do so, you create three classses, Square, Circle, and Trapezoid. Since all three classes share a method called calculateArea, and because you follow the DRY principle, you only want to write the method once. Which of these is not an acceptable way to do this?

1. Create an interface called Areaable with a default method calculateArea
2. Create an abstract parent class called Shape with a calculateArea method
3. Create a static class called AreaCalculator with a singe method calculateArea that each of your shape classes will call
4. Create an interface Areaable and an abstract parent class Shape which implements Areaable

While designing code for a chess game, you realize that many classes (Knight, King, etc.) need to share similar properties relating to being a piece. Piece should be...

1. an abstract class
2. an interface
3. a regular class
4. an enum

When practicing object oriented programming, we often say that we are mapping objects from a real-world ____________ into an ____________ of classes, interfaces, methods, and variables.

1. ontology
2. epistemology
3. axiology
4. deontology

Computer history

The first computer compiler was written by:

1. Grace Hopper
2. Alan Turing
3. Ada Lovelace
4. Richard Stallman

Who is commonly given credit for creating the field of information theory?

1. Grace Hopper
2. Alan Turing
3. Claude Shannon
4. Alan Kay

Which famous computer scientist is most well-known for their relationship to the free (as in speech) software movement?

1. Ada Lovelace
2. Alan Kay
3. Richard Stallman
4. Dennis Ritchie

Who was the first computer programmer?

1. Ada Lovelace
2. Charles Babbage
3. Dennis Ritchie
4. Alan Turing

Who is considered the creator of object oriented programming?

1. Alan Kay
2. Charles Babbage
3. Claude Shannon
4. Richard Stallman

Java

Function overloading is ....

1. when a subclass provides a specific implementation of a method that is already provided by its parent class
2. when a subclass provides a method that is not provided by its parent class
3. when a class has multiple functions by the same name but different parameters
4. when a class has multiple functions by the same name, resulting in an error

The import keyword is used to...

1. import only built-in packages into your java source file
2. import both built-in packages and user-defined packages into your java source file
3. import only user-defined packages into your java source file
4. None of the above

How is an instance of a class created (order matters)?

1. Declaration, instantiation, initialization
2. Instantiation, declaration, initialization
3. Initialization, declaration, instantiation
4. Initialization, instantiation, declaration

Which of the following classes define the println() method?

1. System class
2. Object class
3. InputStream class
4. PrintStream class

Code that recurses forever without termination will trigger what exception?

1. NullPointerException
2. ConcurrentModificationException
3. FileNotFoundException
4. StackOverflowException

Which of the following has to be given a size before it is utilized?

1. LinkedList
2. ArrayList
3. Array
4. Stack

Which of the following does NOT implement the Collection interface?

1. LinkedList
2. Array
3. HashSet
4. Stack

Which of the following variables use value semantics?

1. int x
2. int[] y
3. Object z
4. 1 and 2

A student named Bob writes the following two classes, putting both in the same package:

public class AccessControl{
	public int a;
	private int b;
	protected int c;
	int d;
}

public class SubAccessControl extends AccessControl{
	public SubAccessControl(){
		this.a = 5;
		this.b = 5;
		this.c = 5;
		this.d = 5;
	}
}

Sarah notes that the SubAccessControl constructor should not compile, because not all the fields in AccessControl are visible to the SubAccessControl class. Which statement is true?

1. Sarah is correct. Only a, c, and d are visible.
2. Sarah is correct. Only a and d are visible
3. Sarah is incorrect, all fields are visible.
4. Sarah is incorrect. The code will compile, but it is a bad practice.

How do you define a natural ordering for a class you've written? You may assume the class implements the Comparable interface.

1. The class must implement the compareTo() and equals() methods so that they are compatible with one another.
2. The class must implement the compareTo() and toString() method.
3. The class must implement the equals() and toString() method.
4. All classes have their natural ordering defined at compile-time.

(Extra) Which of the following are valid reason(s) to create an inner class?

1. The inner class will be used to perform some task in the outer class, so it will ensure that the outer class object is created to access it.
2. Inner classes have access to the containing class's private fields.
3. Inner classes always run in constant space and time.
4. 1 and 2
5. 2 and 3
6. All of the above.

Consider the following code:

public class OverLoad {
    public void method(int a, int b) { }
    public int method(int a, int b) { }
}

1. It will compile
2. It will not compile

What is an abstract class?

1. A kind of class that cannot be instantiated
2. Another term for an interface
3. A class which is written in pseudo code
4. None of the above

What is a static method?

1. A method that does not change (cannot be reassigned)
2. A method that can be called on a class, as opposed to an instance of a class
3. A method that takes no parameters
4. All of the above

What is a primitive type?

1. A type that has value semantics
2. int, for example
3. Cannot be stored in an ArrayList directly
4. All of the above

What is an interface?

1. A graphical user interface (frontend)
2. A set of methods that form a contract
3. None of the above

What is a Java package?

1. A named collection of Java source files
2. Each version of Java that is installed on your computer is considered a package
3. An obsolete feature of Java which is no longer recommended
4. An interface together with all the classes that implement it

What is recursion?

1. Cursing something, again
2. A method that calls itself
3. A method of proof
4. None of the above

What is a final class?

1. A class that cannot be changed after it is instantiated
2. A class that cannot be subclassed
3. A class that is immutable
4. All of the above

This code does not compile. Why not?

ArrayList<int> numbers = new ArrayList<int>();
numbers.add(7);

1. You cannot add 7 to an empty list
2. You must cast 7 to an Integer
3. You cannot create an ArrayList of ints
4. All of the above

You know that if you redefine the equals() method for a class, then you must also redefine the hashCode() method. Please answer:

1. If you don't redefine both, then your program will not compile. True or False.
2. If you define an equals method and not a corresponding hashCode method, then your program will throw an exception. True or False.
3. All classes inherit a standard version of equals and hashCode from where?
4. If your class needs a "natural ordering" then you need to redefine hashCode and equals. True or false.
5. If a.equals(b): it is required that a.hashCode() == b.hashCode(). True or false?
6. If !a.equals(b): it is not required that a.hashCode != b.hashCode(). True or false?

When running a Java program, execution begins by

1. Executing the very first line in the file
2. Executing the static void main method found in any of the files of the program
3. Executing the very first line of the class called Main
4. Depends on whether the program is run with Eclipse or from the command line
5. None of the above

It is important to understand the method signature in order to properly use overloading, overriding as well as interfaces. Which of these are not part of the method signature?

1. Return datatype
2. Exceptions thrown
3. Method name
4. Parameter name
5. Parameter datatype
6. modifiers (e.g. private, public etc.)

Which of these are not valid statements:

1. String[] suits = ["Clubs", "Diamonds"];
2. String[] suits = { Clubs, Diamonds };
3. String[] year = { "Freshman", "Software", "Junior", "Senior" }
4. String year[] = new String[10];
5. String year = new String[];
6. int[] oneDim = new int[10];
7. int[][] twoDim = new int[3][5];
8. String[][][] threeDim = new String[2][3][2];

Assume the following context:

String name = "Brandeis";
ArrayList<String> longList = new ArrayList<String>();

For all these expressions, answer what the datatype is, and what they value they have, if it can be determined.

1. 1 + 2
2. "Brandeis".equals("MIT")
3. "a" + " fine day"
4. 'a' + " wonderful afternoon"
5. "Brandeis".equals("MIT") || true
6. new Random().nextInt(100) == 9
7. longList.size() > 0
8. name.charAt(0)
9. name.substring(4).length > 5

PAs

In PA2 (Game of 15), we wrote an interface to a slide puzzle game using a provided class that implemented various methods like moveUp. This most closely represents...

1. Inheritance
2. Abstraction
3. YAGNI
4. None of the above

In PA3 (security and leaky abstractions), we learned that Strings were a bad way to store structured data. Consider the following code:

package edu.brandeis.cs12b.pa3;

/**
 * YOU MAY NOT MODIFY THIS CLASS.
 * 
 *
 */
public class UserAuthenticator {
	private String users = "Bob//test//regular";
	
	/**
	 * Adds a regular user with the given username and password to the database.
	 * @param username the username to add
	 * @param password the password of that user
	 */
	public void addRegularUser(String username, String password) {
		if (password.contains("//"))
			return;
		users = username + "//" + password + "//regular\n" + users;
	}
	
	/**
	 * Authenticates a user based on a username or password. Will return
	 * either the user's access type ("regular" or "admin"), or the string
	 * "Authentication failure!" if the username or password is incorrect
	 * 
	 * @param username the username to log in with
	 * @param password that user's password
	 * @return the user status or "Authentication failure!"
	 */
	public String authenticateUser(String username, String password) {
		for (String line : users.split("\n")) {
			String[] fields = line.split("//");
			
			if (username.equals(fields[0]) && password.equals(fields[1])) {
				return fields[2];
			}
		}
		
		return "Authentication failure!";
	}
}

An additional check to make sure that password does not contain the separator sequence (//) has been added. Which statement is true?

1. The system is no longer vulnerable to an injection attack and the abstraction is no longer leaky
2. The abstraction is still leaky, but the system is no longer vulnerable to an injection attack
3. The system is no longer vulnerable to a timing attack
4. The system is still vulnerable to an injection attack and the abstraction is still leaky.

In PA4 (stats), we wrote reducer classes that a reduce method that took two values: an initial value and a next value. For each item in the list, the reduce method was called with its previous return value as the initial value. Which statement is true?

1. A value of 0 is always appropriate for the initial value
2. This structure only lets the reducer look at a single value from the list at a time
3. This structure is not general enough to express summation
4. None of the above

In PA5 (graphs), we represented Brandeis University as a graph where the vertices were buildings and the edges were weighted paths between them. Kruskal's algorithm was used to compute the minimum spanning tree of the graph, which is...

1. The minimum set of vertices such that all edges are still connected
2. The minimum set of edges such that the sum of their weights is still positive
3. The set of edges with minimal weight sums that still connects all the vertices
4. All of the above

In PA6 (Twitter), we used several APIs in order to create a word cloud for tweets. Which statement is false?

1. The Lucene API let us tokenize our input
2. APIs all require registration with a website to get access keys
3. The Kumo API helps build word clouds
4. None of the above are false

(Extra) In PA7 (knowledge trees), we represented facts about the real world using is-a relationships. This sort of representation is:

1. Ontological, because it makes a statement about what is
2. Ontological, because it makes a statement about how knowledge is represented
3. Epistemological, because it makes a statement about how knowledge is represented
4. Axiological, because it makes a statement about what should be

In PA7 (knowledge trees), we represented knowledge in a way that enabled a computer to answer simple questions. Which of the following was not a piece of information our system could have deduced?

1. A bee is a bug
2. A bird is an animal
3. A rectangle is a shape
4. None of the above

In PA8 (compression), we attempted to make an array of orders smaller. The primary lesson, due to Shannon, is:

1. Making data smaller depends only on the algorithms you are capable of implementing
2. The more we know about the data, the smaller we can make it.
3. Making assumptions about the data does not help compress the data
4. No matter how much you try, you'll never be able to beat ZIP

In PA9 (domain modeling), we represented a library as Java objects. Which statement is false?

1. Java programs consist of classes and objects, so we map the attributes of a library (books, cases, shelves) into those terms
2. In Java, classes and objects can be used to represent real world things, creating a useful separation of responsibilities
3. The creation of classes or objects to represent real world objects is a process known as domain modeling
4. None of the above are false

In PA10 (compilers), we created a lexer, a parser, an interpreter, and a compiler. Which statement is false?

1. Lexers transform source code into a stream of meaningful lexemes
2. If two programs have an identical stream of lexemes, their textual representation is also identical
3. Lexers must always be lazy
4. Lexers can be represented as finite state transducers

In PA10 (compilers), we created a lexer, a parser, an interpreter, and a compiler. Which statement is false?

1. A parser is responsible for transforming a stream of lexemes into a parse tree
2. It is easier to compare the parse trees of two programs than it is to compare the lexemes of two programs
3. Generating a parse tree is usually done before interpretation or compilation
4. None of the above are false

In PA10 (compilers), we created a lexer, a parser, an interpreter, and a compiler. Which statement is false?

1. An interpreter evaluates PitoScript trees from the bottom-up, prompting the user when needed.
2. An interpreter must keep track of the value of each variable as it processes statements.
3. Interpretation generally happens before compilation
4. Interpretation isn't always slower than compilation

In PA10 (compilers), we created a lexer, a parser, an interpreter, and a compiler. Which statement is false?

1. A compiler transforms a parse tree into a sequence of low-level instructions
2. The program generated by a compiler has nothing to do with the input lexemes
3. The compiler must keep track of where it has stored values in memory
4. None of the above are false

In PA10 (compilers), we created a lexer, a parser, an interpreter, and a compiler. Which statement is false?

1. Registers are special places in memory
2. Memory can be thought of as an array of values
3. Instructions are executed one at a time by the VM
4. The OUTPUT instruction is not needed in order to return the values of variables

Programming

Write a static method named samePattern that accepts two arrays of integers as parameters and returns true if the second array is composed of repetitions of the first array and false otherwise.

Your response implements this:

static boolean samePattern(int[]one, int[]two) ...

---

Write a static method named countCommon that accepts three arrays of strings as parameters and returns an integer count of how many indexes store exactly the same string in all three arrays. For example, if the arrays are:

// index        0     1      2      3      4       5        6        7
String[] a1 = {"hi", "Ed",  "how", "are", "you",  "folks", "DoIng", "today?"};
String[] a2 = {"hi", "Bob", "how", "are", "YOUR", "kids",  "doing", "today?"};
String[] a3 = {"hi", "you", "how", "are", "you",  "guys",  "DOING", "today?"};

Then the call of countCommon(a1, a2, a3) should return 4 because indexes 0, 2, 3, and 7 store exactly the same string in all three arrays. Indexes 1, 4, 5, and 6 do not. (Index 6 differs by capitalization.)

The arrays might not be the same length. An index must be within the bounds of all three arrays to be considered. For example, given the arrays below, the call of countCommon(a4, a5, a6) should return 3 because all three arrays store the same values at indexes 0, 2, and 5:

// index        0     1      2      3      4      5         6       7
String[] a4 = {"hi", "Ed",  "how", "ARE", "you", "Doing", "I'm",  "fine"};
String[] a5 = {"hi", "Bob", "how", "are", "YOU", "Doing"};
String[] a6 = {"hi", "you", "how", "is",  "you", "Doing", "this", "fine", "day?"};

For full credit, do not modify the elements of the arrays passed in. Do not make any assumptions about the length of the arrays or the length of the strings stored in them. You may assume that none of the arrays or elements are null.

int countCommon(String[] one, String[]two, String[] three) {} ...

---

At the bottom of the page, write the output produced by the following program, as it would appear on the console.

public class ParameterMystery {
	public static void main(String[] args) {
		String bril = "vorpal";
		String gyre = "jubjub";
		String slithy = "snack";
		String tum = "mut";
		String mut = tum + 1;

		mystery(bril, slithy, gyre);
		mystery(gyre, "gyre", mut);
		mystery(gyre + slithy, bril, tum);
		tum = "tumtum";
		bril = "slithy";
		mystery(tum, gyre, slithy);
	}

	public static void mystery(String gyre, String bril, String slithy) {
		System.out.println("Twas " + bril + " and the " + slithy +
         " toves did " + gyre);
	}
}

1. Answer:

---

Write a method called writeSequence that accepts an integer n as a parameter and prints to the console a symmet- ric sequence of n numbers composed of descending integers that ends in 1, followed by a sequence of ascending integers that begins with 1. The following table indicates the output that should be produced for various values of n:

  Method call               Output produced
  -----------------------------------------
  writeSequence(1);         1
  writeSequence(2);         1 1
  writeSequence(3);         2 1 2
  writeSequence(4);         2 1 1 2
  writeSequence(5);         3 2 1 2 3
  writeSequence(6);         3 2 1 1 2 3
  writeSequence(7);         4 3 2 1 2 3 4
  writeSequence(8);         4 3 2 1 1 2 3 4
  writeSequence(9);         5 4 3 2 1 2 3 4 5
  writeSequence(10);        5 4 3 2 1 1 2 3 4 5

Notice that when n is odd the sequence has a single 1 in the middle, while for even values it has two 1s in the middle. Your method should throw an IllegalArgumentException if it is passed a value less than 1.

---

Lambdas

The Lambda expression was newly introduced in Java 8. Lambdas are useful on their own and also very important in the design Java 8 Streams. The general or generic syntax for a lambda is:

(parameters) -> expression
-or-
(parameters) -> { statements; ... }

1. Write a lambda expression which returns true if a string parameter is longer than 5 characters
2. Write a lambda expression which returns the square of a number parameter
3. Write a lambda expression which returns true if a numeric parameter is even