Wednesday, August 3, 2016

Collections Interview Questions

What are Collection related features in Java 8?
Java 8 has brought major changes in the Collection API. Some of the changes are:
·         Java Stream API collection classes for supporting sequential as well as parallel processing
·          Iterable interface is extended with forEach() default method that we can use to iterate over a collection. It is very helpful when used with lambda expressions  because it’s argument Consumer is a function interface.
·         Miscellaneous Collection API improvements such as forEachRemaining(Consumer action)method in Iterator interface, Map replaceAll(), compute(), merge() methods.

What is Java Collections Framework? List out some benefits of Collections framework?
Collection Framework is representing a unified architecture for storing and manipulating the group of objects. Using collection framework, you can store the objects as a list or as a set or as a queue or as a map and perform operations like adding an object or removing an object or sorting the objects without much hard work. 

Some of the benefits of collections framework are
1.      Reduced development effort by using core collection classes rather than implementing our own collection classes.
2.      Code quality is enhanced with the use of well tested collections framework classes.
3.      Reduced effort for code maintenance by using collection classes shipped with JDK.
4.      Reusability and Interoperability

What is the benefit of Generics in Collections Framework?
Java 1.5 came with Generics and all collection interfaces and implementations use it heavily. Generics allow us to provide the type of Object that a collection can contain, so if you try to add any element of other type it throws compile time error.
This avoids ClassCastException at Runtime because you will get the error at compilation. Also Generics make code clean since we don’t need to use casting and instanceof operator.

What are the basic interfaces of Java Collections Framework?
Collection is the root of the collection hierarchy. A collection represents a group of objects known as its elements. The Java platform doesn’t provide any direct implementations of this interface.
Set is a collection that cannot contain duplicate elements. This interface models the mathematical set abstraction and is used to represent sets, such as the deck of cards.
List is an ordered collection and can contain duplicate elements. You can access any element from it’s index. List is more like array with dynamic length.
Map is an object that maps keys to values. A map cannot contain duplicate keys: Each key can map to at most one value.
Some other interfaces are QueueDequeueIteratorSortedSetSortedMap and ListIterator.

Why Collection doesn’t extend Cloneable and Serializable interfaces?
 “there is no need to do it “. Extending an interface simply means that you are creating a subtype of interface, in other words a more specialized behavior and Collection interface is not expected to do what Cloneable and Serializable interfaces do.

Another reason is that not everybody will have a reason to have Cloneable collection because if it has very large data, then every unnecessary clone operation will consume a big memory. Beginners might use it without knowing the consequences.

Another reason is that Cloneable and Serializable are very specialized behavior and so should be implemented only when required. For example, many concrete classes in collection implement these interfaces. So if you want this feature. use these collection classes otherwise use their alternative classes.

Why Map interface doesn’t extend Collection interface?
because they are incompatible “. Collection has a method add(Object o). Map cannot 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.
Due to such big differences, Collection interface was not used in Map interface, and it was built in separate hierarchy.

What is an Iterator?
Iterator is an interface. It is found in java.util package. It provides methods to iterate over any Collection.

What is difference between Enumeration and Iterator interface?
The main difference between Iterator and Enumeration is that Iterator has remove() method while Enumeration doesn't.
Hence , using Iterator we can manipulate objects by adding and removing the objects from the collections. Enumeration behaves like a read only interface as it can only traverse the objects and fetch it.

Why there is not method like Iterator.add() to add elements to the collection?
The sole purpose of an Iterator is to enumerate through a collection. All collections contain the add() method to serve your purpose. There would be no point in adding to an Iterator because the collection may or may not be ordered. And add() method can not have same implementation for ordered and unordered collections.

What are different ways to iterate over a list?
You can iterate over a list using following ways:
  • Iterator loop
  • For loop
  • For loop (Advance)
  • While loop
What is the difference between List and Set?
Set contain only unique elements while List can contain duplicate elements.
Set is unordered while List is ordered. List maintains the order in which the objects are added.
List does not prevent inserting null elements (as many you like), but Set will allow only one null element.

Difference between Vector and ArrayList?
  • 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. 
