Collections Interview Questions

Why Map interface does not extend Collection interface?

A good answer to this interview question is “because they are incompatible“. Collection has a method add(Object o). Map can not have such method because it need key-value pair. There are other reasons also such as Map supports keySet, valueSet etc. Collection classes does not have such views.

List interface related

Why we use List interface? What are main classes implementing List interface?

A java list is a “ordered” collection of elements. This ordering is a zero based index. It does not care about duplicates. Apart from methods defined in Collection interface, it does have its own methods also which are largely to manipulate the collection based on index location of element. These methods can be grouped as search, get, iteration and range view. All above operations support index locations.

The main classes implementing List interface are: Stack, Vector, ArrayList and LinkedList

How to convert an array of String to arraylist?

/String array

String[] words = {"ace", "boom", "crew", "dog", "eon"};

//Use Arrays utility class

List wordList = Arrays.asList(words);

//Now you can iterate over the list

Set interface related

Why we use Set interface? What are main classes implementing Set interface?

It models the mathematical set in set theory. Set interface is like List interface but with some differences. First, it is not ordered collection. So no ordering is preserved while adding or removing elements. The main feature it does provide is “uniqueness of elements“. It does not support duplicate elements.

Set also adds a stronger contract on the behavior of the equals and hashCode operations, allowing Set instances to be compared meaningfully even if their implementation types differ. Two Set instances are equal if they contain the same elements.

Based on above reasons, it does not have operations based on indexes of elements like List. It only has methods which are inherited by Collection interface.

Main classes implementing Set interface are : EnumSet, HashSet, LinkedHashSet, TreeSet

How HashSet store elements?

You must know that HashMap store key-value pairs, with one condition i.e. keys will be unique. HashSet uses Map’s this feature to ensure uniqueness of elements. In HashSet class, a map declaration is as below:

private transient HashMap map;   //This is added as value for each key private static final Object PRESENT = new Object();

So when you store a element in HashSet, it stores the element as key in map and “PRESENT” object as value. (See declaration above).

public boolean add(E e) { return map.put(e, PRESENT)==null; }

Can a null element added to a TreeSet or HashSet?

As you see, There is no null check in add() method in previous question. And HashMap also allows one null key, so one “null” is allowed in HashSet.

TreeSet uses the same concept as HashSet for internal logic, but uses NavigableMap for storing the elements.

private transient NavigableMap m;   // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object();

NavigableMap is subtype of SortedMap which does not allow null keys. So essentially, TreeSet also does not support null keys. It will throw NullPointerException if you try to add null element in TreeSet

Map interface related

Why we use Map interface? What are main classes implementing Map interface?

Map interface is a special type of collection which is used to store key-value pairs. It does not extend Collection interface for this reason. This interface provides methods to add, remove, search or iterate over various views of Map.

Main classes implementing Map interface are: HashMap, Hashtable, EnumMap, IdentityHashMap, LinkedHashMap and Properties.

What are IdentityHashMap and WeakHashMap?

IdentityHashMap is similar to HashMap except that it uses reference equality when comparing elements. IdentityHashMap class is not a widely used Map implementation. While this class implements the Map interface, it intentionally violates Map’s general contract, which mandates the use of the equals() method when comparing objects. IdentityHashMap is designed for use only in the rare cases wherein reference-equality semantics are required.

WeakHashMap is an implementation of the Map interface that stores only weak references to its keys. Storing only weak references allows a key-value pair to be garbage collected when its key is no longer referenced outside of the WeakHashMap. This class is intended primarily for use with key objects whose equals methods test for object identity using the == operator. Once such a key is discarded it can never be recreated, so it is impossible to do a look-up of that key in a WeakHashMap at some later time and be surprised that its entry has been removed.

How hashmap works?

The most important question which is most likely to be seen in every level of job interviews. You must be very clear on this topic., not only because it is most asked question but also it will open up your mind in further questions related to collection APIs.

