JavaByPatel: Data structures and algorithms interview questions in Java: March 2019

Sunday, 31 March 2019

Check if a Binary Tree is a Mirror Image or Symmetric in Java.

Check if a Binary Tree is a Mirror Image or Symmetric..

Check if a given binary tree is a symmetric or you can also say check whether tree is a mirror of itself (ie, symmetric around its center)

Lets see sample input and output:

Saturday, 30 March 2019

Find Container with Most Water in Java

Find Container with Most Water.

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You cannot slant the container.

Lets understand what is the input and the expected output.

Friday, 29 March 2019

Find Power of a Number using Recursion in Java

Find Power of a Number using Recursion in Java.

Given two integers base and number, write a function to compute base^number.
Assume that base and number are small and will not cause integer overflow.

Lets understand what is the input and the expected output.

Find length of longest substring without repeating characters in Java

Length of the longest substring without repeating characters in Java.

Given a string, find the length of the longest unique substring.

Lets understand what is the input and the expected output.

Maximum consecutive one’s in a binary array

Find the maximum consecutive 1's in an array of 0's and 1's. And Find length of the longest consecutive One's in binary representation.

Given a binary array, find the maximum number of consecutive 1s in this array or find the maximum consecutive 1's in an array of 0's and 1's.

Lets understand what is the input and the expected output.

Thursday, 28 March 2019

Find sum of digits of a number until sum becomes single digit

Find sum of digits of a number until sum becomes single digit.

Given a non-negative integer, repeatedly add all its digits until the result has only one digit.
Lets understand what is the input and the expected output.

Hamming distance between two Integers in Java.

Given two integers, find the hamming distance between them.

Hamming Distance: hamming distance is the count of bits that are different at same position in a binary representation of two numbers.

Lets understand what is the input and the expected output.

Check if a binary tree is subtree of another binary tree

Check if a binary tree is subtree of another binary tree.

Given two binary trees, check if the first tree is subtree of the second one.
A tree is called subtree if all the nodes and its child of the subtree(S) is present in Tree(T) in the same structure.

Lets understand what is the input and the expected output.

Find element in a sorted array whose frequency is greater than or equal to n/2.

Find Majority Element in a Sorted Array in Java? OR Find element in a sorted array whose frequency is greater than or equal to n/2.

Given a sorted array, find the number in array that appears more than or equal to n/2 times.
Condition: there will always be element which is repeated more than n/2 times.

Lets understand with the help of example below,

Try to solve the problem in less than O(1) complexity.

Algorithm

If the element is sorted and such element is always present which is repeated more than n/2 times in that case the repeated element must be the middle element of the array.

If the most repeated element is starting from 0th index, in that case it has to stretch till middle index then only it will be repeated n/2 times,

If the most repeated element is present at last index, if that is the case than middle index should also contain the same element than only it would have be repeated n/2 times,

If the most repeated starts some where in the middle in this case it is sure it would be passing from the middle index for having its count greater than or equal to n/2 times.

package com.javabypatel.arrays;

public class MajorityOfElementInSortedArray {

    public static void main(String args[]) {
        int arr[] = { 1, 2, 3, 3 };
        int n = arr.length;
        System.out.println(findMajorityElement(arr, n));
    }
    public static int findMajorityElement(int arr[], int n) {
        return arr[n / 2];
    }
}

Check Majority Element in a Sorted Array in Java.

Majority Element in a Sorted Array in Java?

Given a sorted array, we need to find if a given x is a majority element.

What is Majority element: Number occurring more than half the size of the array is called Majority element.

Lets understand with the help of example below,

Try to solve the problem in less than O(N) complexity.

Algorithm

We will see two solutions one having time complexity O(N) and one using Binary Search approach having time complexity O(log N).

As the array is sorted we can use binary search to find the index of first occurrence of element to search and once that is found, we can directly add n/2 in that index to see if that index also contains the same element as element to search and if yes, then we have majority element else not.

package com.javabypatel.arrays;

public class MajorityOfElementInSortedArray {
    public static void main(String[] args) {

        int arr[];

        //arr = new int[] {1, 2, 2, 2, 3, 3, 3};
        //arr = new int[] {1, 1, 1, 2, 2, 3};
        //arr = new int[] {1, 1, 1, 2, 2, 2, 2};
        //arr = new int[] {2, 2};
        arr = new int[] {2};

        int x = 3;
        boolean result = isMajority(x, arr, arr.length);
        System.out.println(result);

        result = isMajorityUsingBinarySearch(x, arr, arr.length);
        System.out.println(result);
    }

    //Time complexity O(N)
    private static boolean isMajority(int elementToSearch, int[] arr, int length) {

        //Here we are calculating till what index we need to search for element.
        //we need to only search till length/2 index for even length array and length/2+1 for odd length array after that index if element is present/absent
        //doesn't matter as count of the element would not be greater than length/2+1 after crossing middle element.
        int searchUptil = length % 2 == 0 ? length / 2 : length / 2 + 1;

        for (int i = 0; i < searchUptil; i++) {

            //If we get the index of the first match elementToSearch then check the value at the (currentIndex + length/2)
            //if the value at that index is elementToSearch then elementToSearch occur more than length/2 times.
            if(arr[i] == elementToSearch && arr[i + arr.length/2] == elementToSearch) {
                return true;
            }
        }

        return false;
    }

    private static boolean isMajorityUsingBinarySearch(int elementToSearch, int[] arr, int length) {
        return isMajorityHelper(elementToSearch, arr, 0, length-1);

    }

    /*
        In this approach we will find the first instance of the elementToSearch using BinarySearch after that
        we will directly check the index n/2 from that point and if it is same as elementToSearch then we have
        n/2 count of elementToSearch else not.
     */
    static boolean isMajorityHelper(int elementToSearch, int[] arr, int start, int end) {
        if (start > end) {
            return false;
        }

        int mid = start + (end - start) / 2;

        if (arr[mid] == elementToSearch && (mid == 0 || arr[mid-1] < elementToSearch)) {

            //If we get the index of the first match elementToSearch then check the value at the (currentIndex + length/2)
            //if the value at that index is elementToSearch then elementToSearch occur more than length/2 times.
            if((mid + arr.length/2 < arr.length) && arr[mid + arr.length/2] == elementToSearch) {
                return true;
            }

            return false;

        } else if (arr[mid] < elementToSearch) {
            //Search on right side of mid.
            return isMajorityHelper(elementToSearch, arr, mid + 1, end);
        } else {
            //if the elementToSearch is found and is not the first instance or
            //if elementToSearch is greater than mid, continue searching on left side of mid.
            return isMajorityHelper(elementToSearch, arr, start, mid - 1);
        }
    }


}

