Spring MVC Framework Collection API Question - 2

This is the second set of questions that are generally asked for Collection Framework questions. These are a bit more advanced then the earlier set of questions.

Question 1: What is difference between ArrayList and LinkedList?
There are quiet a few difference between ArrayList and LinkedList:

1. ArrayList uses a primitive array to store the values internally. However, LinkedList is made up of nodes where each nodes has three elements: value, pointer to next element and pointer to previous element.
2. ArrayList implements the RandomAccess interface whereas LinkedList does not. RandomAccess is a marker interface which states that the implementation implements the fast algorithm to access the Nth element. So accessing Nth element is fast and takes constant-time for ArrayList whereas LinkedList has to scan the whole list to find the Nth element, hence making it slower for random access.
3. Inserting and deleting an element at the start and end is faster in LinkedList as compared to ArrayList. While inserting an element in the LinkedList at the start and the beginning , we just need to create a node and assign the pointers whereas in ArrayList if you are inserting an element at the start, then first it will copy all the elements in a different list and then adds them after it, similarly while adding an element at the end means ArrayList will have to scan the whole list for inserting an element.
4. LinkedList usually takes more memory than ArrayList as each node in the LinkedList will also store the next and previous pointers.
5. ArrayList may also have issue if your list fills up quiet frequently as the ArrayList will create a new list with increased capacity and then copies all the elements whereas no such thing is required for LinkedList.

Question 2: Where will you use ArrayList and where will you use LinkedList?

If you have add elements at the start and end frequently or iterate over it for deleting elements then you should consider using LinkedList as it requires constant time for these operations and linear-time in ArrayList. If you have to access the positional elements then you should consider using ArrayList as it takes constant time for that and LinkedList take linear time for positional access.

Question 3: What is the difference between HashMap and HashTable?
The main difference is that HashTable is synchronised whereas HashMap is not. You need to provide external synchronisation if you want to synchronise the HashMap. Another difference is that HashTable does not allows null as keys or values whereas HashMap allow one null key and any number of null values.

Question 4: What is the difference between HashMap and TreeMap?
The basic difference is that in TreeMap objects are stored in an order decided either by the natural ordering of key or by the comparator that is defined at the the instantiation time of the TreeMap whereas HashMap does not guarantee any ordering. Since the elements are stored in an order, I think it is safe to say that the insertion of element in TreeMap will be slower as compared to HashMap whereas retrieval will be faster than HashMap.

Question 5: Explain how HashMap works or how the hashcode() and equals() method is used by the HashMap or how the get() method works in HashMap?
This question generally is the starting point for more complicated questions on HashMap. Basically what happens is when we call get(), put() method of HashMap. The HashMap uses the hashcode() method of the key to find the hashcode, then it uses its internal hashing mechanism to find the index of the correct "bucket" where the value might be stored. This bucket contains a list of Map.Entry objects in the form of a linked list. Once the bucket is identified, the map will traverse through the Map.Entry to find the exact key by using equals method, once found it will overwrite or return the value.

Question 6: How is HashSet implemented? or How will you implement the HashSet using HashMap?
Actually if you look closely on the HashMap methods there is already a set in the HashMap, they keySet. It has all the properties like no duplicates (HashMap does not allow duplicate keys). So, all you need to do is following, when you insert an object in HashSet, you insert the object as key in the HashMap and put the value as an EMPTY object. Same is the case when retrieving a value from HashSet, rather returning a value just return the key.

Question 7: Is Collection.synchronisedMap() is really thread-safe?
Question 8: What is the difference between ArrayList and Vector?
As per the Java API, the main difference between the ArrayList and Vector is that Vector is synchronised whereas ArrayList is not. The other difference is the way there size is incremented, Vector always doubles the size whereas ArrayList increases the size by half the initial capacity. So if there is a need for thread-safety is advisable to use Vector but since synchronisation takes a hit on the performance we may consider using the ArrayList and synchronise it using the Collections utility class.

Question 9: What are the mandatory  methods you should override while using TreeMap and why?

Spring MVC Framework Collection API Questions - 1

Java Collection Framework is one of the hot favourite among interviewers. The reason for that is any Java program uses Java Collection Framework intensively and any manager hiring for his team would like to see that you have basic and some advanced knowledge in the Collection API. Other reason that I find for interest in Collection Framework is that the questions will help in identifying whether the candidate knows how the various Data Structures are implemented in Java explaining his interest. 