What is difference between ArrayList and LinkedList?
ArrayList and LinkedList both implement List interface but there are some differences between them.
1.      ArrayList is an index based data structure backed by Array, so it provides random access to its elements with performance as O(1) but LinkedList stores data as list of nodes where every node is linked to its previous and next node. So even though there is a method to get the element using index, internally it traverse from start to reach at the index node and then return the element, so performance is O(n) that is slower than ArrayList.
2.      Insertion, addition or removal of an element is faster in LinkedList compared to ArrayList because there is no concept of resizing array or updating index when element is added in middle.
3.      LinkedList consumes more memory than ArrayList because every node in LinkedList stores reference of previous and next elements.

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 an 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.

What is the difference between Queue and Stack?
Queue is a data structure which is based on FIFO (first in first out) property. An example of Queue in real world is buying movie tickets in the multiplex or cinema theatres.
Stack is a data structure which is based on LIFO (last in first out) property. An example of Stack in real world is insertion or removal of CD from the CD case.

What is different between Iterator and ListIterator?
1.      We can use Iterator to retrieve Set and List collections whereas ListIterator can be used with Lists only.
2.      Iterator can retrieve in forward direction only whereas ListIterator can be used to retrieve in both the directions.
3.      ListIterator inherits from Iterator interface and comes with extra functionalities like adding an element, replacing an element, getting index position for previous and next elements.

What are different ways to iterate over a list?
We can iterate over a list in two different ways – using iterator and using for-each loop.
List strList = new ArrayList<>();
//using for-each loop
for(String obj : strList){
    System.out.println(obj);
}

//using iterator
Iterator it = strList.iterator();
while(it.hasNext()){
    String obj = it.next();
    System.out.println(obj);
}
Using iterator is more thread-safe because it makes sure that if underlying list elements are modified, it will throw ConcurrentModificationException.

What do you understand by iterator fail-fast property?
Iterator fail-fast property checks for any modification in the structure of the underlying collection everytime we try to get the next element. If there are any modifications found, it throwsConcurrentModificationException. All the implementations of Iterator in Collection classes are fail-fast by design except the concurrent collection classes like ConcurrentHashMap and CopyOnWriteArrayList.

What is difference between fail-fast and fail-safe?
Iterator fail-safe property work with the clone of underlying collection, hence it’s not affected by any modification in the collection. By design, all the collection classes in java.util package are fail-fast whereas collection classes in java.util.concurrent are fail-safe.
Fail-fast iterators throw ConcurrentModificationException whereas fail-safe iterator never throws ConcurrentModificationException.

How to avoid ConcurrentModificationException while iterating a collection?
We can use concurrent collection classes to avoid ConcurrentModificationException while iterating over a collection, for example CopyOnWriteArrayList instead of ArrayList.

What is the difference between HashSet and TreeSet ?

Main differences between HashSet and TreeSet are :
a.  HashSet maintains the inserted elements in random order while TreeSet maintains elements in the sorted order
b. HashSet can store null object while TreeSet cannot store null object.

How HashMap works in Java?
HashMap stores key-value pair in Map.Entry static nested class implementation. HashMap works on hashing algorithm and uses hashCode() and equals() method in put and get methods.
When we call put method by passing key-value pair, HashMap uses Key hashCode() with hashing to find out the index to store the key-value pair. The Entry is stored in the LinkedList, so if there are already existing entry, it uses equals() method to check if the passed key already exists, if yes it overwrites the value else it creates a new entry and store this key-value Entry.
When we call get method by passing Key, again it uses the hashCode() to find the index in the array and then use equals() method to find the correct Entry and return it’s value. 

The other important things to know about HashMap are capacity, load factor, threshold resizing. HashMap initial default capacity is 16 and load factor is 0.75. Threshold is capacity multiplied by load factor and whenever we try to add an entry, if map size is greater than threshold, HashMap rehashes the contents of map into a new array with a larger capacity. The capacity is always power of 2, so if you know that you need to store a large number of key-value pairs, for example in caching data from database, it’s good idea to initialize the HashMap with correct capacity and load factor.