Wednesday, 27 March 2019

Difference between CountDownLatch and CyclicBarrier in Java

Difference between CountDownLatch and CyclicBarrier in Java?

Difference 1:

In CountDownLatch, main thread which mostly invokes latch.await() waits for other threads to call countDown() and count reaches 0. In CyclicBarrier, threads wait for each other to complete their execution and reach at common point after which barrier is opened.

Note in CountDownLatch, it is not necessary same thread calls latch.countDown() 10 times or 10 threads calling latch.countDown and making the counter 0 but in case of CyclicBarrier different threads should reach at the common barrier point.

Let's see example of CyclicBarrier

package com.javabypatel.practice;

import java.util.concurrent.CyclicBarrier;

public class CyclicBarrierExample {
    
    public static void main(String args[]) {
        final CyclicBarrier cb = new CyclicBarrier(3, new Runnable(){
            @Override
            public void run(){
                System.out.println("Start the Game");
            }
        });

        Thread player1 = new Thread(new Player(cb), "Thread1");
        Thread player2 = new Thread(new Player(cb), "Thread2");
        Thread player3 = new Thread(new Player(cb), "Thread3");

        player1.start();
        player2.start();
        player3.start();
    }
}

class Player implements Runnable {

    private CyclicBarrier barrier;
    public Player(CyclicBarrier barrier) {
        this.barrier = barrier;
    }

    @Override
    public void run() {
        try {
            System.out.println(Thread.currentThread().getName() + " is waiting on barrier");
            barrier.await();
            System.out.println(Thread.currentThread().getName() + " has passed the barrier");
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }
}

Output:
Thread1 is waiting on barrier
Thread2 is waiting on barrier
Thread3 is waiting on barrier
Start the Game
Thread3 has passed the barrier
Thread2 has passed the barrier
Thread1 has passed the barrier

Difference 2:

CountDownLatch can not be reused once count reaches 0. CyclicBarrier can be reinitialized once parties reaches 0.

Difference 3:

CountDownLatch calls countDown() method to reduce the counter where as CyclicBarrier calls await() method to reduce the counter. Note, await() method blocks the thread from further execution until all thread reaches to a common barrier, countDown() method doesn't block anything.

Difference 4:

CountDownLatch can not trigger common event when count reaches 0, that is when count reaches 0, it just unblocks the blocked thread and proceed with executing further instructions.

CyclicBarrier can trigger common event (Runnable) once it reaches to a barrier point.
Example: refer above

Difference 5:

CyclicBarrier is used for map-reduce kind of operations, like say we want to count population on India, so we will create say 4 threads which counts the population of East, West, North and South.

Each thread will count the population of its Region, we also need to merge the result when data from all threads is ready until which merging cannot be done.

We can create a CyclicBarrier and block the thread after it finds the count, so all threads are blocked after counting the population of its respective region, once all thread reaches barrier, it is broken and merger(Runnable event) can be executed to count the population.

CountDownLatch is used when we want all thread to reach at common event but doesn't necessarily want to block them at that point and they can proceed after signaling(latch.countDown()), Say for example, if we want to start the client file poller after database service(thread1) and ConnectionPoolService with 100 threads(thread2) is up, so we can wait for thread1 and thread2 to call countDown() after which blocked main thread can proceed with starting client file pooler.

Difference between Join and CountDownLatch in Java

Difference between Join and CountDownLatch?

Difference 1:

Thread join method waits for other thread to finish before further executing current thread.
If t1.join is called in main thread, then main thread will wait at that point until t1 finishes its job.

CountDownLatch on the other end wait for its counter to reach 0 before executing current thread.

ExecutorService service = Executors.newFixedThreadPool(5);
final CountDownLatch latch = new CountDownLatch(3);

for(int i = 0; i < 5; i++) {
    service.submit(new Runnable() {
        public void run() {
            latch.countDown();
        }
    });
}

latch.await();

When latch.countDown is called, associated counter will be decremented and as soon as it reaches 0, main thread which was blocked at line latch.await() proceeds further.

Note:
Thread join method wait for joined thread to finish the execution before the main thread on which join method is called to starts its execution. Whereas in CountDownLatch, latch.await doesn't wait for the thread that calls latch.countDown() to be finished, it proceeds once the counter value reaches 0 and it has no association with the state of the thread that calls countDown().

Difference 2:

We can call join method when we have control over the threads but while using ExecutorService we don't have control over individual threads instead we deal with just submitting the task to framework and it internally manages threads in this situation using CountDownLatch is right approach.

Example above in difference 1 can be used as Reference.

Usage:

Example 1:
CountDownLatch is useful in Multiplayer games, Lets say we have a online chess game that can only be played when two player joins, in this case we will initialize the CountDownLatch to 2 and starts the game only after 2 threads(player) joins(calls countDown()).

Example 2:
Lets say we have some Timer task that we want to start only after all the modules of the application get loaded or when all the services is up.

ReentrantLock interview questions in Java

Reentrant lock is more feature rich than using synchronized method/block.

This post assume you have basic idea about Threads and synchronization in Java, If not I recommend going through below Multithreading articles first,

When using synchronized method or a synchronized block, process of lock acquisition and release is actually handled internally but with Reentrant Lock, programmer has full control over thread locks and thread locking management is on developer by explicitly calling lock and unlock method, so there is both advantages and disadvantages of this Reentrantlock.

Reentrantlock interview questions in java

Question 1: What is the difference between ReentrantLock and Synchronized keyword in Java?

Time to wait for getting a Lock:

When a thread invoke synchronized method or a block, It has to first acquire a lock and then only it can proceed, there is no control to programmer over a time a thread should keep waiting for lock.

Lets understand above point with an example, When thread 1 tries to call any synchronized method or synchronized block, It has to wait until some other thread say thread 2 release the lock on the same monitor. What if the thread 2 doesn't release the monitor due to some reason, How much time thread 1 has to wait, there is no control to the programmer till when Thread 1 will be waiting.

Using ReentrantLock which was introduced in jdk 1.5 under java.util.concurrent.locks package, We can provide a timeout till when thread should keep waiting for acquiring a lock and after that time thread will proceed with normal execution. this will give more control to threads while waiting for a lock instead of indefinitely waiting or getting blocked till lock is acquired.

Example: tryLock method,

  
Lock lock = new ReentrantLock();
lock.tryLock(long timeout, TimeUnit unit)

Complete trylock example in Java

package javabypatel;

import java.util.Random;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.ReentrantLock;

public class ThreadSafeArrayList<E> {
    public static void main(String[] args) throws Exception {
        final ReentrantLock lock1 = new ReentrantLock();
        final ReentrantLock lock2 = new ReentrantLock();

        String printerLock = "PrinterLock";
        String scannerLock = "ScannerLock";

        Runnable try1_2 = getRunnable(lock1, printerLock, lock2, scannerLock);
        Runnable try2_1 = getRunnable(lock2, scannerLock, lock1, printerLock);
        Thread t1 = new Thread(try1_2);
        t1.start();
        Thread t2 = new Thread(try2_1);
        t2.start();
    }

