Sunday, April 22, 2018

How will you check if a given sentence is a pangram or not

Pangram
A pangram is a sentence containing every letter in the English Alphabet (a-z).
Pangram example: The quick brown fox jumps over the lazy dog
Pack my box with five dozen liquor jugs.
— Pangram
Approach:
  1. Create an boolean array that can hold 26 boolean corresponding to each alphabet in English.
  2. Traverse each character of the sentence and mark corresponding index (a=0, b=1,.. z=26) in the boolean array. Take care of upper and lower case.
  3. Traverse through the entire boolean array and see if all characters are covered. If all positions are set to true then input sentence is a pangram.
Pangram Source
package org.shunya.interview.chapter2;

public class Pangram {

    public boolean checkPangram(String str) {
        boolean[] mark = new boolean[26];

        int index = 0;
        for (int i = 0; i < str.length(); i++) {
            // If uppercase character, subtract 'A' to find index.
            if ('A' <= str.charAt(i) && str.charAt(i) <= 'Z')
                index = str.charAt(i) - 'A';
            else if ('a' <= str.charAt(i) && str.charAt(i) <= 'z')
                index = str.charAt(i) - 'a';
            mark[index] = true;
        }
        for (int i = 0; i <= 25; i++)
            if (!mark[i])
                return (false);
        return (true);
    }
}
A slightly optimized version of the same program can use an integer (has 32 bits) to hold the state of 26 alphabets by use of Bitwise OR and left shift operator.
 private void pangramEfficient() {
        String s = "The quick brown fox jumps over the lazy dog";
        int i = 0;
        for (char c : s.toCharArray()) {
            int x = Character.toUpperCase(c);
            if (x >= 'A' && x <= 'Z') {
                i |= 1 << (x - 'A');
            }
        }
        if (i == (1 << (1 + 'Z' - 'A')) - 1) {
            System.out.println("input is a pangram");
        } else {
            System.out.println("input is not a pangram");
        }
    }
JUNIT Test
import org.junit.Test;

import static org.junit.Assert.assertTrue;

public class PangramTest {
    private Pangram pangramChecker = new Pangram();

    @Test
    public void checkPangram() {
        String str = "The quick brown fox jumps over the lazy dog";
        assertTrue(pangramChecker.checkPangram(str));
    }
}
Thats all.

Tuesday, April 17, 2018

What is difference between ExecutorService's submit() and execute() method

It is a common multi-threading question thats generally asked in investment banking interviews (Barclays, Citibank, Morgan Stanley).
Lets first see the relation between ExecutorService and Executor interface.
Figure: ExecutorService extends Executor
Main differences between the two methods:
  1. The execute() method is declared in Executor interface while submit() method is declared in ExecutorService interface.
  2. The submit() method can accept both Runnable as well as Callable tasks, but execute() method can only accept a Runnable Task.
  3. execute() method returns void while submit() method returns Future object. Using future you can cancel the execution or retrieve the results of computation done by runnable/callable task.
  4. There is a difference when looking at exception handling. If your tasks throws an exception and if it was submitted with execute this exception will go to the uncaught exception handler (when you don’t have provided one explicitly, the default one will just print the stack trace to System.err). If you submitted the task with submit any thrown exception, checked exception or not, is then part of the task’s return status. For a task that was submitted with submit and that terminates with an exception, the Future.get will re-throw this exception, wrapped in an ExecutionException.
Final advise
You should prefer to use submit() method because it gives more flexibility to the programmer in terms of execution control i.e. you can check status of task, cancel a task or get the results of task. Additionally a better exception handling is possible using submit().
Finally, a working example of ExecutorService.
ExecutorService Example
import java.util.concurrent.*;

public class ExecutorExample {