What is the importance of hashCode() and equals() methods?
HashMap uses Key object hashCode() and equals() method to determine the index to put the key-value pair. These methods are also used when we try to get value from HashMap. If these methods are not implemented correctly, two different Key’s might produce same hashCode() and equals() output and in that case rather than storing it at different location, HashMap will consider them same and overwrite them.
Similarly all the collection classes that doesn’t store duplicate data use hashCode() and equals() to find duplicates, so it’s very important to implement them correctly. The implementation of equals() and hashCode() should follow these rules.
    • If o1.equals(o2), then o1.hashCode() == o2.hashCode()should always be true.
    • If o1.hashCode() == o2.hashCode is true, it doesn’t mean that o1.equals(o2) will be true.
Can we replace Hashtable with ConcurrentHashMap?
Yes, we can replace Hashtable with ConcurrentHashMap and that's what suggested in Java documentation of ConcurrentHashMap. but you need to be careful with code which relies on locking behavior of Hashtable. Since Hashtable locks whole Map instead of a portion of Map, compound operations like if(Hashtable.get(key) == null) put(key, value) works in Hashtable but not in concurrentHashMap. instead of this use putIfAbsent() method of ConcurrentHashMap

What is difference between HashMap and Hashtable?
HashMap and Hashtable both implements Map interface and looks similar, however there are following difference between HashMap and Hashtable.
1.      HashMap allows null key and values whereas Hashtable doesn’t allow null key and values.
2.      Hashtable is synchronized but HashMap is not synchronized. So HashMap is better for single threaded environment, Hashtable is suitable for multi-threaded environment.
3.      LinkedHashMap was introduced in Java 1.4 as a subclass of HashMap, so in case you want iteration order, you can easily switch from HashMap to LinkedHashMap but that is not the case with Hashtable whose iteration order is unpredictable.
4.      HashMap provides Set of keys to iterate and hence it’s fail-fast but Hashtable provides Enumeration of keys that doesn’t support this feature.
5.      Hashtable is considered to be legacy class and if you are looking for modifications of Map while iterating, you should use ConcurrentHashMap

How to decide between HashMap and TreeMap?
For inserting, deleting, and locating elements in a Map, the HashMap offers the best alternative. If, however, you need to traverse the keys in a sorted order, then TreeMap is your better alternative. Depending upon the size of your collection, it may be faster to add elements to a HashMap, then convert the map to a TreeMap for sorted key traversal.

What are different Collection views provided by Map interface?
Map interface provides 3 views of key-values pairs stored in it:
  • key set view
  • value set view
  • entry set view
All the views can be navigated using iterators.

What is the difference between HashMap and ConcurrentHashMap?
Main differences between HashMap and ConcurrentHashMap are:
a. HashMap is not synchronized while ConcurrentHashMap is synchronized.
b. HashMap can have one null key and any number of null values while ConcurrentHashMap does not allow null keys and null values 

How do you use a custom object as key in Collection classes like HashMap ?
If one is using the custom object as key then one needs to override equals() and hashCode() method and one also need to fulfil the contract.
If you want to store the custom object in the SortedCollections like SortedMap then one needs to make sure that equals() method is consistent to the compareTo() method. If inconsistent, then collection will not follow their contracts, that is, Sets may allow duplicate elements.

What is hash-collision in Hashtable? How it was handled in Java?
In Hashtable , if two different keys have the same hash value then it lead to hash -collision. A bucket of type linkedlist used to hold the different keys of same hash value.

What is EnumSet?
java.util.EnumSet is Set implementation to use with enum types. All of the elements in an enum set must come from a single enum type that is specified, explicitly or implicitly, when the set is created. EnumSet is not synchronized and null elements are not allowed. It also provides some useful methods like copyOf(Collection c), of(E first, E… rest) and complementOf(EnumSet s).

What is IdentityHashMap?
IdentityHashMap is a class present in java.util package. It implements the Map interface with a hash table , using reference equality instead of object equality when comparing keys and values.In other words , in IdentityHashMap two keys k1 and k2 are considered equal if only if (k1==k2).
IdentityHashMap is not synchronized.
Iterators returned by the iterator() method are fail-fast , hence , will throw ConcurrentModificationException. 