    private static Runnable getRunnable(final ReentrantLock lock1, final String lock1Name,
        final ReentrantLock lock2, final String lock2Name) {
        return new Runnable() {
            @Override
            public void run() {
                try {
                    if (lock1.tryLock(5, TimeUnit.SECONDS)) {
                        System.out.println(lock1Name + " acquired by thread " + Thread.currentThread());

                        Random rand = new Random();

                        if (lock2.tryLock(rand.nextInt(10), TimeUnit.SECONDS)) {
                            System.out.println(lock2Name + " acquired by thread " + Thread.currentThread());
                            Thread.sleep(2000);
                        } else {
                            System.out.println("Could not acquire " + lock2Name + " by thread " + Thread.currentThread());
                            lock1.unlock();
                            System.out.println(lock1Name + " released by thread " + Thread.currentThread());
                        }
                    } else {
                        System.out.println("Unable to acquire " + lock1Name + " by thread " + Thread.currentThread());
                    }
                } catch (InterruptedException e) {
                    System.out.println("I am interrupted" + Thread.currentThread());
                } finally {
                    if (lock1.isHeldByCurrentThread())
                        lock1.unlock();
                    if (lock2.isHeldByCurrentThread())
                        lock2.unlock();
                }
            }
        };
    }
}

Fairness policy:

When thread (say thread 1) calls synchronized method or synchronized block, it has to first acquire the monitor and then only can enter inside synchronized area. If monitor is acquired by other thread say thread 2 then thread 1 has to wait.

Also, there can be many threads(say thread 1, thread 5, thread 8 etc) waiting for the same monitor. what will happen when thread 2 release the lock on monitor, which thread will be the next to execute among thread 1, thread 5, thread 8 waiting for lock?

There is no guarantee which thread will get the control and that totally depends on scheduler, this leads to problem of thread (say thread 1) not getting monitor even though it is waiting for longest time among other threads for acquiring the lock and other thread (say thread 5) gets the monitor even if it just joined the waiting queue. ReentrantLock solves this problem by adding fairness policy while creating

ReentrantLock object.

While creating a ReentrantLock object, we can provide fairness property for making the lock fair. Fairness property provides lock to longest waiting thread, in case of contention. With fairness enabled, Threads get the lock in the order they requested it.

Example:

  
  ReentrantLock lock = new ReentrantLock(true);

Note: Performance is degraded by fairness policy.

LockInterruptibly

When thread 1 calls the synchronized method or synchronized block, it will be blocked until lock on the monitor is available. programmer don't have control to resume the blocked thread.
ReentrantLock provides a method called lockInterruptibly(), which can be used to interrupt the thread when it is waiting for lock. so that it can no longer in blocked state indefinitely.

void lockInterruptibly()
If thread is able to acquire lock then this method increments lock hold count by 1.
If the lock is with another thread then the current thread waits until it gets the lock or some other thread interrupts the thread.

lockinterruptibly example in java:

public class LockInterruptiblyExample{
 final ReentrantLock reentrantLock = new ReentrantLock();
 
