Binary Search

package com.mylearnings;

public class BinarySearch {

public static void main(String[] args) {
int input[] = {5,7,6,8,65,87,12,3,343,44,767,78};
int sortedInput[] = {5,6,12,15,18,25,45,65,70,75,78,80,82,83,85,88,90,98,100,105,107};
BinarySearch search  = new BinarySearch();
int index = search.binarySearch(sortedInput, 0, sortedInput.length, 65);
System.out.println(index);
}

public int binarySearch(int[] input, int startIndex, int endIndex, int search) {
if(startIndex <= endIndex) {

int mid= startIndex + (endIndex - startIndex)/2;
int midVal = input[mid];
if(midVal == search) {
//System.out.println("Value found at index : "+mid);
return mid;
}else if(search < midVal) {
return binarySearch(input, startIndex , mid-1, search);
}else {
return binarySearch(input, mid+1, endIndex, search);
}
}

return -1;
}

}

Thread.run() and Thread.start()

Thread.start() essentially calls run() method only.
If we call Thread.run() directly, it will be executed in the same thread and a new thread would not be created.
So the purpose of multithreading is not fulfilled.

LimeSpot interview Question (Telephonic Interview)

Currently there are three projects in LimeWire :
1. LimeWire
2. Lime Domain : Hosts domain for users
3. LIme Exchange

Q1: What in an outer join and what is an Inner join?
A: Inner Join returns a row when there is at-least one match in one match in both the tables. e.g.
SELECT Persons.LastName, Persons.FirstName, Orders.OrderNo
FROM Persons
INNER JOIN Orders
ON Persons.P_Id=Orders.P_Id
ORDER BY Persons.LastName

http://www.w3schools.com/sql/sql_join_inner.asp

Outer JOin :
Returns a row even if there is no match.
An outer join does not require each record in the two joined tables to have a matching record. The joined table retains each record—even if no other matching record exists. Outer joins subdivide further into left outer joins, right outer joins, and full outer joins, depending on which table(s) one retains the rows from (left, right, or both).

Q2. What is Normalisation and what is BCNF?
A: Boyce Codd Normal Form

Volatile variable in java

According to Kathy Sierra :

" The volatile modifier tells the JVM that a thread accessing the variable must
always reconcile its own private copy of the variable with the master copy in
memory "

My understanding :
In normal scenario, In a multi-threaded environment, every thread keeps a local copy of instance variable and if a thread makes some change to the variable, the changed value would be visible to that thread only.

But if we declare a variable as volatile, the variable is stored in main memory and not in local memory of any thread. So, if the value of the variable is changed by any thread, it will be changed in the main memory and would be visible to all threads accessing that variable.

The Java Class Loading Mechanism

The Java platform uses a delegation model for loading classes. The basic idea is that every class loader has a "parent" class loader. When loading a class, a class loader first "delegates" the search for the class to its parent class loader before attempting to find the class itself.

Constructors in java.lang.ClassLoader and its subclasses allow you to specify a parent when you instantiate a new class loader. If you don't explicitly specify a parent, the virtual machine's system class loader will be assigned as the default parent.

The loadClass method in ClassLoader performs these tasks, in order, when called to load a class:

If a class has already been loaded, it returns it.

Otherwise, it delegates the search for the new class to the parent class loader.

If the parent class loader does not find the class, loadClass calls the method findClass to find and load the class.

The findClass method of ClassLoader searches for the class in the current class loader if the class wasn't found by the parent class loader. You will probably want to override this method when you instantiate a class loader subclass in your application.

The class java.net.URLClassLoader serves as the basic class loader for extensions and other JAR files, overriding the findClass method of java.lang.ClassLoader to search one or more specified URLs for classes and resources.

java.lang.Error

Error extends Throwable.

It indicates that some serious and abnormal condition has occurred and the application should not try to catch it.

Multiple catch blocks

Both

try{

     }catch(Error e){

     }catch(NullPointerException npe){

    }

and


           try{

}catch(NullPointerException npe){

}catch(Error e){

}

will compile.

Exception Hierarchy

Throwable is a class which extends Serializable interface.
All other classes in hierarchy extend Throwable class

