Chapter 7: Generics and Collections

Question 1

What are the 4 rules for a valid .equals override?

Answer 1

• Reflexive: For any reference value x, x.equals(x) always returns true.
• Symmetric: For any reference values x and y. If x.equals(y) returns true, so should y.equals(x);
• Consistent: For any refernce values x and y. Multiple invocations of x.equals(y) should return the same value.
• For any non-null reference value x, x.equals(null) should return false.

Question 2

True or False:

If x.equals(y) returns true, x.hashCode == y.hashCode may return false.

Answer 2

False, if x.equals(y) returns true, then both objects should generate the same hashcode.

Question 3

Describe the steps for Hashing retrieval (f.e. HashMap).

Answer 3

1. Find the right “bucket” using the hasCode() method of the object.
2. Compare all the items in the bucket with the object using the equals method.

Question 4

True or False:

If x.hashCode == y.hashCode is true, x.equals(y) is always true.

Answer 4

False! x.equals(y) may return false. HashCode only describes in which bucket the object should be stored (f.e. HashMap). However if x.equals(y) indeed returns true, then the hashCode methods should return the same value.

Question 5

What is wrong with the following hashCode override?

public int hashCode() { return 999; }

Answer 5

It’s a valid override because it doesn’t break the contract. However will be very inefficient when used in Hash retrieval collections.

Question 6

What are the 3 contract rules for the hashCode method?

Answer 6

• Whenever the method is invoked it should always consitently return the same value for a given object.
• Whenever x.equals(y), both x and y should generate the same hashCode.
• It is NOT required to generate unique hashCode values for two objects that are considered equal (using the equals method) but is recommended because of performance improvements.

Question 7

What happens if you use a transient instance variable in determining the hashCode?

Answer 7

If you serialize and deserialize the object. The object may suddenly produce a different hashCode because the value is lost in the serialization proces. It will get it’s default value.

Question 8

What are the basic flavors for Collections?

Answer 8

Lists, Sets, Maps and Queues

Question 9

What are the sub-flavors for Collections?

Answer 9

Sorted, Unsorted, Ordered, Unordered

Question 10

What is an ordered collection?

Answer 10

It means you can iterate through a collections in a specific not-random order. (f.e. ArrayList uses the index as the order).

Question 11

What is an sorted collection?

Answer 11

It means the order in the collection is determined by some rule or rules, known as the sort order.

Question 12

Describe the three List implementations, and whether they are ordered, unorderd, sorted and/or unsorted.

Answer 12

ArrayList, ordered (by index) but unsorted
Vector, ordered (by index) but unsorted (thread-safe, synchronized). Old java version.
LinkedList, ordered (by index) also implements the queue interface. Elements are linked.

Question 13

Describe the three Set implementations and whether they are ordered, unorderd, sorted and/or unsorted.

Answer 13

HashSet, unsorted and unordered. Uses hashCodes for placing in the collection.
LinkedHashSet, unsorted but ordered. Use this if you care about the iteration order (order of insertion)
TreeSet, sorted. Using natural order (ascending) or custom defined order using Comparable or Comparator.

Question 14

Describe the four Map implementations and whether they are ordered, unorderd, sorted and/or unsorted.

Answer 14

HashMap, unsorted and unorderd. Uses hashCodes for placing in the collection. Can contain a single NULL key and many NULL values.
Hashtable, unsorted and unorderd. Old java version. Cant’t contain NULL values as key or value.
LinkedHashMap, unsorted but ordered. Keeps insertion order.
TreeMap, sorted. Keeps natural order or custom order using the Comparable ar Comparator interfaces.

Question 15

Describe the Queue implementations and whether they are ordered, unorderd, sorted and/or unsorted.

Answer 15

LinkedList, ordered (by index) also implements the queue interface. Elements are linked.
PriorityQueue, sorted by natural order or custom order if defined with a Comparable or Comparator implementation.

Question 16

What will the compareTo() method return for a valid implenetation of the Comparable interface?

Answer 16

negative -> thisObject < anotherObject
zero -> thisObject == anotherObject
psoitive -> thisObject > anotherObject

Question 17

What is the difference between the Comparable interface and the Comparator interface?

Answer 17

• Comparable should be implemented by the class you want to sort. Comparator can be any class and can sort any type of object (even final classes because you don’t neet to modify the to be sorted class).
• Comparable uses the method compareTo(objTwo). Comparator uses the method compare(objOne, objTwo).
• Comparable can only define one sort order for an Object. You can create many variants of the Comparator implementation for the same object.

Question 18

What are the util methods for sorting lists and arrays?

Answer 18

Collections.sort(listToSort)
Collections.sort(listToSort, Comparator)
Arrays.sort(arrayToSort)
Arrays.sort(arrayToSort, Comparator)

Question 19

What will be the result?
String [] sa = {"1", "2", "3"}
Arrays.sort(sa);
Arrays.binarySearch(sa, "1"); // 1
Arrays.binarySearch(sa, "4"); // 2

List list = Arrays.asList(sa);
ReverseComparator rs = new ReverseComparator()
Collections.sort(list, rs);
Collections.binarySearch(list, “3”, rs); // 3

Answer 19

1. 0
2. -4 (inertion point is actually 3, but it is returned as a negative number. Because value 0 is still a found match.)
3. 0

Question 20

What is the result?
TreeSet times = new TreeSet();
times.add(1205);
times.add(1505);
times.add(1545);
times.add(1830);
times.add(2010);
times.add(2100);

times. lower(1505); // 1
times. floor(1505); //2
times. higher(1830); //3
times. ceiling(2010); //4

Answer 20

1. 1205
2. 1505
3. 2010
4. 2010