 public void performTask() {
      try {
       reentrantLock.lockInterruptibly(); //wait till thread get the lock or till other thread interrupts
         //and you can control further execution from catch block
       try {
         //.....
       } finally {
      reentrantLock.unlock();
       }
      } catch (InterruptedException e) {
       e.printStackTrace();
      }
 }
}

Number of Threads blocked on monitor:

Using synchronized method or block doesn't provide any mechanism to know how many threads are blocked to acquire a lock on monitor
Reentrant lock provides getQueueLength() method which return number of threads that may be waiting to acquire this lock in java.

Lock Unlock in different scope

With Synchronized keyword, lock need to be acquired and released at complete method level or at block level. Lets say when thread t1 tries to acquire multiple locks by calling multiple synchronized method, in that case multiple locks are acquired by t1 and they must all be released in the opposite order.

In ReentrantLock, locks can be acquired and released in different scopes, and allowing multiple locks to be acquired and released in any order.

Example:

ReentrantLock reentrantLock;

public void getA() {
  reentrantLock.lock();
}

public void getB() {
  reentrantLock.unlock();
}

More than one waiting condition

When lock is acquired using intrinsic lock by calling synchronized method/block, this threads then communicate using wait(), notify() and notifyAll() methods of Object class.

Condition allows inter thread communication when lock is acquired using extrinsic way by Lock interface. Condition defines methods such as await(), signal() and signalAll() for waiting and notifying.

Using synchronized block/method for a common monitor, there is no way to distinguish for what reason each thread is waiting, thread t1, t2, t3 might be blocked say for putting the data in the queue, other threads say t5, t6, t7, t8 might be waiting for reading data from the queue and they all are waiting on common monitor "queue".

Lets consider producer consumer situation, say we have a queue of size one and is full and t1, t2, t3 is blocked for putting the data in the queue, so they are in waiting state.
Now, t5, t6, t7, t8 tries to read data from the queue, lets say t5 would be reading the data in the queue, meanwhile t6, t7, t8 would be in waiting state.

After t5 read the data from the queue, it calls notifyAll, this call is to notify producers(t1,t2,t3) to put the data in the queue as there is a space now,
there are total 6 threads waiting for monitor "queue"
putting data in queue = t1, t2, t3,
reading data from queue = t4, t6, t7
currently monitor is held by executing thread = t5

when t5 calls notifyAll, there is no guarantee who is going to be wake up, might be thread t7 wake up and it has to go back to waiting state again as nothing is there to read, next time might be t4 gets a chance and again no use of t4 wakeup and it will go back to waiting state.
When someone from t1, t2 or t3 wakes up then only things would proceed.

If there is a way for t5 thread to notifyAll only to threads that want to put data to queue t1, t2 and t3 then it would be helpful. Using Condition that is possible.

With intrinsic lock using synchronized method/block there is no way to group the waiting threads waiting on a common monitor. with Condition, we can create multiple wait sets.

When you use Condition: await()/signal() you can distinguish which object or group of objects/threads get a specific signal.

Using Condition, we now have way to create more than one condition variable per monitor.
Monitors that use the synchronized keyword can only have one. This means Reentrant locks(implementation of Lock interface) support more than one wait()/notify() queue.

    private final Lock lock = new ReentrantLock();
    private final Condition queueEmpty = lock.newCondition();
    private final Condition queueFull = lock.newCondition();

    public void putData(int data) {
        lock.lock();
        try {
            while (queue is empty) {
                queueEmpty.await();
            }
            this.data = data;
            queueFull.signalAll();
                      
        } finally {
            lock.unlock();
        }
    }

    public void getData() {
        lock.lock();
        try {
            while (queue is full) {
                queueFull.await();
            }
            queueEmpty.signalAll();
        } finally {
            lock.unlock();
        }
    }

Now with queueFull.signalAll(), only threads those are waiting for this condition on same monitor "lock" will be awaked and rest will still be waiting.

Condition interface also comes with useful method that is:
boolean awaitUntil(Date deadline): Causes the current thread to wait until it is signaled or interrupted, or the specified deadline elapses.

Note: there is similar method wait(long timeInMilliseconds), but when there is System date change, above method will have impact while wait will keep waiting for provided timeInMilliseconds. So decide which is better in your situation.

Question 2. Does synchronized method and block are reentrant?

Yes. synchronized method, synchronized block and Reentrant lock are all reentrant in nature.

What is the meaning of Reentrant?
A reentrant lock is one where a process can claim the lock multiple times without blocking on itself.
In simple terms, ability to call the same synchronized method again and again without getting blocked is called reentrant.

Lets understand with example,

synchronized  void getA () {
    getB();
}

synchronized void getB () {
    getA();
}

What will happen if say Thread 1 calls obj.getA(), thread 1 will acquire a lock on obj and call method getA(). inside which it calls getB()(which is obj.getB()), thread 1 already hold the lock on obj so it will call getB(),
getB() call getA()(which is obj.getA()), thread 1 already hold a lock on obj so it is allowed to call the method getA() again. this is called Reentrant. same lock is claimed multiple times that is each time getA is called.

Question 3. Show simple example on how to write lock and unlock method of Reentrant Lock?

public void getA() { 
      reentrantLock.lock(); 
      try{ 
          //...
      } catch(Exception e) { 
          e.printStackTrace(); 
      } finally { 
          reentrantLock.unlock(); 
      }     
}

Question 4. Why ReentrantLock is called ReentrantLock?

ReentrantLock keep track of lock acquisition count associated with the lock.
when a call reentrantLock.lock() is made to acquire a lock and if the lock is obtained then the acquisition count variable is incremented to 1, stating that lock has been acquired one time till now.

Similarly, when a call reentrantLock.unlock() is made acquisition count variable is decremented by 1.
When the count reaches 0 then only other thread will be allowed to take the lock.

When a thread t1 acquires a reentrant lock inside method say getA() and make a call to another method say getB() from inside getA() which is also guarded by reentrant lock, in this case thread t1 will acquire a lock twice one for getA() method and one for getB() method. In this case, if a thread t1 that is already holding a lock is now acquiring it again inside getB(), the acquisition count is incremented to 2 and now the lock needs to be released twice to fully release the lock.

Let's see sample program,

package com.javabypatel.concurrency;

import java.util.concurrent.locks.ReentrantLock;

public class ReentrantLockExample {
    public static void main(String[] args) {
        ReentrantLock reentrantLock = new ReentrantLock();

        Thread t1 = new Thread(new Printer("Thread1", reentrantLock));
        Thread t2 = new Thread(new Printer("Thread2", reentrantLock));

        t1.start();
        t2.start();
    }
}

class Printer implements Runnable {

    private String threadName;
    private ReentrantLock reentrantLock;

    Printer(String threadName, ReentrantLock reentrantLock) {
        this.threadName = threadName;
        this.reentrantLock = reentrantLock;
    }

    @Override
    public void run() {
        System.out.println("Thread " + threadName + " is waiting to get lock");
        reentrantLock.lock();
        try {
            System.out.println("Thread " + threadName + " acquired lock");
            getA();
        } finally {
            reentrantLock.unlock();
            System.out.println("Thread " + threadName + " released the lock and the lock held count is :"+reentrantLock.getHoldCount());
        }
    }