Error , Exception and Runtime Exception classes only have the constructors (which call the corresponding super class constructors). All other methods are inherited from the Throwable class itself.

Program to Shuffle a pack of card in O(n)

public class Shuffle {

public static void shuff(int[] arr) {
for(int i=0; i
int rand  = (int)(Math.random() * arr.length);
int temp = arr[rand];
arr[rand] = arr[i];
arr[i] = temp;
}
for(int i=0; i
System.out.println(" "+arr[i]);
}
}
}

MarkIT Telephonic Interview Questions

1. Difference between ArrayList and LinkedList. Why search in ArrayList is faster than in LL. When to use what

Ans : Array List is implemented as an Array and since arrayList is indexed, we just need to go to array+i th position directly. We do not have to traverse the whole list as in case of LL

2. HashCode and Equals contract

3. Difference between HashTable and HashMap
(If have inserted lakhs of objects in a HashTable and these threads simultaneously want to access a method(lets say equals() method)... one thread will accquire lock on the method, so others will have to wait. This will be a performance hit.
This is the reason why HashMap (not synchronised) came into picture. HashTable is legacy datastructure.

4. Difference between IOC and Dependency Injection

5. Difference between Error and Exception. Are all Errors Irrecoverable. (Think about NoClassDefFoundError)

java.lang.ThreadDeath

java.lang.Object
          |
java.lang.Throwable
          |
java.lang.Error
          |
java.lang.ThreadDeath (implements Serializable interface)

This Error is thrown by the Thread when the stop method with zero arguments is called.

Java Program without main method

When JVM finds a class, it first executes the static block and then searches for main method.
So, to avoid the JVM from searching for main method, we can execute the required code (iff possible) in static block and then exit .. before the main method is called.

Below is the code :


/**
* @Author : Pragya Rawal
*
*/
public class NoMain {


static {
System.out.println("I am in static block");
System.exit(0);
}
}

Please note that you would not be able to run this program using Eclispe IDE. You will have to run using command line

javac NoMain.java
java NoMain

you would see the output : "I am in static block"

Generics and Unboxing

When using legacy (non-type safe) collections—watch out for unboxing problems! If you declare a non-generic collection, the get() methodALWAYS returns a reference of type java.lang.Object. Remember that unboxing can't convert a plain old Object to a primitive, even if that Object reference points to an Integer (or some other primitive) on the heap. Unboxing converts only from a wrapper class reference (like an Integer or a Long) to a primitive.

Generics exist only till compile time. They do not exist at run time

All your generic code is strictly for the compiler. Through a process called "type erasure," the compiler does all of its verifications on your generic code and then strips the type information out of the class bytecode. At runtime, ALL collection code—both legacy and new Java 5 code you write using generics—looks exactly like the pre-generic version of collections. None of your typing information exists at runtime. In other words, even though you WROTE

List myList = new ArrayList();


By the time the compiler is done with it, the JVM sees what it always saw before Java 5 and generics:

List myList = new ArrayList();

The compiler even inserts the casts for you—the casts you had to do to get things out of a pre-Java 5 collection.

Think of generics as strictly a compile-time protection. The compiler uses generic type information (the in the angle brackets) to make sure that your code doesn't put the wrong things into a collection, and that you do not assign what you get from a collection to the wrong reference type. But NONE of this protection exists at runtime.


This compiler warning isn't very descriptive, but the second note suggests that you recompile with -xlint:unchecked. If you do, you'll get something like this:

javac -Xlint:unchecked TestBadLegacy.java
TestBadLegacy.java:17: warning: [unchecked] unchecked call to
add(E) as a member of the raw type java.util.List
list.add(new String("42"));
^
1 warning

When you compile with the -Xlint:unchecked flag, the compiler shows you exactly which method(s) might be doing something dangerous.

Cloneable Interface

The clone( ) method generates a duplicate copy of the object on which it is called. Only classes that implement the Cloneable interface can be cloned.
The Cloneable interface defines no members. It is used to indicate that a class allows a bitwise copy of an object (that is, a clone) to be made. If you try to call clone( ) on a class that does not implement Cloneable, a CloneNotSupportedException is thrown. When a clone is made, the constructor for the object being cloned is not called. A clone is simply an exact copy of the original.

Cloning is a potentially dangerous action, because it can cause unintended side effects. For example, if the object being cloned contains a reference variable called obRef, then when the clone is made, obRef in the clone will refer to the same object as does obRef in the original. If the clone makes a change to the contents of the object referred to by obRef, then it will be changed for the original object, too. Here is another example. If an object opens an I/O stream and is then cloned, two objects will be capable of operating on the same stream. Further, if one of these objects closes the stream, the other object might still attempt to write to it, causing an error.

Because cloning can cause problems, clone( ) is declared as protected inside Object. This means that it must either be called from within a method defined by the class that implements Cloneable, or it must be explicitly overridden by that class so that it is public. 

Inefficient O(n^2) Method of finding Largest Recurring Substring in a string

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
* @author Pragya Rawal
*/
public class LargestSubstring {
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter String : ");
try {
String input = br.readLine();
LargestSubstring str = new LargestSubstring();
String largestSubstr = str.getLargestSubstr(input);
if (largestSubstr != null) {
System.out.println("Largest Recurring substring is : "
+ largestSubstr);
}
} catch (IOException e) {
e.printStackTrace();
}

}

public String getLargestSubstr(String input) {
if (null == input || input.length() == 0) {
System.out.println("Invalid / Empty string ...");
return null;
} else {
int length = input.length();
int subStrLen = 0;
String longestSubStr = "";
String currentStr = "";
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
int k = i;
int l = j;
while ((k < length) && (l < length) &&(input.charAt(k) == input.charAt(l)) ) {
currentStr += input.charAt(k);
k++;
l++;
subStrLen++;
}
if (longestSubStr.length() < currentStr.length()) {
longestSubStr = currentStr;
}
currentStr = "";
}

}
return longestSubStr;
}

}
}

