Saturday, 3 December 2016

Intermediate Level(1-3 yrs ) Interview Question based on Java Collections

The collection framework of Java is asked in almost every Java interview. In the last post I shared some of the collection questions which are asked the fresher level or below 1 year of experience. If you haven't gone through that here is the link for that.Java Collection Interview Question(0-1 Years). Below are some of questions that are asked at some experience level.

 

What is the difference between ArrayList and Vector ?


Vector is synchronized while ArrayList is not . Vector is slow while ArrayList is fast . Every time when needed, Vector increases the capacity twice of its initial size while ArrayList increases its ArraySize by 50%.

 

What is the difference between HashMap and Hashtable ?


a. HashMap allows one null key and any number of null values while Hashtable does not allow null keys and null values.
b. HashMap is not synchronized or thread-safe while Hashtable is synchronized or thread-safe .

 

What is the difference between peek(),poll() and remove() method of the Queue interface ?


Both poll() and remove() method is used to remove head object of the Queue. The main difference lies when the Queue is empty().
If Queue is empty then poll() method will return null . While in similar case , remove() method will throw NoSuchElementException .
peek() method retrieves but does not remove the head of the Queue. If queue is empty then peek() method also returns null.

 

What is the difference between Iterator and ListIterator.


Using Iterator we can traverse the list of objects in forward direction . But ListIterator can traverse the collection in both directions that is forward as well as backward.

 

What is the difference between Array and ArrayList in Java ?


a. Array is static in size while ArrayList is dynamic in size.
b. Array can contain primitive data types while ArrayList can not contain primitive data types.When you add any primitive data type to ArrayList, it will automatically convert it to its corresponding Wrapper class(auto Boxing).

 

What is the difference between HashSet and TreeSet ?


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 can not store null object.

 

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 .

 

What is the difference between LinkedList and ArrayList in Java ?


Main differences between LinkedList and ArrayList are :
a. LinkedList is the doubly linked list implementation of list interface , while , ArrayList is the resizable array implementation of list interface.
b. LinkedList can be traversed in the reverse direction using descendingIterator() method  provided by the Java Api developers , while , we need to implement our own method to traverse ArrayList in the reverse direction.

 

Why Map interface does not extend the Collection interface in Java Collections Framework ?


Map interface is not compatible with the Collection interface.
Explanation : Since Map requires key as well as value , for example , if we want to add key-value pair then we will use put(Object key , Object value) . So there are two parameters required to add element to the HashMap object  . In Collection interface add(Object o) has only one parameter.
The other reasons are Map supports valueSet , keySet as well as other appropriate methods which have just different views from the Collection interface.

 

When to use ArrayList and when to use LinkedList in application?


ArrayList has constant time get operation O(1).Hence, ArrayList is preferred when the list is collection required more querying than modifying.
Insertion , Deletion operations take constant time O(1) for LinkedList. Hence, LinkedList is preferred when there are more insertions or deletions involved in the application.

Suggested Posts:

Interview Questions on List Interface 

 

Friday, 25 November 2016

Data Structures - UnderStanding Merge Sort

Data structures is asked in every programming interview. Irrespective of the programming language, data structures and algorithm puzzles are asked in every programming interview.Sorting is one of the most common topic asked in data structures.
 Merge Sort  works on the concept of Divide and Conquer approach.But it doesn't divides the list into two halves. In merge sort the unsorted list is divided into N sublists, each having one element, because a list of one element is considered sorted.

Wednesday, 19 October 2016

Beginners Level(0-1 yrs ) Interview Question based on Java Collections

What is the root interface in collection hierarchy ?
Root interface in collection hierarchy is Collection interface .

What is the difference between Collection and Collections ?
Collection is  an interface while Collections is a java class , both are present in java.util package and  part of java collections framework.

Which collection classes are synchronized or thread-safe ?
Stack, Properties , Vector and Hashtable can be used in multi threaded environment because they are synchronized classes (or thread-safe).

Name the core Collection  interfaces ?
The list of core collection interfaces are : just mention the important ones
Important : Collection , Set , Queue , List , Map
Maps do not extend this interface, yet they are part of java collection framework
Other interface also in the list :  SortedSet, SortedMap , Deque, ListIterator etc.

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 .

What is the difference between Map and Set ?
Map object has unique keys each containing some value, while Set contain only unique values.