    public void getA() {
        System.out.println("getA :: Thread " + threadName + " is waiting to get lock");
        try {
            reentrantLock.lock();
            System.out.println("getA :: Thread " + threadName + " acquired lock");
            System.out.println("getA :: Lock count held by thread " + threadName + " : " + reentrantLock.getHoldCount());

        } finally {
            reentrantLock.unlock();
            System.out.println("getA :: Thread " + threadName + " released the lock and the lock held count is :"+reentrantLock.getHoldCount());
        }
    }
}

Output:

Thread Thread1 is waiting to get lock
Thread Thread1 acquired lock
getA :: Thread Thread1 is waiting to get lock
getA :: Thread Thread1 acquired lock
getA :: Lock count held by thread Thread1 : 2
getA :: Thread Thread1 released the lock and the lock held count is :1
Thread Thread1 released the lock and the lock held count is :0
Thread Thread2 is waiting to get lock
Thread Thread2 acquired lock
getA :: Thread Thread2 is waiting to get lock
getA :: Thread Thread2 acquired lock
getA :: Lock count held by thread Thread2 : 2
getA :: Thread Thread2 released the lock and the lock held count is :1
Thread Thread2 released the lock and the lock held count is :0

You can see lock held count should go back to 0 for another thread to acquire a lock.

Monday, 25 March 2019

Delete all occurrences of a given key in a linked list.

Given a Linked list and key to delete, Remove all the occurrences of a given key in singly linked list.

Lets understand what is the input and the expected output.

Thursday, 14 March 2019

Find K largest elements in array using Min Heap.

Given a unsorted array, Find k largest element in array.

Find K largest elements in array using Max Heap

Lets understand what is the input and the expected output.

Wednesday, 13 March 2019

Find K largest elements in array using Max Heap

Find K largest elements in array using Max Heap.

Given a unsorted array, Find k largest element in array.

Heap Sort Algorithm

Lets understand what is the input and the expected output.

Tuesday, 12 March 2019

Quick Sort in Java

Quick Sort in Java.

Given a unsorted array, Sort it using Quick Sort Algorithm.

Merge sort linked list java

Lets understand what is the input and the expected output.

Friday, 8 March 2019

How Comparable and Comparator works internally in Java

In Java, Comparable and Comparator are used for sorting collection of objects.

java.lang.Comparable is used to sort collection of same types(classes) like List<Student>, List<Employee>, List<Orange>, It means Comparable is like "I can compare myself with another object of same type".

Example: if we want to sort List<Student> based on roll number or their first name etc.

java.util.Comparator is used to sort collection of different types(classes) like List<Object>.
It means Comparator is like "I can compare myself with other object of same/different type"

If you have observe java.util.Comparator is more like a Utility class that can sort objects of any class you provide and that is why it is in util package.

Comparable example

package com.javabypatel;

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class ComparableExample {

    private static final int INSERTIONSORT_THRESHOLD = 7;

    public static void main(String[] args) {
        Student s1 = new Student(10);
        Student s2 = new Student(50);
        Student s3 = new Student(20);
        Student s4 = new Student(30);

        List<Student> list = new ArrayList<>();
        list.add(s1);
        list.add(s2);
        list.add(s3);
        list.add(s4);

        System.out.println("Before sort:");
        list.forEach(s -> System.out.print(s.rollNo + " "));

        sort(list);
        //Collections.sort(list);

        System.out.println("After sort:");
        list.forEach(s -> System.out.print(s.rollNo + " "));
    }

    static void sort(List<Student> list) {
        int low = 0;
        Object[] dest = list.toArray();
        for (int i = 0; i < list.size(); i++)
            for (int j = i; j > low && ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--)
                swap(dest, j, j - 1);

        ListIterator<Student> i = list.listIterator();
        for (Object e : dest) {
            i.next();
            i.set((Student) e);
        }
    }

    private static void swap(Object[] x, int a, int b) {
        Object t = x[a];
        x[a] = x[b];
        x[b] = t;
    }

}

class Student implements Comparable<Student>{
    int rollNo;

    public Student(int rollNo) {
        this.rollNo = rollNo;
    }

    @Override
    public int compareTo(Student s) {
        if(rollNo==s.rollNo)
            return 0;
        else if(rollNo>s.rollNo)
            return 1;
        else
            return -1;
    }
}

Output:

Before sort:
10 50 20 30
After sort:
10 20 30 50

Here we are sorting List of Students by their roll number.
Generally we should be using "Collections.sort(list);" for sorting the list, for better understanding I have copied the code of sort method to understand how internally it sort the list.

It compare 2 objects and swap based on result returned by compareTo method.

Comparator example

package com.javabypatel;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ComparatorExample {

    public static void main(String[] args) {
        Student s1 = new Student(10, "Zara");
        Student s2 = new Student(50, "Jayesh");
        Student s3 = new Student(20, "Ash");
        Student s4 = new Student(30, "Kate");

        List<Student> list = new ArrayList<>();
        list.add(s1);
        list.add(s2);
        list.add(s3);
        list.add(s4);

        System.out.println("Before sort:");
        list.forEach(s -> System.out.print(s.name + " " + s.rollNo + ", "));

        NameComparator nameComparator = new NameComparator();
        Collections.sort(list, nameComparator);

        System.out.println("\n\nAfter sort by name:");
        list.forEach(s -> System.out.print(s.name + " " + s.rollNo + ", "));

        RollNumberComparator rollNumberComparator = new RollNumberComparator();
        Collections.sort(list, rollNumberComparator);

        System.out.println("\n\nAfter sort by Roll number:");
        list.forEach(s -> System.out.print(s.name + " " + s.rollNo + ", "));
    }
}

package com.javabypatel;

import java.util.Comparator;

public class Student {
    int rollNo;
    String name;