Program(s) for finding power of a number

First, an interactive solution: (raising a to the power of b)

public double Power(double a, int b) {
if (b<=0) return 0; // we want a positive integer for the exponent
else {
double c=1;
for (int i=0; i c*=a;
}
return c;
}
}


Very easy and linear. You start from one and go on multiplying c by a so c is respectively 1, a, a^2, a^3, ... a^b.
When done, you return c. This one takes linear time.

Second, a recursive solution:

public double Power(double a, int b) {
if (b<=0) return 0;
else if (b==1) return a;
else {
return a*Power(a,b-1);
}
}


This is also an easy one. What we do here? Simple: we calculate a^b=a * a^(b-1). This is done by the recursion and takes linear time as well.

So, how can we beat these to slugs? We do this way.
Let me give you an example with b being a power of 2 (which is the easiest to understand).

Imagine you have to evaluate a^64. You could think this:

a^64 = c^32 where c=a^2
c^32 = d^16 where d=c^2
d^16 = e^8 where e=d^2
e^8 = f^4 where f=e^2
f^4 = g^2 where g=f^2
g^2 = g*g

This requires 6 operations. Using one of the two previous algorithms takes 64 operations! In fact 6=log64 (log is meant in base 2 obviously).

Now, things are different when b isn't a power of 2, but the algorithm is just a bit more complicated. Let's see an example again. We'll evaluate a^20.

a^20 = c^10 where c=a^2
c^10 = d^5 where d=c^2
d^5 = d * e^2 where e=d^2
e^2 = e*e

This requires 5 operations. Log16=4 and log32=5 so as you can see we have here 5=Ceiling(log20). This happens when b isn't a power of 2, but the cost of the entire algorithm doesn't grow that much and we can still say that it runs in logarithmic time (this is more true when b is a medium-big number).

private double Power(double a, int b) {
if (b<0) {
throw new ApplicationException("B must be a positive integer or zero");
}
if (b==0) return 1;
if (a==0) return 0;
if (b%2==0) {
return Power(a*a, b/2);
} else if (b%2==1) {
return a*Power(a*a,b/2);
}
return 0;
}


Another solution can be :
a^b = 10^(ln[10](a) * b)

Reference : http://www.osix.net/modules/article/?id=696

Details of retainAll() in Set interface

The Set interface contains a method 'retainAll()' which gives us the intersection of two sets.