// lower: returns the first element that is lower then the given key.
// floor: return the first element that is equal or lower then the given key.
// higher: returns the first element that is higher then the given key.
// ceiling: return the first element that is higher or equal to the given key.

Question 21

Describe the methods for retrieving (and removing) an item from a TreeSet and TreeMap.

Answer 21

TreeSet.pollFirst();
TreeSet.pollLast();

TreeMap.pollFirstEntry();
TreeMap.pollLastEntry();

Question 22

TreeSet has lower, floor, etc. methods, what are the equivalents for a TreeMap?

Answer 22

TreeMap.lowerKey(key); the first lower key
TreeMap.floorKey(key); the first lower or equal key
TreeMap.higherKey(key); the first higher key
TreeMap.ceilingKey(Key); the first higher or equal key

Question 23

What are the items contained in map and submap?

TreeMap map = new TreeMap<>();

map. put(“a”, “ant”);
map. put(“d”, “dog”);
map. put(“h”, “horse”);

SortedMap submap = map.subMap(“b”, “g”);

map. put(“b”, “bat”);
submap. put(“f”, “fish”);
map. put(“r”, “raccoon”);

Answer 23

Map:
a=ant
b=bat
d=dog
f=fish
h=horse
r=raccoon

SubMap
b=bat
d=dog
f=fish

Submap is a backed collection. Anything that is added to the original map that is also in the range defined for the submap (b-g) it is automatically added to the submap. When something is added into the submap it is also added to the original map but only if it’s inside the given range (b-g). If an item is added that is outside the range, (submap.put(“p”, “pig”)) an exception is thrown.

Question 24

What are the three important PriorityQueue methods?

Answer 24

peek(); // returns the highest priority item without removing it.
poll(); // returns the highest priority item and removes it from the queue.
offer(); // Add element to the queue.

Question 25

What determines the priority in a PriorityQueue?

Answer 25

1. Natural order
PriorityQueue queue = new PriorityQueue();

2. Custom order using comparator
PriorityQueue queue = new PriorityQueue(10, myComparator);

Question 26

What is the order of the queue given the following code?
String[] sa = { “ff”, “ f”, “f “, “FF” }

PriorityQueue queue = new PriorityQueue();

for(String s : sa)
queue.offer(s);

Answer 26

Natural order, because no comparator is given.

” f” => “FF” => “f “ => “ff”

Spaces sort for characters and uppercase letters sort before lowercase letters.

Question 27

What is the result of compiling and running the following code?

public class Generics {

    public static void main(String[] args) {
        List strings = new ArrayList();
        strings.add("test");
        Generics.addThings(strings);
        for(String string : strings) {
            System.out.println(string);
        }
    }

    public static void addThings(List list) {
        list.add(new Integer(1));
    }
}

Answer 27

Compiles fine (generics are a compile time protection). Will give an ClassCastException because an Integer cannot be cast to a String.

Question 28

What is the result of the following?
List animals = new ArrayList(); // 1
Animal[] animals2 = new Dog[3]; // 2

Answer 28

1. Compiler error.
   The type of the declaration and the initialization must be exactly the same.
2. Compiles fine.

Question 29

What is the result of the following?
public class Generics {

    public static class Animal {}
    public static class Dog extends Animal {}
    public static class Cat extends Animal {}

    public static void main(String[] args) {
        Dog[] dogs = { new Dog(), new Dog() };
        addThings(dogs);
    }

    public static void addThings(Animal[] animals) {
        animals[1] = new Cat();
    }
}

Answer 29

ArrayStoreException (RuntimeException)

Can’t put a Cat into a Dog array.

Question 30

What is the result of the following?
public void addAnimal(List  extends Animal> animals) {
animals.add(new Dog());
}

Answer 30

Compiler error.

You can’t add to the list if your using the ? notation.

Question 31

Will the following compile?

void foo(List < ? implements Serializable> list) {}

Answer 31

No

When using the ? notation you use extends for both super classes and interfaces. F.e.

? extends Serializable

Question 32

Which of these will compile?

1. List> list = new ArrayList();
2. List extends Animal> list = new ArrayList();
3. List> list = new ArrayList extends Animal>();
4. List extends Dog> list = new ArrayList();
5. List super Dog> list = new ArrayList();
6. List super Animal> list = new ArrayList();

Answer 32

1,2,5

3. You cant use a wildcard in the object creation.
4. You cant assing an integer list to an variable that takes a Dog list or a subtype of Dog).
5. You cant assign a Dog list to a Animal list (or a super type of animal). Dog is to low in the hierachy.

Question 33

Describe a method that takes a generic argument with no return type.

Answer 33

public void makeMyArrayList(T t);

this.makeMyArrayList(new Dog());

Question 34

What is wrong?
class X { public  X(X x) { } }

Answer 34

Nothing.

A class X with a constructor with a genericy typed argument named X.

Question 35

Given a TreeSet with the following contents:
a, aa, b, bb, c, cc

Complete the following code to get the output:
a, b, null, c

treeSet.(“a”);
treeSet.(“aaa”);
treeSet.(“a”);
treeSet.(“bb”);

Answer 35

floor -> equals or lower
ceiling -> equals or higher
lower -> lower then the given element
higher -> higher then the given element

Treeset is sorted frow lowest value to highest value a > cc

Question 36

True or False:

A HashSet can contain null values.

Answer 36

True

Question 37

Your application needs to load a set of key value pairs from a database table which never changes. Multiple threads need to access this information but none of them changes it.
Which class would be the most appropriate to store such data?

HashTable
HashMap
Set
TreeMap
List

Answer 37

HashMap

HashTable is synchronized and not needed for this situation because it will impact performance