    public Student(int rollNo, String name) {
        this.rollNo = rollNo;
        this.name = name;
    }
}


//Name Comparator
class NameComparator implements Comparator<Student> {
    public int compare(Student s1, Student s2) {
        return s1.name.compareTo(s2.name);
    }
}

//Roll number Comparator 
class RollNumberComparator implements Comparator<Student> {
    public int compare(Student s1, Student s2) {
        if (s1.rollNo < s2.rollNo) return -1;
        if (s1.rollNo > s2.rollNo) return 1;
        else return 0;
    }
}

Output:
Before sort:
Zara 10, Jayesh 50, Ash 20, Kate 30,

After sort by name:
Ash 20, Jayesh 50, Kate 30, Zara 10,

After sort by Roll number:
Zara 10, Ash 20, Kate 30, Jayesh 50,

Thursday, 7 March 2019

How substring method creates memory leak in Java

How substring() method of String class use to create memory leaks before Java 7?

We know memory leak happens when any object is not used by the application and also GC is unable to reclaim memory blocked by that object, in that situation we would have Memory leak problem.

Calling substring method creates scenario as described above which leads to Memory leak.

public class SubstringExample {
    public static void main(String[] args) {
        String str1 = "Hello, this is Java";
        String str2 = str1.substring(7, 11);
        System.out.println(str2);
    }
}

Below diagram may give some clarity on how substring() method causes Memory leak.

What happens when we call "str1.substring(7, 11);", Ideally what should happen is, str2 should hold the value "this" but that is not happening and it still points to original string referenced by str1.

Before Java 7, String class uses count, offset and value field for representing any String.
count = length of the String
offset = index from which string needs to be printed
value = holds the actual String

String str1 = "Hello, this is Java";

count = 19
offset = 0
value = "Hello, this is Java"

Now when we print str1, it refers string present in value and start printing from index mentioned in offset which is 0 and print 19 characters from that index, which is a complete string.

String str2 = str1.substring(7, 11);

count = 4

offset = 7
value = "Hello, this is Java"

Now when we print str2, it refers string present in value and start printing from index mentioned in offset which is 7 and print 4 characters from that index, which is "this".

Note: str2 holds the value string "Hello, this is Java" which is not at all required, instead it should store "this".
Basically, str2 still points to the same string referenced by str1, because of which even str2 needs small portion of the string "this" but big string "Hello, this is Java" will not be garbage collected as str2 is holding it.

In Java 1.7 version, offset and count variable which is used to track position of the string to print are removed from String class to prevent memory leak.

Java Memory Management Interview Questions

What is memory leak?

In Java, Garbage collector handles memory management, but when garbage collector is not able to free any object that is not used by the application but it still holds the reference to it is called memory leak.
In other words, when the program/application allocates memory for the object and later when object is no longer needed, instead of marking the reference as null, application holds the indirect reference to that object in such a way that garbage collector cannot free that object is called memory leak. slowly, application memory starts growing and ultimately result in OutOfMemoryError.

What happens when Garbage Collector(GC) runs? what does it mean by "stop-the-world"?
When GC thread runs, other threads are stopped for that duration, so application waits for that duration.
Note: Irrespective of GC need to run in Old generation or New Generation, all the events of GC run will pause application threads until GC run completes.

In Java, what goes in Heap and Stack?

Heap and Stack both are the part of RAM. So there is a separate space in RAM for stack and heap.
Local variables/references: All the local variables (primitive type) of the method and the method call itself goes to Stack.

Objects: when an object is created using new operator, the actual space for that object is allocated in heap but the reference to that space(object) is created in stack.

class Student {
    String rollNumber;
    String name
    Address address;
}

class Address{
    String zipcode;
}
public static void main(String args[]){
   Student s1 = new Student(10, "Jason", new Address("V5H3U7"))
}

Stack Heap
s1 ----------------> Student{ rollNumber = 10, name="Jason", address}
|
|
Address{zip code = "V5H3U7"}

What is the scope of Heap and Stack?

The stack is associated for a thread, so when the thread is done the stack is reclaimed. The heap is typically allocated at application startup by the runtime, and is reclaimed when the application (technically process) exits.

Which is faster Stack or Heap? Why?

Stack is faster in many terms than Heap though they both are part of RAM.
For Stack, in terms of deletion, it just needs to move the pointers in LIFO Manner, whereas for Heap, it has to do checks for live references along with that deletion creates fragmentation issues where if memory is freed in non continuous manner, then it has to do compaction (Memory compaction is the process of moving allocated objects together and leaving empty space together.)

Heap is shared across Threads, so allocation/deallocation of memory needs to be synchronized for Heaps, but for Stack, memory is private to Stack. this is also the reason Stack is faster than Heap.

Stack is generally accessed more frequently so for that purpose data of Stack is cached and that is also the reason it is faster than Heap.

The heap is a portion on RAM which is not managed automatically, and is not as tightly managed by the CPU. It is a just a block of memory and need to be managed by user. To allocate memory on the heap, you must use new keyword. we are responsible for deallocation of unused memory once we no longer require it, failing which can cause memory leaks.

How you fine tune Heap size?

-Xms (example: -Xms64m or -Xms64M)

Sets the initial size of the Java heap.

-Xmx (example: -Xmx1g or -Xmx1G)

Sets the maximum size to which the Java heap can grow.

-Xmn (example: -Xmn512, -Xmn512m, -Xmn512k)

Sets the initial Java heap size for the Young generation(Eden generation).

-Xss (example: -Xss512, -Xss512m, -Xss512k)
Sets the maximum stack size of each thread.
This option allows to fine tune max size allocated to each thread to store local variable, partial results and method calling information.
When the method is doing heavy operation with lots of variables, method calls and if you are encountering StackOverflowError, you can fine tune stack size by using this flag.

-Xnoclassgc

Disables garbage collection (GC) of classes. When you specify -Xnoclassgc at startup, the class objects in the application will be left untouched during GC and will always be considered live. This can result in more memory being permanently occupied which, if not used carefully, will throw an out of memory exception.

When you encounter StackOverflowError and OutOfMemoryError?

StackOverflowError :
Stack is used in Java for method execution, for every method call, a block of memory is created in the stack. The data related to method like parameters, local variables or references to objects are stored in this block.

When the method finishes its execution, this block is removed from the stack along with data stored in it. If a method keep calling other method recursively without returning back then at one point Stack will be full and there would not be any space left for allocating new stack block at that time you will encounter StackOverflowError.

OutOfMemoryError:

When there is no space left for creating new objects on Heap memory, java.lang.OutOfMemoryError is thrown.

OutOfMemoryError is encountered in below two scenarios,
1. java.lang.OutOfMemoryError: Java heap space Issue
2. java.lang.OutOfMemoryError: PermGen space Issue

Note few points below:

1. Garbage collection happens on Heap only.

2. Stack size is private to Thread

3. Heap size is shared across Threads.

How Garbage collection works, What is Mark and Sweep algorithm for garbage collection?

In Java, GC handles memory management, so it is GC's job to remove the object and free up the heap space when it is no longer referenced.
For removing the object, it first need to scan all the objects present, whether there exist any active references to the object or not, and remove the object those are not referenced from anywhere.

The process of identifying and marking the referenced(reachable) object is called Marking phase, where GC starts marking the objects as a indication that they are reachable, that is, the object reference is being referred(in use) and should not be deleted.
The process of deleting the marked objects is called Sweep phase, where un-referenced objects memory are freed up and heap space will be reclaimed.

Does GC guarantees that a program will not run OutOfMemory?

GC does not guarantee that a program will not run out of memory. It is possible that Program create objects faster as compare to GC cleaning the unreferenced objects. Also, it is possible that application creates lots of heavy object and holding the references to those object in this case GC can't help and may cause OutOfMemory error.

How many Class loaders are present in JVM?

First of all what Class loader does is load the .class files from physical location to JVM's memory and stores information such as class names, parent class, methods, constructors etc.

There are mainly 3 class loaders present in JVM,

Bootstrap ClassLoader: This classloader prime responsibility is to load internal core java classes present in the rt.jar and other classes present in the java.lang.* package. This class loader is shipped with every JVM and is written in native language. This class loader has no parent classloader.

Extension ClassLoader: This classloader responsibility is to load classes from jre\lib\ext folder.
The parent of this class loader is Bootstrap classloader. Java extensions are also referred to as optional packages.

Application or System ClassLoader: The parent of this class loader is Extension classloader
and is responsible for loading the classes from the system classpath(generally classes folder). It internally uses the ‘CLASSPATH‘ environment variable and is written in Java language.

Note: Class is loaded into memory only once even if you try to load multiple times.

When you get NoClassDefFoundError?

It is an error of type java.lang.Error. Any class which is available while compilation phase but is no longer available while running the application causes NoClassDefFoundError. Example:

class Student{ }
public class MainApp{
    public static void main(String[] args){
        Student stud = new Student();
    }
}

> javac MainApp.java
Above command will generate 2 classes MainApp.class and Student.class
Delete Student.class file

> java MainApp
This will throw NoClassDefFoundError

When you get ClassNotFoundException?

It is an runtime exception and is caused when application tries to explicitly load any class using Class.forName("path of class") and if the class is not available at the mentioned Path then it throws ClassNotFoundException.

How JVM Heap memory blocks is divided?
Till Java 7

Java memory management

Eden space, S0, S1 = Young Generation
S0, S1 = Survivor Space
Old Memory = Old Generation = Tenured Memory
Perm = Permanent Generation

Short description of Heap blocks:

Eden space, S0 and S1 are called Young generation space and Old Memory space is called old Generation space this is because Newly created objects are places in Eden space.

When GC runs in Eden space and if there are live references found in Eden space they are placed into Survivor space S0 and when GC runs in S0 and the reference is still live
(after some threshold) it is placed in S1. Now when GC runs in S1 and the reference is still live (after some threshold of surviving multiple GC cycle) it is placed in Old generation space.

Permanent Generation Space (PermGen space):
This is non Heap space used to store class metadata information. It is used by JVM to describe the classes and methods used in the application.

Note: You can get OutOfMemoryError when any of this block has no further space to store data.

When GC runs at Eden, S0 or S1 space it is called Minor GC, but when it runs in Old Generation it is called Major GC and it takes time to complete GC operation in Old generation .

Java 8

PermGen space which was part of Heap is removed in Java8 and is now called Metaspace.

The JDK 8 HotSpot JVM is now using native memory for the representation of class metadata, this also means that there will no longer be java.lang.OutOfMemoryError: PermGen space problems.

The arguments which was used to set the PermGen space is now useless and PermSize and MaxPermSize JVM arguments are ignored and a warning is given if present at start-up.

A new flag called MaxMetaspaceSize is provided to limit the amount of native memory used for class metadata. If we don’t specify this, the Metaspace will dynamically re-size depending of the application demand at runtime.

Garbage collection of the dead classes and classloaders is triggered once the class metadata usage reaches the “MaxMetaspaceSize”.

What is Method Area and where it belongs?

Method Area is part of space in the Perm Gen and used to store class structure (runtime constants and static variables) and code for methods and constructors.

Where is Java String pool located?

String pool was part of PermGen space but is now moved to separate Heap space because PermGen space was very limited, default size 64 MB and was used to store class metadata .class files information.

When are static variables loaded in memory ?

They are loaded at runtime when the respective Class is loaded.

What happens when we import any package or class? what if the same import is repeated in multiple classes? Will the JVM load the package or class twice at runtime?

No matter how many times you import the same class. JVM will load class only once(per class loader).

When is the finalize() method called in Java?

The finalize method will be called after the GC detects that the object is no longer reachable, and before it actually reclaims the memory used by the object.

Note: It is not a good practice to rely on finalize() method for clean up operation as we never know when GC will be invoked, also it is not guaranteed.
Also, finalize method may not get called if there is always active reference to the object.
finalize() is part of Object class.

@Override
public void finalize() {
    try {
        reader.close();
        System.out.println("Closed BufferedReader in the finalizer");
    } catch (IOException e) {
        // ...
    }
}

there are chances that class A job is to read data from file and then cache the String and always returned cached value, in this case we only need to open connection to file, read it and close. if we use finalize for closing the connection would be bad here because class A instance may always have active reference to return the cached value and finalize for closing the file will never get invoked.

Do member(instance) and local(method) variables have default values?

Example:

public class Example {
    static int a;
    int b;