Answer to this question is very large and you should read it my post: How HashMap works? For now, lets remember that HashMap works on principle of Hashing. A map by definition is : “An object that maps keys to values”. To store such structure, it uses an inner class Entry:

static class Entry implements Map.Entry { final K key; V value; Entry next; final int hash; ...//More code goes here }

Here key and value variables are used to store key-value pairs. Whole entry object is stored in an array.

/** * The table, re-sized as necessary. Length MUST Always be a power of two. */ transient Entry[] table;

The index of array is calculated on basis on hashcode of Key object

How to design a good key for hashmap?

Another good question usually followed up after answering how hashmap works. Well, the most important constraint is you must be able to fetch the value object back in future. Otherwise, there is no use of having such a data structure. If you understand the working of hashmap, you will find it largely depends on hashCode() and equals() method of Key objects.

So a good key object must provide same hashCode() again and again, no matter how many times it is fetched. Similarly, same keys must return true when compare with equals() method and different keys must return false.

For this reason, immutable classes are considered best candidate for HashMap keys.

Tell the difference questions

Difference between Set and List?

The most noticeable differences are :

• Set is unordered collection where List is ordered collection based on zero based index.
• List allow duplicate elements but Set does not allow duplicates.
• List does not prevent inserting null elements (as many you like), but Set will allow only one null element.

Difference between List and Map?

Perhaps most easy question. List is collection of elements where as map is collection of key-value pairs. There is actually lots of differences which originate from first statement. They have separate top level interface, separate set of generic methods, different supported methods and different views of collection.

I will take much time hear as answer to this question is enough as first difference only.

Difference between HashMap and HashTable?

There are several differences between HashMap and Hashtable in Java:

• Hashtable is synchronized, whereas HashMap is not.
• Hashtable does not allow null keys or values. HashMap allows one null key and any number of null values.
• The third significant difference between HashMap vs Hashtable is that Iterator in the HashMap is a fail-fast iterator while the enumerator for the Hashtable is not.

Difference between Vector and ArrayList?

Lets note down the differences:

• All the methods of Vector is synchronized. But, the methods of ArrayList is not synchronized.
• Vector is a Legacy class added in first release of JDK. ArrayList was part of JDK 1.2, when collection framework was introduced in java.
• By default, Vector doubles the size of its array when it is re-sized internally. But, ArrayList increases by half of its size when it is re-sized.

Difference between Iterator and Enumeration?

Iterators differ from enumerations in three ways:

• Iterators allow the caller to remove elements from the underlying collection during the iteration with its remove() method. You can not add/remove elements from a collection when using enumerator.
• Enumeration is available in legacy classes i.e Vector/Stack etc. whereas Iterator is available in all modern collection classes.
• Another minor difference is that Iterator has improved method names e.g. Enumeration.hasMoreElement() has become Iterator.hasNext(), Enumeration.nextElement() has become Iterator.next() etc.

Difference between HashMap and HashSet?

HashMap is collection of key-value pairs whereas HashSet is un-ordered collection of unique elements. That’s it. No need to describe further.

Difference between Iterator and ListIterator?

There are three Differences are there:

• We can use Iterator to traverse Set and List and also Map type of Objects. But ListIterator can be used to traverse for List type Objects, but not for Set type of Objects.
• By using Iterator we can retrieve the elements from Collection Object in forward direction only whereas ListIterator, which allows you to traverse in either directions using hasPrevious() and previous() methods.
• ListIterator allows you modify the list using add() remove() methods. Using Iterator you can not add, only remove the elements.

Difference between TreeSet and SortedSet?

SortedSet is an interface which TreeSet implements. That’ it !!

Difference between ArrayList and LinkedList?

• LinkedList store elements within a doubly-linked list data structure. ArrayList store elements within a dynamically resizing array.
• LinkedList allows for constant-time insertions or removals, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but grabbing an element in the middle takes time proportional to the size of the list. ArrayLists, on the other hand, allow random access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap.
• LinkedList has more memory overhead than ArrayList because in ArrayList each index only holds actual object (data) but in case of LinkedList each node holds both data and address of next and previous node.