Lets say we define a Set as : Set s = new HashSet();

HashSet class extends the abstract class AbstractSet , which in turn extends the abstract class AbstractCollection. The implementation of retainAll() is present in AbstractCollecction class.

This method Retains only the elements in this collection that are contained in the
specified collection (optional operation). In other words, removes
from this collection all of its elements that are not contained in the
specified collection.

This implementation iterates over this collection, checking each
element returned by the iterator in turn to see if it's contained
in the specified collection. If it's not so contained, it's removed
from this collection with the iterator's remove method.

Note that this implementation will throw an
UnsupportedOperationException if the iterator returned by the
iterator method does not implement the remove method
and this collection contains one or more elements not present in the
specified collection.

Class Loader methods : Why class loaders must delegate class loading

defineClass() : This method converts the array of bytes code an instance of the class.The class must be resolved before it can be used. THis is a final method. In this, an instance of class java.lang.Class is created and cached in the Class Loader so that the byte code can not change on the further requests to load the class. This method also checks that the given class name matches the class name in the byte code. Because this method is final, no custom class loader can change this behavior.


Q : Why class loaders must delegate class loading ?
As we know, a class loader must delegate the class loading(although a developer can override loadClass() and change this behavior). On one hand, if loading of system classes is not delegated, an application could provide malicious code for JDK classes and introduce a ton of problems. On the other hand, all classes at least extend java.lang.Object, and this class must be resolved, too. Thus the custom class loader has to load this class by itself, otherwise the load fails with a linkage error. These two facts imply that a custom class loader has to delegate class loading.

However,there are some loaders like the loader for web container defined in servlet specification, tries to load the class by itself before delegating.Nevertheless, some classes, such as java.*, javax.*, org.xml.sax.* and others, are delegated first to the parent.


As long as a Java developer does not deal with his or her own class loader, all of the classes are loaded by the bootstrap and system class loader, and there will never be a conflict. Thus, it seems that a class is defined only by the fully qualified class name. As soon as there are sibling class loaders -- neither a parent of the other -- a class type can be loaded multiple times with or without different byte code. The class loader also defines the visibility of a class type because any upcast checks against the class name as well as its class loaders.

To use the currency analogy, this is expressed by the fact that you can have several currencies in your wallet, but as soon as you want to use one, the cashier will check if your money is of the local currency. Still, you can carry these currencies in your pocket wherever you go, and likewise, you can carry around instances of classes even when they are unknown or not compatible in a particular class, as long as the class of the reference is compatible there. Luckily in Java, java.lang.Object is the superclass of all instances and is loaded by the BS, which is the parent of all class loaders no matter what. This means a reference of a class java.lang.Object is always compatible. I think of this as a "tunneling through" of classes from one compatible island to the next -- something that is very important in J2EE, as will be shown in a future installment.

'Extension' Class Loader

The extension framework makes use of the class-loading delegation mechanism. When the runtime environment needs to load a new class for an application, it looks for the class in the following locations, in order:
Bootstrap classes: the runtime classes in rt.jar, internationalization classes in i18n.jar, and others.
Installed extensions: classes in JAR files in the lib/ext directory of the JRE, and in the system-wide, platform-specific extension directory (such as /usr/jdk/packages/lib/ext on the SolarisTM Operating System, but note that use of this directory applies only to JavaTM 6 and later).
The class path: classes, including classes in JAR files, on paths specified by the system property java.class.path. If a JAR file on the class path has a manifest with the Class-Path attribute, JAR files specified by the Class-Path attribute will be searched also. By default, the java.class.path property's value is ., the current directory. You can change the value by using the -classpath or -cp command-line options, or setting the CLASSPATH environment variable. The command-line options override the setting of the CLASSPATH environment variable.
The precedence list tells you, for example, that the class path is searched only if a class to be loaded hasn't been found among the classes in rt.jar, i18n.jar or the installed extensions.

Unless your software instantiates its own class loaders for special purposes, you don't really need to know much more than to keep this precedence list in mind. In particular, you should be aware of any class name conflicts that might be present. For example, if you list a class on the class path, you'll get unexpected results if the runtime environment instead loads another class of the same name that it found in an installed extension.