What are the classes implementing List and Set interface ?
Class implementing List interface :  ArrayList , Vector , LinkedList ,
Class implementing Set interface :  HashSet , TreeSet

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 the difference between Iterator and Enumeration ?

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 .

Which design pattern followed by Iterator ?
It follows iterator design pattern. Iterator design pattern provides us to navigate through the collection of objects by using a common interface without letting us know about the underlying implementation.
Enumeration is an example of Iterator design pattern.

Which methods you need to override to use any object as key in HashMap ?
To use any object as key in HashMap , it needs to implement equals() and hashCode() method .

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

How to reverse the List in Collections ?
There is a built in reverse method in Collections class . reverse(List list) accepts list as parameter.
Collections.reverse(listobject);

How to convert the array of strings into the list ?
Arrays class of java.util package contains the method asList() which accepts the array as parameter.
So,

String[]  wordArray =  {"Hello" , "World" , "from Java"};
List wordList =  Arrays.asList(wordArray);

Thursday, 13 October 2016

repeatEnd

Home
Goto Problem

Given a string and an int N, return a string made of N repetitions of the last N characters of the string. You may assume that N is between 0 and the length of the string, inclusive.
repeatEnd("Hello", 3) → "llollollo"
repeatEnd("Hello", 2) → "lolo"
repeatEnd("Hello", 1) → "o"

public String repeatEnd(String str, int n)

{
    String res=str.substring(str.length()-n);
    for(int i=1;i<n;i++)
            res=res+str.substring(str.length()-n);
    return res;
}

Tuesday, 11 October 2016

List Interface - An Interview based approach.

List is all about indexes and index based access of elements. The one thing that List has that non-lists don't have is a set of methods related to the index. Those key methods include things like get(int index) , indexOf(Object o) , add(int index, Object obj) , and so on. The three List implementations are ordered by index position—a position that you determine either by setting an object at a specific index or by adding it without specifying position, in which case the object is added to the end. The three List implementations are described in the following sections.

ArrayList : ArrayList can be considered as dynamically resizing array. It gives you fast iteration and fast random access. To state the obvious: it is an ordered collection (by index), but not sorted. It implements RandomAccess interface—a marker interface that says, "this list supports fast (generally constant time) random access.

Vector : Vector is a holdover from the earliest days of Java; Vector and Hashtable were the two original collections, the rest were added with Java 2 versions 1.2 and 1.4. A Vector is basically the same as an ArrayList, but Vector methods are synchronized for thread safety. You'll normally want to use ArrayList instead of Vector because the synchronized methods add a performance hit you might not need. And if you do need thread safety, there are utility methods in class Collections that can help. Vector is the only class other than ArrayList to implement RandomAccess.

LinkedList A LinkedList is ordered by index position, like ArrayList, except that the elements are doubly-linked to one another. This linkage gives you new methods (beyond what you get from the List interface) for adding and removing from the beginning or end, which makes it an easy choice for implementing a  stack or queue. Remenber that a LinkedList may iterate more slowly than an ArrayList, but it's a good choice when you need fast insertion and deletion. As of Java 5, the LinkedList class has been enhanced to implement the java.util.Queue interface. As such, it now supports the common queue methods: peek() , poll() , and offer() .

ArrayList Vs LinkedList
  1.  Both are concrete implementations of List interface. 
  2.  ArrayList provided random access where as LinkedList provide sequential access.
  3.  Both LinkedList and ArrayList maintains the insertion order.
  4. Add operation of ArrayList is slower than that of LinkedList because it may involve resizing of array which requires creating new array and copying elements to new array.
  5. Get Opration of ArrayList is much faster than LinkedList. Time complexity of get operation of ArrayList is O(1) ie. constant time wheres as that of LinkedList is O(n)
  6. Both provide fail-fast iterator and throw concurrent modification exception.
Imporant : ArrayList is preferred when the list manipulation is done less frequently and the get operation is performed more frequently whereas LinkedList is preferred when the frequency of list manipulation is more than the frequency of get operation on the list.

Sunday, 9 October 2016

Understanding Polymorphism in Java

