Please keep all your answers short and to the point. Do not provide extra information that was not asked for.

1. (10 points) True or false?
1. true   An enum is a class. Yes, with methods and everything.
2. false  An enum may be abstract.
3. true   A tree that consists of a single node has depth zero.
4. false  If for(Thing thing : things) {...} is legal, then things is an Iterator. No, it's an Iterable.
5. false  Strings in Java are terminated by a zero byte. No, started with a length int.
6. false  A hashCode() method should return a number between 0 and the size of your array minus one.
          Returns an int; hashCode() doesn't know the size of your array.
7. true   log₂1024 = 10.
8. false  If two algorithms have the same Big-O running time, they are equally fast.
9. true   If you implement equals, it should be reflexive, symmetric, and transitive.
10. false  It doesn't make sense for a class's only constructor to be private. Used with Factory methods.
    
    
    
2. (6 points) Assume you are writing an Employee class, and

   You want to do the following:	What interfaces, if any, must your Employee class implement?	What methods must your Employee class implement? (Show the complete signature.)
   Use Employee objects as keys in a HashMap	None	public boolean equals(Object o) public int hashCode()
   Keep a SortedSet of Employee objects	Comparable (or use Comparator)	public int compareTo(T o) (Comparable uses public int compare(T o1, T o2)
   Be able to sort Employee objects by either their name field or their EmployeeId field	None (but its Comparator must implement public int compare(T o1, T o2) and public boolean equals(Object o)	None

   
   
3. (9 points) Suppose you have the following BNF rule:   <foo> ::= "u" [ "x" ] | "w" { "y" }
   In the lists below, circle the <foo>s and cross out the non-<foo>s
   

   	uu	uw	w
   	ux	uxy	wy
   	uxx	uxwy	wyyy

   
   
4. (4 points) Draw a state machine to recognize <foo> objects, as defined in the previous question. Indicate which states are your start and final states. Do not include an error state.
   
   
5. (3 points) Tell what the major error is in the following Recognizer method:

       public boolean term() {
           if (!term()) return false; Recursion is not with a simpler case.
           while (multiplyOperator()) {
               if (!term()) error("No term after '+' or '-'");
           }
           return true;  Also accepted: no base case, left recursive, infinite recursion
       }

6. (6 points) What order do you visit the nodes when you traverse this binary tree:

   In preorder?     *  +  x  y  z In inorder?         x  +  y  *  z In postorder?     x  y  +  z  *

   
   
7. (3 points) What is the difference between a data type and an abstract data type?
   
   An abstract data type does not define the data representation.
   
   
   
8. (4 points) Assume that array has been filled with randomly generated integers in the range 1 to 10. What is the expected running time (Big-O notation) of the following method?

       int findFive(final int ARRAY_SIZE, int[] array) {
           for (int i = 0; i < ARRAY_SIZE; i++) {
   	        if (array[i] == 5) return i;
           }
   	    return -1; O(1), or constant time; found on average after 5 probes.
       }

9. (4 points) What is the running time (Big-O notation) of the following method?

       int log2(int n) {
           int result = 0;
           int power = 1;
           while (power < n) {
               result++;
               power = 2 * power;  log2(n)
           }
           return result;
       }

10. (2 points) What is the difference between a mutative transformer and an applicative transformer?
    
    A mutative transformer changes the given object; an applicative transformer returns a new object.
    
    
11. (6 points) Suppose you wish to time a method. List three ways to improve the accuracy of your timing.
    
    Any three of:
         Call System.gc() before doing the timing.
         Minimize the number of other active processes.
         Repeat the timing many times and take the average.
         Repeat many times and discard the extreme values.
         Use nanoTime() -- helps only on certain computers.
    
    
12. (4 points) Put the following in order, best to worst: O(n²), O(2ⁿ), O(n), O(1), O(log n), O(n log n).
    
    

    (best)

    O(1)  O(log n)  O(n)  O(n log n)  O(n2)  O(2n)

    (worst)

    
    
    
13. (6 points) Suppose set1 and set2 are both objects of type Set. For each of the following, write a single Java statement to:
    
    
    1. Make set1 the union of the two sets
       set1.addAll(set2)
       
       
    2. Make set1 the intersection of the two sets
       set1.retainAll(set2)
       
       
    3. Make set1 the difference (set1 - set2) of the two sets
       set1.removeAll(set2)
       
       
    4. Set boolean isSubset to true if and only if set1 is a subset of set2
       isSubset = set1.containsAll(set2);
       
       
14. (18 points) List three methods declared by each of the following interfaces, with complete signatures. Do not include any inherited methods, for example, equals, or the methods that SortedSet inherits from Set.
    The following lists all and only the methods that I will accept for this question. All are public and abstract.

    Collection	boolean add(E o)	Iterator<E> iterator()
    	boolean addAll(Collection<? extends E> c)	boolean remove(Object o)
    	void clear()	boolean removeAll(Collection<?> c)
    	boolean contains(Object o)	boolean retainAll(Collection<?> c)
    	boolean containsAll(Collection<?> c)	int size()
    	boolean equals(Object o)	Object[] toArray()
    	int hashCode()	<T> T[] toArray(T[] a)
    	boolean isEmpty()
    Set	Just those declared in Collection.
    SortedSet	Comparator<? super E> comparator()	SortedSet<E> headSet(E toElement
    	E first()	SortedSet<E> tailSet(E fromElement)
    	E last()	SortedSet<E> subSet(E fromElement, E toElement)
    List	void add(int index, E element)	ListIterator<E> listIterator()
    	boolean addAll(int index, Collection<? extends E> c)	ListIterator<E> listIterator(int index)
    	E get(int index)	E remove(int index)
    	int indexOf(Object o)	E set(int index, E element)
    	int lastIndexOf(Object o)	List<E> subList(int fromIndex, int toIndex)
    Map	void clear()	boolean isEmpty()
    	boolean containsKey(Object key)	Set<K> keySet()
    	boolean containsValue(Object value)	V put(K key, V value)
    	Set<Map.Entry<K,V>> entrySet()	void putAll(Map<? extends K,? extends V> t)
    	boolean equals(Object o)	V remove(Object key)
    	V get(Object key)	int size()
    	int hashCode()	Collection<V> values()
    SortedMap	Comparator<? super K> comparator()	K lastKey()
    	K firstKey()	SortedMap<K,V> subMap(K fromKey, K toKey)
    	SortedMap<K,V> headMap(K toKey)	SortedMap<K,V> tailMap(K fromKey)

    
    
15. (6 points) For each of the following sort methods, tell what the invariant is. (An informal description in English is OK.)
    

    Bubble sort	Everything on the right end of the array is in the correct place. for all j > outer, if i < j, then a[i] <= a[j]
    Insertion sort	All elements on the left end of the array are sorted with respect to one another For all i < outer, j < outer, if i < j then a[i] <= a[j]
    Selection sort	Everything on the left end of the array is in the correct place. for all i <= outer, if i < j then a[i] <= a[j]

    
    
16. (3 points) What methods are required to implement each of the following interfaces?
    
    
    1. Iterable     Iterator<T> iterator()
       
       
    2. Comparable     int compareTo(T o)
       
       
    3. Comparator    int compare(T o1, T o2)
       
       
17. (8 points) State Dr. Dave's four rules for doing recursion.
    
    Do the base cases first
    Recur only with a simpler case
    Don't modify and use nonlocal variables
    Don't look down
    
    
    
18. (4 points) From Joel on Software, by Joel Spolsky:
    

    Schlemiel gets a job as a street painter, painting the dotted lines down the middle of the road. On the first day he takes a can of paint out to the road and finishes 300 yards of the road. "That's pretty good!" says his boss, "you're a fast worker!" and pays him a kopeck. The next day Schlemiel only gets 150 yards done. "Well, that's not nearly as good as yesterday, but you're still a fast worker. 150 yards is respectable," and pays him a kopeck. The next day Schlemiel lpaints 30 yards of the road. "Only 30!" shouts his boss. "That's unacceptable! On the first day you did ten times that much work! What's going on?" "I can't help it," says Schlemiel. "Every day I get farther and farther away from the paint can!"

    
    Assuming that Schlemiel works continuously (not day by day) until the entire N yards of the road is painted, what is the running time in Big-O notation of Schlemiel the Painter's Algorithm?
    
    At each step, Schlemiel goes to the paint can and back (an average of distance of N) and paints some constant number of dots (say, one yard's worth). He must do this N times. Hence, O(N²).
    For an exhaustive discussion, see:
       http://discuss.fogcreek.com/techInterview/default.asp?cmd=show&ixPost=153