    void getA(){
        A ref;
        int c ;
        System.out.println(a);   // ok         
        System.out.println(b);   // ok         
        System.out.println(ref); //Error: Variable ref might not have been initialized            
        System.out.println(c);   //Error: Variable c might not have been initialized    
   }
}

All member variables have to load into heap so they have to initialized with default values when an instance of class is created, so member variables are initialized with default values.
Local variables are stored on stack, so they are not initialized by default.

When the class is loaded by classloader?

When the class object is created using the new operator (static class loading) or when the class is explicitly loaded using Class.forName("path of the class") (dynamic class loading).

What are strong, soft, weak and phantom references in Java?

These references are useful in terms of when they are eligible for Garbage collection.

Strong Reference:
This is the default behavior of object creation. Strong reference means the object should not be garbage collected if there is any live reference pointing to it.

Student s = new Student()
s.rollNo = 10;
GC
---------------------------
s------------------------------------------->| Student(rollNo=10) | Heap
--------------------------
GC will not remove this memory because it is referred by
strong reference "s"

Weak Reference:
A weak reference is a reference which is not strong enough to survive garbage collection. In simple words, as the name suggest, object created using weak reference will be weak enough to get removed when the next garbage collection cycle runs.

Soft Reference:
A soft reference is very similar to Weak reference but the only difference is GC will throw the soft reference only when memory is low. It is generally used for implementing Cache.

Phantom reference:
A phantom reference will be finalized but the memory will not be reclaimed. Can be useful when you want to be notified that an object is about to be collected.

What are different ways to create String object? Explain.

There are 2 ways to create String object,
1. String str1 = new String("javabypatel");
2. String str2 = "javabypatel";

With the first approach using new operator, JVM creates the String in Heap as well as in String literal Pool (However I found conflicting answers for this, where some claims that only one object is created in heap and we need to explicitly call intern() method to copy it to pool), str1 will refer to the object created in Heap.

When we create a String using double quotes, JVM looks in the String pool to find if any other String is stored with same value. If found, it just returns the reference to that String object else it creates a new String object with given value and stores it in the String pool.

How substring() method of String class use to create memory leaks before Java 7?

We know memory leak happens when application is not using a object and GC is not able to reclaim memory blocked by that object due to active reference still exist.
substring method creates scenario as described above which leads to Memory leak.

Detail explanation in this How substring method creates memory leak in Java

What is Just-in-time(JIT) compilation in Java?

1. In Java, .java files are compiled to byte code(.class file)
2. JVM reads the .class files and convert it into machine understandable format.
3. Machine understandable lines are passed to CPU for execution.

Example source code:

String str1 = "Hello, this is Java";
System.out.println(str1);
System.out.println(str1);
System.out.println(str1);

Above code is compiled and say .class file is generated like below,

xyz1111
mnooooo
mnooooo
mnooooo

JVM needs to load compiled .class file, converts each line into Machine understandable format and give it for execution.

Before converting the compiled .class files to machine understandable instructions, JVM takes the compiled class files and does further compilation for complex optimizations to generate high-quality machine code. we will see what kind of optimization it does later. (this further compilation is done by part of JVM which is known at JIT.)

From above example, is there need to convert byte code "mnooooo" 3 times?
No. converted code can be stored and can be reuse when required.

JIT Compiler helps doing such optimization for JVM.

JIT also does further compilation to .class files and one of the feature for which it does further compilation is inlining, which is the practice of substituting the body of a method into the places where that method is called. Inlining saves the cost of calling the method; no new stack frames need to be created. By default, Java HotSpot VM will try to inline methods that contain less than 35 bytes of JVM bytecode.

Loop optimization, type sharpening, dead-code elimination, and intrinsics are just some of the other ways that Java HotSpot VM tries to optimize code as much as it can. Techniques are frequently layered one on top of another, so that once one optimization has been applied, the compiler might be able to see more optimizations that can be performed.

Compilation Modes

Inside Java HotSpot VM, there are actually two separate JIT compiler modes, which are known as C1 and C2. C1 is used for applications where quick startup and rock-solid optimization are required; GUI applications are often good candidates for this compiler. C2, on the other hand, was originally intended for long-running, predominantly server-side applications. Prior to some of the later Java SE 7 releases, these two modes were available using the -client and -server switches, respectively.

When memory is allocated for static variables in java?

When the class is first loaded into memory.

Where does static method, variables are stored in Java?

Classes goes in special area on heap called Permanent Generation.
Static member variables are kept on the Permanent Generation.
Eg:
static int i =10 (i=10 goes in perm gen space.)

static Address address = new Address
(address = "pointer to where address object is created" address reference will be part of permgen space but the actual memory allocation [new Address()] can be in Young or Old generation in Heap.)

static method(code): There is only one copy of each method per class, be the method static or non-static. That copy is put in the Permanent Generation area. (Method Area part of PermGen space)

Sunday, 31 March 2019

Check if a Binary Tree is a Mirror Image or Symmetric..

Saturday, 30 March 2019

Find Container with Most Water.

Friday, 29 March 2019

Find Power of a Number using Recursion in Java.

Length of the longest substring without repeating characters in Java.

Find the maximum consecutive 1's in an array of 0's and 1's. And Find length of the longest consecutive One's in binary representation.

Thursday, 28 March 2019

Find sum of digits of a number until sum becomes single digit.

Hamming distance between two Integers in Java.

Check if a binary tree is subtree of another binary tree.

Find Majority Element in a Sorted Array in Java? OR Find element in a sorted array whose frequency is greater than or equal to n/2.

Algorithm

You may also like to see

Majority Element in a Sorted Array in Java?

Algorithm

You may also like to see

Wednesday, 27 March 2019

Difference between CountDownLatch and CyclicBarrier in Java?

You may also like to see

Difference between Join and CountDownLatch?

You may also like to see

ReentrantLock interview questions in Java

Question 1: What is the difference between ReentrantLock and Synchronized keyword in Java?

You may also like to see

Monday, 25 March 2019

Delete all occurrences of a given key in a linked list.

Thursday, 14 March 2019

Find K largest elements in array using Min Heap.

Wednesday, 13 March 2019

Find K largest elements in array using Max Heap.

Tuesday, 12 March 2019

Quick Sort in Java.

Friday, 8 March 2019

How Comparable and Comparator works internally in Java

Comparable example

Comparator example

You may also like to see

Thursday, 7 March 2019

You may also like to see

Java Memory Management Interview Questions

You may also like to see