What is WeakHashMap? 
WeakHashMap is a class present in java.util package similar to IdentityHashMap. It is a Hashtable based implementation of Map interface with weak keys. An entry in WeakHashMap will automatically be removed when its key is no longer in ordinary use. More precisely the presence of a mapping for a given key will not prevent the key from being discarded by the garbage collector.
It permits null keys and null values.
Like most collection classes this class is not synchronized. A synchronized WeakHashMap may be constructed using the Collections.synchronizedMap() method.
Iterators returned by the iterator() method are fail-fast , hence , will throw ConcurrentModificationException

How will you make Collections readOnly ?
We can make the Collection readOnly by using the following lines code:
General : Collections.unmodifiableCollection(Collection c)

Collections.unmodifiableMap(Map m)
Collections.unmodifiableList(List l)
Collections.unmodifiableSet(Set s)

What are concurrent Collection Classes?
Java 1.5 Concurrent package (java.util.concurrent) contains thread-safe collection classes that allow collections to be modified while iterating. By design Iterator implementation in java.utilpackages are fail-fast and throws ConcurrentModificationException. But Iterator implementation injava.util.concurrent packages are fail-safe and we can modify the collection while iterating. Some of these classes are CopyOnWriteArrayList, ConcurrentHashMap, CopyOnWriteArraySet.

What is BlockingQueue?
java.util.concurrent.BlockingQueue is a Queue that supports operations that wait for the queue to become non-empty when retrieving and removing an element, and wait for space to become available in the queue when adding an element.
BlockingQueue interface is part of java collections framework and it’s primarily used for implementing producer consumer problem. We don’t need to worry about waiting for the space to be available for producer or object to be available for consumer in BlockingQueue as it’s handled by implementation classes of BlockingQueue.
Java provides several BlockingQueue implementations such as ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue, SynchronousQueue etc.

What is Queue and Stack, list their differences?
Both Queue and Stack are used to store data before processing them. java.util.Queue is an interface whose implementation classes are present in java concurrent package. Queue allows retrieval of element in First-In-First-Out (FIFO) order but it’s not always the case. There is also Deque interface that allows elements to be retrieved from both end of the queue.
Stack is similar to queue except that it allows elements to be retrieved in Last-In-First-Out (LIFO) order.
Stack is a class that extends Vector whereas Queue is an interface.

What is difference between Comparable and Comparator interface?
Comparable and Comparator interfaces are used to sort collection or array of objects.

  • Comparable Interface is actually from java.lang package.
  • It will have a method compareTo(Object obj)to sort objects
  • Comparator Interface is actually from java.util package.
  • It will have a method compare(Object obj1, Object obj2)to sort objects
 Comparable interface is used to provide the natural sorting of objects and we can use it to provide sorting based on single logic.
Comparator interface is used to provide different algorithms for sorting and we can choose the comparator we want to use to sort the given collection of objects.

How can we sort a list of Objects?
If we need to sort an array of Objects, we can use Arrays.sort(). If we need to sort a list of objects, we can use Collections.sort(). Both these classes have overloaded sort() methods for natural sorting (using Comparable) or sorting based on criteria (using Comparator).
Collections internally uses Arrays sorting method, so both of them have same performance except that Collections take sometime to convert list to array.

What is Big-O notation? Give some examples?
The Big-O notation describes the performance of an algorithm in terms of number of elements in a data structure. Since Collection classes are actually data structures, we usually tend to use Big-O notation to choose the collection implementation to use based on time, memory and performance.
Example 1: ArrayList get(index i) is a constant-time operation and doesn’t depend on the number of elements in the list. So it’s performance in Big-O notation is O(1).
Example 2: A linear search on array or list performance is O(n) because we need to search through entire list of elements to find the element.

What is CopyOnWriteArrayList?  How it is different from ArrayList in Java?
CopyOnWriteArrayList is a thread safe variant of ArrayList   in which all mutative operations like add, set are implemented by creating a fresh copy of the underlying array.
It guaranteed not to throw ConcurrentModificationException.
It permits all elements including null. It is introduced in jdk 1.5 

What is UnsupportedOperationException?
This exception is thrown on invoked methods which are not supported by actual collection type.
For example, if you make a read-only list list using “Collections.unmodifiableList(list)” and then call add() or remove() method, what should happen. It should clearly throw UnsupportedOperationException.

Which collection classes provide random access of it’s elements?
ArrayList, HashMap, TreeMap, Hashtable classes provide random access to it’s elements.



No comments:

Post a Comment