In this post I will try to list some of the beginner to advanced level questions asked on the Collection Framework.

Question 1: What is the Java's collection API?

Java's Collection API is a unified architecture of interfaces, classes and algorithms that are required for representing and manipulation of Collections. For example, List, Map, Set and the like. Benefit of these classes is as follows:

1.        It reduces the programming effort for the developers.

2.        It increases the program speed and quality, since the Collection API provides the high-performance and high quality implementation of the data structure and the algorithms required for their manipulation.

2.        It increase software re-usability.

3.        Reduces efforts to learn and create basic data structures API’s

An excerpt from the Java's Collection Trail 

Question 2: What are the basic interfaces in the Collection API?
Basic interfaces in the collection API are:

1. Collection: This is the parent interface and all other interfaces extend this interface.

2. Set: This is a core interface to represent a mathematical set, the basic thing about a set is it 

             does not have duplicate values and at most have one null value.

3. List: An ordered collection or sequence, the user of this interface has precise control over 

            where each element is inserted. The user can access each element by its index /  

            position. It differs from the set in the way, that it allows duplicates and null values.

4. Queue: This is a collection used to hold multiple elements prior to processing. Queues 

                  typically, but do not necessarily, order elements in a FIFO (first-in, first-out) manner. 

                 Among the exceptions are priority queues, which order elements according to a  

                 supplied comparator or the elements' natural ordering. Whatever the ordering used, 

                 the head of the queue is the element that would be removed by a call to remove or  

                 poll. In a FIFO queue, all new elements are inserted at the tail of the queue. Other 

                 kinds of queues may use different placement rules.

5. Map: This is a collection of key-value pair. A Map cannot contain duplicate keys; each key 

              can map to at most one value.

The other two core interfaces are merely sorted versions of set and map.

1. SortedSet: This is a Set that maintains its elements in ascending order. Several additional  

                        operations are provided to take advantage of the ordering.

2. SortedMap: This is a Map that maintains its mappings in ascending key order.

Their hierarchy is depicted in the below diagram.

Question 3: What is the difference between Set and List?
The basic difference between a Set and List is that set does not allow duplicates and allows at most one null value. Also, List is an ordered collection of elements whereas set is an unordered collection of elements.

Question 4: Why doesn't Map interface extend Collection?
Theoretically, let us assume that Map extends Collection, So what exactly are the elements of this collection? The only answer to this is "key-value" pair. But you cannot really iterate over these elements without knowing the value of key. However, Map can be viewed as a collection of the keys, values, key-value pair or entrySets. Depicting this behaviour Map does provide the collection view method keySets(), values(), entrySets().

Similary, if the Collection interface extends Map interface, then what are the keys of these elements. There is no satisfactory example.While it is possible to view List as a possible map with the indices as the keys, this has a property that when you remove an element from the List, it changes the keys of the elements preceding it and hence the reason that we don't have Map view operations on the list.

Question 5: Why doesn't Collection extends Cloneable or Serializable interface?
The only answer I can think of is that it is rarely required to clone or serialize the whole collection. There are serializable / cloneable implementations of the Collection. So, if the user want to create a Cloneable/Serializable collection, he can create a generic collection and then can use addAll() to insert the collection in a cloneable / serializable collection implementation.

Question 6: What are the other useful interfaces in Collection Framework?
Other useful interfaces are:

• Iteration : Enumerator, Iterator, ListIterator
• Ordering: Comparable, Comparator
• Performance: RandomAccess

Question 7: What is the difference between Enumerator, Iterator and ListIterator?

Property	Enumeration	Iterator	ListIterator
Number of method	2	3	9
Method names	hasMoreElements(), nextElement()	hasNext(), next(), remove().	add(), hasNext(), next(), hasPrevious(), previous(), nextIndex(), previousIndex(), set(),remove().
Access Direction	Forward-only	Forward only	Bi-directional
Summary	It provides a read only traversal of the collection. Legacy classes such as Vector and HashTable returns this	Iterator provides a method to remove an element from the iterator. Java Collection Framework classes return this.	It provides a bi-directional access on the collection and hence has methods to support it, like previous() and next(). It also allows the modification of elements using set() and add() operation.