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);

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;
}

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.

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.

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.

The Two Synchronized method Problem

The Two Synchronized method Problem.

Problem Statement: A class has two synchronized (non-static)methods M1 and M2. Two different threads T1 and T2 simultaneously trying to access the methods M1 and M2 respectively.
Is is possible?

import java.util.concurrent.TimeUnit;

public class TwoSyncMethods {

 public static void main(String[] args) {
  // TODO Auto-generated method stub

  
  final TwoSyncMethods tsm = new TwoSyncMethods();
  new Thread(new Runnable() {
   
   @Override
   public void run() {
    try {
     tsm.m1();
    } catch (InterruptedException e) {
     e.printStackTrace();
    }
   }
  }, "One").start();
  
   new Thread(new Runnable() {
   
   @Override
   public void run() {
    try {
     tsm.m2();//Calling other synchronized method on same object
    } catch (InterruptedException e) {
     e.printStackTrace();
    }
    
   }
  }, "Two").start();
  
 }

 public synchronized void m1() throws InterruptedException{
  System.out.println("Acquired by "+Thread.currentThread().getName());
  TimeUnit.SECONDS.sleep(2);  
  System.out.println("Released by "+Thread.currentThread().getName());
  
  
 }
  
 public synchronized void m2() throws InterruptedException
        {
   System.out.println("In Sync "+Thread.currentThread().getName());
   TimeUnit.SECONDS.sleep(5);
   System.out.println("In Sync After time out "+Thread.currentThread().getName());
  
 }
 
}

Answer. No,this is not possible.Two different methods can not access the two different synchronized method of the same class simultaneously.

Explanation : Every object has a monitor associated with it.For a thread to enter the synchronized block (also known as critical section), the thread must be the owner of the lock on the monitor. In other words, a thread must acquire a lock on the monitor if it wants to enter critical section.Now, since both the methods are non-static, therefore if they are called on the same object, the 1st thread, requesting the lock on monitor,will acquire the lock on the monitor while the 2nd thread will have to wait for lock to be released.

How to make it possible? As stated above, since same object is used to call both the methods, therefore once the lock is acquired by any one of the threads will cause the other thread to wait. So the solution to this to make two different objects of the class and then call the two methods simultaneously from the different threads using the different objects. This way, both the threads will acquire lock on the monitor of two different objects.

import java.util.concurrent.TimeUnit;

public class TwoSyncMethods {

 public static void main(String[] args) {
  // TODO Auto-generated method stub

  
  final TwoSyncMethods tsm1 = new TwoSyncMethods();
                final TwoSyncMethods tsm2 = new TwoSyncMethods();
  new Thread(new Runnable() {
   
   @Override
   public void run() {
    try {
     tsm1.m1();
    } catch (InterruptedException e) {
     e.printStackTrace();
    }
   }
  }, "One").start();
  
   new Thread(new Runnable() {
   
   @Override
   public void run() {
    try {
     tsm2.m2();//Calling synchronized methods on different objects
    } catch (InterruptedException e) {
     e.printStackTrace();
    }
    
   }
  }, "Two").start();
  
 }

 public synchronized void m1() throws InterruptedException{
  System.out.println("Acquired by "+Thread.currentThread().getName());
  TimeUnit.SECONDS.sleep(2);  
  System.out.println("Released by "+Thread.currentThread().getName());
  
  
 }
  
 public synchronized void m2() throws InterruptedException
        {
   System.out.println("In Sync "+Thread.currentThread().getName());
   TimeUnit.SECONDS.sleep(5);
   System.out.println("In Sync After time out "+Thread.currentThread().getName());
  
 }
 
}

What is the state of the thread waiting for other thread to exit critical section?
Blocked

public class StateCheck {

    public synchronized void m1() {
        try { Thread.sleep(2000); }
        catch (InterruptedException ie) {}
    }

    public synchronized void m2() {
        try { Thread.sleep(2000); }
        catch (InterruptedException ie) {}
    }

    public static void main(String[] args) throws InterruptedException {
        final StateCheck t = new StateCheck();
        Thread t1 = new Thread() { public void run() { t.m1(); } };
        Thread t2 = new Thread() { public void run() { t.m2(); } };

        t1.start();
        Thread.sleep(500);

        t2.start();
        Thread.sleep(500);

        System.out.println(t2.getState());
    }
}

A thread in the blocked state is waiting for a monitor lock to enter a synchronized block/method or reenter a synchronized block/method after calling Object.wait.