Polymorphism is one of the hot topics for a java interview. Questions, based on polymorphism, are asked at every level in java interview. In java, polymorphism is achieved, when a method with same name but different body are executed under different conditions.Polymorphic method invocations apply only to instance methods. You can always refer to an object with a more general reference variable type (a superclass or interface), but at runtime, the ONLY things that are dynamically selected based on the actual object (rather than the reference type) are instance methods. In java, objects can only be accessed through reference variables. Let us see few important things regarding the reference type variables in java :

  • A reference variable can be of only one type, and once declared, that type can never be changed (although the object it references can change).
  • A reference is a variable, so it can be reassigned to other objects, (unless the reference is declared final ).
  • A reference variable's type determines the methods that can be invoked on the object the variable is referencing.
  • A reference variable can refer to any object of the same type as the declared reference, or—this is the big one—it can refer to any subtype of the declared type!
  • A reference variable can be declared as a class type or an interface type. If the variable is declared as an interface type, it can reference any object of any class that implements the interface.
In java, there are two types of Polymorphism; 1. Runtime Polymorphism(implemented through method overriding). 2. Compile-time polymorphism(implemented through method overloading).

Method Overriding

When a method with same name and same signature is present in both Super class and Sub class, then the method in the super class is called over ridden method and the method in the sub class is called overriding method.Any time you have a class that inherits a method from a superclass, you have the opportunity to override the method. The key benefit of overriding is the ability to define behavior that's specific to a particular subclass type. The following example demonstrates a Horse subclass of Animal overriding the Animal version of the eat() method:

public class Animal {
	public void eat() {
		System.out.println("Eat method of Animal Class");
	}
}
class Horse extends Animal {
	public void eat() {
		System.out.println("Eat method of Horse class");
	}
}
public class TestAnimals 
{
	public static void main (String [] args) {
		Animal a = new Animal();
		Animal b = new Horse(); //Animal ref, but a Horse object
		a.eat(); // Runs the Animal version of eat()
		b.eat(); // Runs the Horse version of eat()
	}
}

In the above example,since,the object creation occurs at run time,therefore which version of eat() to be called is decided at run time.This why it is referred to as runtime polymorphism

Method Overloading

Two methods with same,name in same class but with different signatures will be referred to as as overloaded methods.Overloaded methods let you reuse the same method name in a class, but with different arguments (and optionally, a different return type).


class SumNumber {
	public int getSum(int x, int y) {
		return x + y;
	}
	// Overload the getSum method to add doubles instead of ints
	public double getSum(double x, double y) {
		return x + y;
	}
}

public class TestSum{
	public static void main(String [] args)
	{
		SumNumber sn = new SumNumber();
		System.out.println("Sum of Integer : "+sn.getSum(10, 20));//Integer version of getSum is called
		System.out.println("Sum of Double : "+sn.getSum(10.5, 19.5));//Double version of getSum is called

	}
}

In the above example,which method of get sum is to be called is decided at compile time,based on method signature therefore it is called compile-time polymorphism