    public void example() {
        ExecutorService executor = Executors.newFixedThreadPool(2);
        Callable<String> futureTask =
                new Callable<String>() {
                    @Override
                    public String call() throws Exception {
                        return searcher.search(target);
                    }
                };
        final Future<String> future = executor.submit(futureTask);
        try {
            String result = future.get();
            System.out.println("result = " + result);
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
        executor.shutdownNow();
    }

    public static void main(String[] args) {
        ExecutorExample test = new ExecutorExample();
        test.example();
    }
}

Explain Java Exception Class Hierarchy

Throwable sits at the top of Java Exception Class hierarchy. Exception and Error are the two direct subclasses that extends Throwable.
Below is the rough diagram for Java Exception Class Hierarchy.
Java Exception Class Hierarchy
Logically, there are three main types of Exceptions in Java:
Error
It is an irrecoverable condition e.g. OutOfMemoryErrorStackoverflowErrorAssertionError etc. Right side of Exception Class Tree clearly illustrates Error Hierarchy.
Checked Exceptions
These classes extends Exception class but not part of RuntimeException, example includes:  IOExceptionSQLExceptionFileNotFoundException, etc. Developers need to declare/catch these exceptions using try-catch block.
Unchecked (Runtime) Exceptions
As illustrated in left most side of Tree in above diagram, anything that extends RuntimeException belongs to this category. It represents an error in our program’s logic which can not be reasonably recovered from at run time, for example NullPointerException, ArrayIndexOutOfBoundsException. We do not need to declare/catch such exception in the method signature because these are not expected by any programmer. A custom unchecked exceptions can be created by extending from RuntimeException.

Is it possible to catch Exception before catching NullPointerException in single try-catch block?

No, compiler will complain. Lets see the code first.
Java Source
private void method1() {
    try {
        throw new NullPointerException("test");
    } catch (Exception e) {
        e.printStackTrace();
    } catch (NullPointerException npe) {    
        npe.printStackTrace();
    }
}
Compiler will report error on this line, because the super class of NullPointerException which is Exception, already has a catch block before NPE.
The correct way would be to move NPE before the exception catch block, as illustrated in the below code snippet.
private void method2() {
    try {
        throw new NullPointerException("test");
    } catch (NullPointerException npe) {
        npe.printStackTrace();
    } catch (Exception e) {
        e.printStackTrace();
    }
}

Monday, April 16, 2018

Swap two numbers in Java without temporary variable

Swap two numbers Java

There are mainly 3 approaches to swap two number in Java, we will discuss all of them in order of increasing relevancy from interview point of view.

Approach 1. Using a temporary variable

Two numbers can be swapped using a temporary variable.
void method3() {
    int x = 10, y = 5;

    int temp = x;
    x = y;
    y = temp;
    System.out.println("After swap x = " + x + ", y = " + y);
}
Program output
After swap x = 5, y = 10
But this approach is not of great relevance from interview point of view.

Without temp variable

Approach 2. Using sum of numbers

We can easily swap two numbers using summation approach, as illustrated in the below code snippet.
void method1() {
    int x = 10, y = 5;

    x = x + y; // x becomes 15
    y = x - y; // y becomes 15 - 5 = 10
    x = x - y; // x becomes 15 - 10 = 5
    System.out.println("After swap x = " + x + ", y = " + y);
}
But there are issues with this code due to integer overflow and underflow. This program will not behave as expected when sum of x and y crosses the (+/-)231 limit.
Integer overflow & underflow
If it overflows, it goes back to the minimum value (Integer.MIN_VALUE = -231) and continues from there. If it underflows, it goes back to the maximum value (Integer.MAX_VALUE = 231) and continues from there. The main issue here is that overflow and underflow are silent and you will not see any exceptions if it occurs.
Integer overflow example:
void integerOverflow() {
    int x = Integer.MAX_VALUE - 10;
    int y = Integer.MAX_VALUE - 10;
    int result = x + y;    
    System.out.println("sum = " + result);
}
Since variable result can not hold sum of two large integer values, so integer overflow will occur. Please be noted that there will be no exception, so user will never be notified about this behavior.
Program output
sum = -22
Did you know
Java 8 provides option to let programmer know about the underflow and overflow by making use of the new Math#addExact() and Math#subtractExact() methods which will throw an ArithmeticException on overflow/underflow.
Java 8 approach (safe approach)
public static boolean willAdditionOverflow(int left, int right) {
    try {
        Math.addExact(left, right);
        return false;
    } catch (ArithmeticException e) {
        return true;
    }
}

Approach 3. Using XOR bitwise operator

Best way to swap two numbers without falling into trap of integer overflow problem is to use XOR bitwise operator.
What is Bitwise XOR
A bitwise XOR takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. In this we perform the comparison of two bits, being 1 if the two bits are different, and 0 if they are the same.
    0101 (decimal 2)
XOR 0011 (decimal 10)
    ----
  = 0110 (decimal 8)
Bitwise XOR Practical Use
Bitwise XOR can be used to flip the bits in a given number. Any bit may be toggled by XORing it with 1.
Java Code to swap two integer using XOR
void method2() {
    int x = 10;
    int y = 5;

    // Code to swap 'x' (1010) and 'y' (0101)
    x = x ^ y; // x now becomes 15 (1111)
    y = x ^ y; // y becomes 10 (1010)
    x = x ^ y; // x becomes 5 (0101)

    System.out.println("After swap: x = " + x + ", y = " + y);
}
Program output
After swap: x = 5, y = 10
That’s all.

Practical Usecase of Bitwise OR, AND and XOR operand

Bitwise AND
The operation may be used to determine whether a particular bit is set (1) or clear (0).
Bitwise OR
The bitwise OR may be used to set to 1 the selected bits of the register described above.
Bitwise XOR
The bitwise XOR may be used to invert selected bits in a register (also called toggle or flip). Any bit may be toggled by XORing it with 1.