Collections Java Interview Questions – Set 02

by

What is the Collections API?

The Collections API is a set of classes and interfaces that support operations on collections of objects.

What is an Iterator interface?

The Iterator interface is used to step through the elements of a Collection.

The Iterator is an interface, used to traverse through the elements of a Collection. It is not advisable to modify the collection itself while traversing an Iterator.

What’s the main difference between ArrayList / HashMap and Vector / Hashtable?

Vector / HashTable are synchronized which means they are thread safe. Cost of thread safe is performance degradation. So if you are sure that you are not dealing with huge number of threads then you should use ArrayList / HashMap.But yes you can stillsynchronize List and Map’s using Collections provided methods :-

  • List OurList = Collections.synchronizedList (OurList);
  • Map OurMap = Collections.synchronizedMap (OurMap);

What is the List interface?

The List interface provides support for ordered collections of objects.

What is the difference between ArrayList and LinkedList? (ArrayList vs LinkedList.

when the internal array fills up. The arrayList has to create a new array and copy all the elements there. The ArrayList has a growth algorithm of (n*3)/2+1, meaning that each time the buffer is too small it will create a new one of size (n*3)/2+1 where n is the number of elements of the current buffer. Hence if we can guess the number of elements that we are going to have, then it java.util.ArrayList and java.util.LinkedList are two Collections classes used for storing lists of object references Here are some key differences:

  • ArrayList uses primitive object array for storing objects whereas LinkedList is made up of a chain of nodes. Each node stores an element and the pointer to the next node. A singly linked list only has pointers to next. A doubly linked list has a pointer to the next and the previous element. This makes walking the list backward easier.
  • ArrayList implements the RandomAccess interface, and LinkedList does not. The commonly used ArrayList implementation uses primitive Object array for internal storage. Therefore an ArrayList is much faster than a LinkedList for random access, that is, when accessing arbitrary list elements using the get method. Note that the get method is implemented for LinkedLists, but it requires a sequential scan from the front or back of the list. This scan is very slow. For a LinkedList, there’s no fast way to access the Nth element of the list.
  • Adding and deleting at the start and middle of the ArrayList is slow, because all the later elements have to be copied forward or backward. (Using System.arrayCopy()) Whereas Linked lists are faster for inserts and deletes anywhere in the list, since all you do is update a few next and previous pointers of a node.
  • Each element of a linked list (especially a doubly linked list) uses a bit more memory than its equivalent in array list, due to the need for next and previous pointers.
  • ArrayList may also have a performance issue makes sense to create a arraylist with that capacity during object creation (using construtor new ArrayList(capacity)). Whereas LinkedLists should not have such capacity issues.

What is HashMap and Map

Map is Interface which is part of Java collections framework. This is to store Key Value pair, and Hashmap is class that implements that using hashing technique.

what is Enumeration in java

An enumeration is an object that generates elements one at a time, used for passing through a collection, usually of unknown size. The traversing of elements can only be done once per creation.

What are some of the best practices relating to the Java Collection framework

Best practices relating to Java Collection framework are as follow:

  • Choose the right type of data structure based on usage patterns like fixed size or required to grow, duplicates allowed or not, ordering is required to be maintained or not, traversal is forward only or bi-directional, inserts at the end only or any arbitrary position, more inserts or more reads, concurrently accessed or not, modification is allowed or not, homogeneous or heterogeneous collection, etc. Also, keep multi-threading, atomicity, memory usage and performance considerations discussed earlier in mind.
  • Don’t assume that your collection is always going to be small as it can potentially grow bigger with time. So your collection should scale well.
  • Program in terms of interface not implementation: For example, you might decide a LinkedList is the best choice for some application, but then later decide ArrayList might be a better choice for performance reason.
    • Bad:
      • ArrayList list = new ArrayList(100);
    • Good:

// program to interface so that the implementation can change

  • List list = new ArrayList(100);
  • List list2 = new LinkedList(100);
  • Return zero length collections or arrays as opposed to returning a null in the context of the fetched list is actually empty. Returning a null instead of a zero length collection is more error prone, since the programmer writing the calling method might forget to handle a return value of null.
    • List emptyList = Collections.emptyList( );
    • Set emptySet = Collections.emptySet( );
  • Use generics for type safety, readability, and robustness.
  • Encapsulate collections: In general, collections are not immutable objects. So care should be taken not to unintentionally expose the collection fields to the caller. The caller may not perform any necessary validation.

Where will you use Vector and where will you use ArrayList

The basic difference between a Vector and an ArrayList is that, vector is synchronized while ArrayList is not. Thus whenever there is a possibility of multiple threads accessing the same instance, one should use Vector. While if not multiple threads are going to access the same instance then use ArrayList. Non synchronized data structure will give better performance than the synchronized one.

What are the common data structures, and where would you use them? How you would go about implementing your own List, Set, and Map

Many leave out Trees and Graphs. Trees and Graphs are very useful data structures as well.Whilst it is not recommended to write your own implementation when Java provides proven and tested implementations, the interviewer is testing your understanding on data structures. My book entitled “Core Java Career Essentials” covers this in more detail with diagrams, examples, and code.

Here are the common data structures.

Arrays are the most commonly used data structure. Arrays are of fixed size, indexed, and all containing elements are of the same type (i.e. a homogenous collection). For example, storing employee details just read from the database as EmployeeDetail[ ], converting and storing a string as a byte array for further manipulation or processing, etc. Wrap an array in a class to protect it from being inadvertently altered. This would be true for other data structures as well.

Lists are known as arrays that can grow. These data structures are generally backed by a fixed sized array and they re-size themselves as necessary. A list can have duplicateelements. For example,  adding new line items to an order that stores its line items as a list, removing all expired products from a list of products, etc. Initialize them with an appropriate initial size to minimize the number of re-sizes

Sets are like lists but they do not hold duplicate elements. Sets can be used when you have a requirement to store unique elements.

Stacks allow access to only one data item, which is the last item inserted (i.e. Last In First Out – LIFO). If you remove this item, you can access the next-to-last item inserted, and so on. The LIFO is achieved through restricting access only via methods like peek( ), push( ), and pop( ). This is useful in many programing situations like parsing mathematical expressions like (4+2) * 3, storing methods and exceptions in the order they occur, checking your source code to see if the brackets and braces are balanced properly, etc.

The LIFO access mechanism used by a stack has many practical uses.  For example, Evaluation of expressions / syntax Parsing, validating and parsing XML, undo sequence in a text editor, pages visited history in a web browser, etc. Java interview questions and answers on stack data structure.

Queues are somewhat like a stack, except that in a queue the first item inserted is the first to be removed (i.e. First In First Out – FIFO). The FIFO is achieved through restricting access only via methods like peek( ), offer( ), and poll( ). For example,  waiting in a line for a bus, a queue at the bank or super market teller, etc.

LinkedLists are data structures made of nodes, where each node contains data and a reference to the next node, and possibly to the previous node as well for a doubly linked list. For example, a stack or queue can be implemented with a linked list or a doubly linked list because you can insert and delete at both ends. There would also be other situations where data will be frequently inserted and deleted from the middle. The Apache library provides a TreeListimplementation, which is a good replacement for a LinkedList as it performs much better than a LinkedList at the expense of using a little more memory.  This means a LinkedList is rarely a good choice of implementation.

ArrayList is a good general purpose list implementation. An ArrayList is faster than a TreeList for most operations except inserting and removing in the middle of the list. A TreeList implementation utilizes a tree structure internally to ensure that all insertions and removals are O(log n). This provides much faster performance than both an ArrayList and a LinkedListwhere elements are inserted and removed repeatedly from anywhere.

class Link

{

private int id;                    // data

private String name;               // data

private Link next;                 // reference to next link

}

HashMaps are amortized constant-time access data structures that map keys to values. This data structure is backed by an array. It uses a hashing functionality to identify a location, and some type of collision detection algorithm is used to handle values that hash to the same location. For example, storing employee records with employee number as the key, storing name/value pairs read from a properties file, etc. Initialize them with an appropriate initial size to minimize the number of re-sizes.

Trees are the data structures that contain nodes with optional data elements and one or more child elements, and possibly each child element references the parent element to represent a hierarchical or ordered set of data elements.  For example, a hierarchy of employees in an organization, storing the XML data as a hierarchy, etc.  If every node in a tree can have utmost 2 children, the tree is called a binary tree. The binary trees are very common because the shape of a binary tree makes it easy to search and insert data. The edges in a tree represent quick ways to navigate from node to node.

list.

Java does not provide an implementation for this but it can be easily implemented as shown below. Just make a class Node with an ArrayList holding links to other Nodes.

package bigo;

import java.util.ArrayList;

import java.util.List;

public class Node {

private String name;

private List<node> children = new ArrayList<node>( );

private Node parent;

public Node getParent( ) {

return parent;

}

public void setParent(Node parent) {

this.parent = parent;

}

public Node(String name) {

this.name = name;

}

public void addChild(Node child) {

children.add(child);

}

public void removeChild(Node child) {

children.remove(child);

}

public String toString( ) {

return name;

}

}

Graphs are data structures that represent arbitrary relationships between members of any data sets that can be represented as networks of nodes and edges. A tree structure is essentially a more organized graph where each node can only have one parent node. Unlike a tree, a graph’s shape is dictated by a physical or abstract problem. For example,nodes (or vertices)  in a graph may represent cities, while edges may represent airline flight routes between the cities.

To make a Java graph class, you will have to work out the way in which the information can be stored and accessed. A graph will be using some of the data structures mentioned above. The Java API does not provide an implementation for this. But there are a number of third party libraries like  JUNG, JGraphT, and JDSL (does not seem to support generics).The book “Core Java Career Essentials” covers working examples using Java.