Some key take aways and rules regarding method overloading and method overriding

  • Methods can be overridden or overloaded; constructors can be overloaded but not overridden.
  • Abstract methods must be overridden by the first concrete (non-abstract) subclass.
  • With respect to the method it overrides, the overriding method
  • Must have the same argument list.
  • Must have the same return type, except that as of Java 5, the return type can be a subclass—this is known as a covariant return.
  • Must not have a more restrictive access modifier.
  • May have a less restrictive access modifier.
  • Must not throw new or broader checked exceptions.
  • May throw fewer or narrower checked exceptions, or any unchecked exception.
  • final methods cannot be overridden.
  • Only inherited methods may be overridden, and remember that private methods are not inherited.
  • A subclass uses super.overriddenMethodName() to call the superclass version of an overridden method.
  • Overloading means reusing a method name, but with different arguments.
  • Overloaded methods must have different argument lists.
  • Overloaded methods may have different return types, if argument lists are also different.
  • Overloaded methods may have different access modifiers.
  • Overloaded methods may throw different exceptions.
  • Methods from a superclass can be overloaded in a subclass.
  • Polymorphism applies to overriding, not to overloading.
  • Object type (not the reference variable's type), determines which overridden method is used at runtime.
  • Reference type determines which overloaded method will be used at compile time.

Saturday, 8 October 2016

Yield Vs Join and Sleep Vs Wait

In this post, I am going to discuss about some of the important methods of Thread class and their usage.These methods are also actively asked in interviews.There is very little chance that you would have had the experience of actually using them at the starting level.It is expected from all the interviewee to have basic idea about these methods. Before diving straight into the topic, first let us gather some background information which will help us to understand them better.

Understanding thread priorities and thread scheduling

JVM is a preemptive, priority-based scheduler for threads.Each java thread has a well defined priority.A developer can change the priority of the thread as per the requirements.If the user doesn't set the priority of the thread, a default priority is set for each thread which is same for all in a particular java application.This priority value has its significance in multi threaded environment. It helps the JVM to decide which thread to execute when more than one threads are waiting for a common resource.This is why it is called priority based scheduler. The operating system generally chooses the thread with the highest priority. If any high priority thread is ready for the execution then the scheduler interrupts (preempts) the low priority thread. However, there is a catch, the OS may choose to wait the high priority thread and continue wit the lower priority thread(Ya ya... I know, OS some time can be moody -_- ).

  • Remember that all the threads carry normal priority when a priority is not specified.
  • Priorities can be specified from 1 to 10. 10 being the highest, 1 being the lowest priority and 5 being the normal priority.
  • Remember that the thread with highest priority will be given preference in execution. But there is no guarantee that it will be in running state the moment it starts.
  • It can be assumed that the currently executing thread might have the higher priority when compared to the threads in the pool who are waiting for their chance. However as we have learned this is not 100% guaranteed.
  • It is the thread scheduler which decides what thread should be executed.
  • setPriority(Thread.MIN_PRIORITY) method can be used to set the priority of the thread.
  • Remember that the priorities should be set before the threads start method is invoked.
  • Thread class provides some predefined constants for setting the priority, MIN_PRIORITY,MAX_PRIORITY and NORM_PRIORITY.

sleep() is a method which is used to hold the process for the time you wanted but in case of wait() method thread goes in waiting state and it won’t come back automatically until we call the notify() or notifyAll().

The major difference is that wait() releases the lock or monitor while sleep() doesn’t releases any lock or monitor while waiting. Wait is used for inter-thread communication while sleep is used to introduce pause on execution, generally.

Thread.sleep() sends the current thread into the “Not Runnable” state for some amount of time. The thread keeps the monitors it has acquired — i.e. if the thread is currently in a synchronized block or method no other thread can enter this block or method. If another thread calls t.interrupt() it will wake up the sleeping thread. Note that sleep is a static method, which means that it always affects the current thread (the one that is executing the sleep method). A common mistake is to call t.sleep() where t is a different thread; even then, it is the current thread that will sleep, not the t thread.

object.wait() sends the current thread into the “Not Runnable” state, like sleep(), but with a twist. Wait is called on an object, not a thread; we call this object the “lock object.” Before lock.wait() is called, the current thread must synchronize on the lock object; wait() then releases this lock, and adds the thread to the “wait list” associated with the lock. Later, another thread can synchronize on the same lock object and call lock.notify(). This wakes up the original, waiting thread. Basically, wait()/notify() is like sleep()/interrupt(), only the active thread does not need a direct pointer to the sleeping thread, but only to the shared lock object.


yield() is defined as following in Thread.java.

/**
  * A hint to the scheduler that the current thread is willing to yield its current use of a processor. The scheduler is free to ignore
  * this hint. Yield is a heuristic attempt to improve relative progression between threads that would otherwise over-utilize a CPU.
  * Its use should be combined with detailed profiling and benchmarking to ensure that it actually has the desired effect.
  */

public static native void yield();

A yielding thread tells the virtual machine that it’s willing to let other threads be scheduled in its place. This indicates that it’s not doing something too critical. Note that it’s only a hint, though, and not guaranteed to have any effect at all.

join() method

The join() method of a Thread instance can be used to “join” the start of a thread’s execution to the end of another thread’s execution so that a thread will not start running until another thread has ended. If join() is called on a Thread instance, the currently running thread will block until the Thread instance has finished executing.


Giving a timeout within join(), will make the join() effect to be nullified after the specific timeout. When the timeout is reached, the main thread and taskThread are equally probable candidates to execute. However, as with sleep, join is dependent on the OS for timing, so you should not assume that join will wait exactly as long as you specify.

Like sleep, join responds to an interrupt by exiting with an InterruptedException.