Popular Posts

Tuesday, January 25, 2011

Run time polymorphism in java

object that it is acting upon. In other words, polymorphism allows you define one interface and have multiple implementation. This is one of the basic principles of object oriented programming.

The method overriding is an example of runtime polymorphism. You can have a method in subclass overrides the method in its super classes with the same name and signature. Java virtual machine determines the proper method to call at the runtime, not at the compile time.

Let's take a look at the following example:

class veicle{
void whoAmI() {
System.out.println("I am a generic veicle.");
}
}
class carextends veicle{
void whoAmI() {
System.out.println("I am a car.");
}
}
class bus extends veicle{
void whoAmI() {
System.out.println("I am a bus.");
}
}

class RuntimePolymorphismDemo {

public static void main(String[] args) {
veicle ref1 = new veicle();
veicle ref2 = new car();
veicle ref3 = new bus();

ref1.whoAmI();
ref2.whoAmI();
ref3.whoAmI();

}
}

The output is

I am a generic veicle.
I am a car.
I am a bus.

String lterals

There are two ways to create a String object in Java:
Using the new operator.
For example,  String str = new String("Hello");.
Using a string literal or constant expression). For example,
String str="Hello"; (string literal) or
String str="Hel" + "lo"; (string constant expression).
What is difference between these String's creations? In Java, the equals method can be considered to perform a deep comparison of the value of an object, whereas the == operator performs a shallow comparison. The equals method compares the content of two objects rather than two objects' references. The == operator with reference types (i.e., Objects) evaluates as true if the references are identical - point to the same object. With value types (i.e., primitives) it evaluates as true if the value is identical. The equals method is to return true if two objects have identical content - however, the equals method in the java.lang.Object class - the default equals method if a class does not override it - returns true only if both references point to the same object.
Let's use the following example to see what difference between these creations of string:
The creation of two strings with the same sequence of letters without the use of the new keyword will create pointers to the same String in the Java String literal pool. The String literal pool is a way Java conserves resources.
public class DemoStringCreation {

public static void main(String args[]) {
String str1 = "Hello";
String str2 = "Hello";
System.out.println("str1 and str2 are created by using string literal.");
System.out.println(" str1 == str2 is " + (str1 == str2));// str1 == str2 is true
System.out.println(" str1.equals(str2) is " + str1.equals(str2));// str1.equals(str2) is true

String str3 = new String("Hello");
String str4 = new String("Hello");
System.out.println("str3 and str4 are created by using new operator.");
System.out.println(" str3 == str4 is " + (str3 == str4));// str3 == str4 is false
System.out.println(" str3.equals(str4) is " + str3.equals(str4));// str3.equals(str4) is true

String str5 = "Hel" + "lo";
String str6 = "He" + "llo";
System.out.println("str5 and str6 are created by using string constant expression.");
System.out.println(" str5 == str6 is " + (str5 == str6));// str5 == str6 is true
System.out.println(" str5.equals(str6) is " + str5.equals(str6));// str5.equals(str6) is true

String s = "lo";
String str7 = "Hel" + s;
String str8 = "He" + "llo";
System.out.println("str7 is computed at runtime.");
System.out.println("str8 is created by using string constant expression.");
System.out.println(" str7 == str8 is " + (str7 == str8));// str7 == str8 is false
System.out.println(" str7.equals(str8) is " + str7.equals(str8));// str7.equals(str8) is true
}
}
String Literal Pool :
String allocation, like all object allocation, proves costly in both time and memory. The JVM performs some trickery while instantiating string literals to increase performance and decrease memory overhead. To cut down the number of String objects created in the JVM, the String class keeps a pool of strings. Each time your code create a string literal, the JVM checks the string literal pool first. If the string already exists in the pool, a reference to the pooled instance returns. If the string does not exist in the pool, a new String object instantiates, then is placed in the pool. Java can make this optimization since strings are immutable and can be shared without fear of data corruption. For example
public class Program {
public static void main(String[] args) {
String str1 = "Hello";
String str2 = "Hello";
System.out.print(str1 == str2);//true
}
}
Unfortunately, when you use
String a=new String("Hello");
a String object is created out of the String literal pool, even if an equal string already exists in the pool. Considering all that, avoid new String unless you specifically know that you need it! For example
public class Program {
public static void main(String[] args) {
String str1 = "Hello";
String str2 = new String("Hello");
System.out.print(str1 == str2 + " ");//false
System.out.print(str1.equals(str2));//true
}
}
A JVM has a string pool where it keeps at most one object of any String. String literals always refer to an object in the string pool. String objects created with the new operator do not refer to objects in the string pool but can be made to using String's intern() method. The java.lang.String.intern() returns an interned String, that is, one that has an entry in the global String pool. If the String is not already in the global String pool, then it will be added. For example
public class Program {
public static void main(String[] args) {
// Create three strings in three different ways.
String s1 = "Hello";
String s2 = new StringBuffer("He").append("llo").toString();
String s3 = s2.intern();

// Determine which strings are equivalent using the == operator
System.out.println("s1 == s2 ? " + (s1 == s2));//s1 == s2? false
System.out.println("s1 == s3 ? " + (s1 == s3));//s1 == s3? true
}
}
There is a table always maintaining a single reference to each unique String object in the global string literal pool ever created by an instance of the runtime in order to optimize space. That means that they always have a reference to String objects in string literal pool, therefore, the string objects in the string literal pool not eligible for garbage collection.

String Literals in the Java Language Specification Third Edition
Each string literal is a reference to an instance of class String. String objects have a constant value. String literals-or, more generally, strings that are the values of constant expressions-are "interned" so as to share unique instances, using the method String.intern.
Thus, the test program consisting of the compilation unit:
class Other {
static String hello = "Hello";
}

class Test {
public static void main(String[] args) {
String hello = "Hello", lo = "lo";
System.out.println((hello == "Hello") + " ");//true
System.out.println((Other.hello == hello) + " ");//true
System.out.println((Other.hello == hello) + " ");//true
System.out.println((hello == ("Hel" + "lo")) + " ");//true
System.out.println((hello == ("Hel" + lo)) + " ");//false
System.out.println(hello == ("Hel" + lo).intern()); //true
}
}
This example illustrates six points:
Literal strings within the same class in the same package represent references to the same String object.
Literal strings within different classes in the same package represent references to the same String object.
Literal strings within different classes in different packages likewise represent references to the same String object.
Strings computed by constant expressions are computed at compile time and then treated as if they were literals.
Strings computed by concatenation at run time are newly created and therefore distinct.
The result of explicitly interning a computed string is the same string as any pre-existing literal string with the same contents.
Refer : http://www.xyzws.com/javafaq/what-is-string-literal-pool/3

Autoboxing and unboxing

From primitive type to it corresponse wrapper class is called autoboxing, the reverse process is called unboxing. Autoboxing and unboxing also apply to methods calls. For example, you can pass an argument of type int to a method that has a formal parameter of type Integer.

A NullpointerException exception occurs When unboxing an null wrapper class's reference to its primitive type. For example, the code will compile but it will throw a NullpointerException at runtime.
...
Long L = null;
long l = L;
...
Boxing conversion converts values of primitive type to corresponding values of reference type. But the primitive types can not be widened/Narrowed to the Wrapper classes and vice versa. For example,
byte b = 43;

Integer I1 = 23; //Constant integer value
Integer I2 = (int)b; //Cast to int type

Long L1 = 23; //compile error because 23 is integer value
Long L2 = (Long)23; //can not cast integer value to Long wrapper class

Long L3 = 23L;
Long L4 = (long)23;

This restriction is also applied to method invocation:

public class MyClass {
public void method(Long i) {
System.out.println("Here");
}
public static void main(String[] args) {

MyClass s = new MyClasslass();
//s.method(12); // error
s.method(12L); // ok
}

}
When invoking a method from multiple overloading methods, For the matching method process, the Java compiler will perferance the order of primitive types.


Autoboxing is guaranteed to return the same object for integral values in the range [-128, 127], but an implementation may, at its discretion, cache values outside of that range. It would be bad style to rely on this caching in your code. Also, The Java Language Specification does not explicitly guarantee this behavior for long values within the range of a byte.

Creating a wrapper object by using keyword new will return different reference. For example,

class Program {
public static void main(String[] args) {
Integer i1 = 20;
Integer i2 = new Integer(20);
Integer i3 = new Integer(20);
System.out.println(i1 == i2);
System.out.println(i1 == i3);
}
}
The output is

false
false


class Program {
public static void main(String[] args) {
Integer i1 = 20;
Integer i2 = 20;
Integer i3 = 201;
Integer i4 = 201;
System.out.println(i1 == i2);
System.out.println(i3 == i4);
}
}
The output is

true
false

For small integral values, the objects are cached in a pool much like String pool. When i1 and i2 have the value of 20, they both point to a single object in the cache pool. While i3 and i4 have the value of 201, two separate objects are referenced.

Saturday, January 22, 2011

Applications of Priority Heaps

how to use a priority heap as the sorting machine to produce merged parts of large (internally) sorted sections . If a sorted section took M memory and the sorting problem was k x M big, then take sequential sections of each of the k sections of size M/k , at a time, so they fit in M memory ( k * M/k = M ), and feed the first element of each of k sections to make a k sized priority queue, and as the top element is removed and written to an output buffer, take the next element from the corresponding section. This means elements may need to be associated with a label for the section they come from. When a M/k-sized section is exhausted, load in the next M/k sized minisection from the original sorted section stored on disc. Continue until all minisections in each of the k sections on disc have been exhausted.
(As an example of pipelining to fill up disc operational delays, there are twin output buffers, so that once an output buffer is full one gets written the disc while the other is being filled.)
This paper showed that a priority heap is more straightforward than a binary tree, because elements are constantly being deleted, as well as added, as a queuing mechanism for a k way merge, and has practical application for sorting large sets of data that exceed internal memory storage.

Heapsort: One of the best sorting methods being in-place and with no quadratic worst-case scenarios.
Selection algorithms: Finding the min, max, both the min and max, median, or even the k-th largest element can be done in linear time (often constant time) using heaps.[4]
Graph algorithms: By using heaps as internal traversal data structures, run time will be reduced by polynomial order. Examples of such problems are Prim's minimal spanning tree algorithm and Dijkstra's shortest path problem.
Full and almost full binary heaps may be represented in a very space-efficient way using an array alone. The first (or last) element will contain the root. The next two elements of the array contain its children. The next four contain the four children of the two child nodes, etc. Thus the children of the node at position n would be at positions 2n and 2n+1 in a one-based array, or 2n+1 and 2n+2 in a zero-based array. This allows moving up or down the tree by doing simple index computations. Balancing a heap is done by swapping elements which are out of order. As we can build a heap from an array without requiring extra memory (for the nodes, for example), heapsort can be used to sort an array in-place.
One more advantage of heaps over trees in some applications is that construction of heaps can be done in linear time using Tarjan's algorithm.


refer : for diagramatic explanation

When to use static class

We use static class when we have to separate data and behavior that will be independent of any object identity. The data and functions do not change regardless of what happens to the object.

A static class can only contain static members. We cannot create an instance of a static class. Static class is always sealed and they cannot contain instance constructor. Hence we can also say that creating a static class is nearly same as creating a class with only static members and a private constructor (private constructor prevents the class from being instantiated).

The advantage of using the static class is that compiler can check that no instance of the class is accidentally added. The complier will not allow any instance class of a static class. We also cannot inherit a static class since it is sealed. Static class do not have constructor, but can still declare static constructor to set up the initial values.

Static class also makes the implementation simpler and faster since we do not have make and instance of the class to call its method. An example of good use of static class would be a class like math, which does all the mathematic function, or a currency converter class to convert currency class for converting the currency.
              Refer here for article relating to inheritance of static methods.Static methods will be inherited as normal methods.If type cast it to super class then super class static method will be invoked.

Sunday, January 2, 2011

Coins in a Line

We have an array of integers which has numbers in it.each integer represents a currency note.You and your friend playing a game in which each can either take number(money) from left or right.That is each step you have two options either you take left most currency note or right most currency note.Now you need to maximize your money.

ex : array = {5,9,2,3}

Maximum amount we can make is {3,9} 9+3 = 12.

Java code for calculating maximum mount we can get in this play is :
public class MaxSumOfCoins {

public static void main(String[] args) {
int[] a = { 3, 2, 2, 3, 1, 2 };
int maxSum = getMaxSum(a, 0, a.length - 1);
System.out.println("Maximum sum we can obtain in this play is : "
+ maxSum);
}

private static int getMaxSum(int[] a, int i, int j) {

if (j < 0 || i > a.length - 1 || i > j)
return 0;

// P1 = Ai + min { P(i+2, j), P(i+1, j-1) }
int selectIandIplus1 = getMaxSum(a, i + 2, j);
int selectIandJ = getMaxSum(a, i + 1, j - 1);
int p1 = a[i]
+ (selectIandIplus1 < selectIandJ ? selectIandIplus1
: selectIandJ);

// P2 = Aj + min { P(i+1, j-1), P(i, j-2) }
int selectJandIplus1 = getMaxSum(a, i + 1, j - 1);
int selectJandJminus1 = getMaxSum(a, i, j - 2);
int p2 = a[j]
+ (selectJandIplus1 < selectJandJminus1 ? selectJandIplus1
: selectJandJminus1);

return p1 > p2 ? p1 : p2;
}
}
Refer : http://www.leetcode.com/2011/02/coins-in-line.html

TODO : print selcted coins in ur turn.

Saturday, January 1, 2011

Logical gates algorithm

You have a tree(binary tree) having nodes such that all the internal nodes are either OR(bitwise '|' or bitwise AND '&') and all the leaves are either '0' or '1'.

eg:
AND
/ \
OR AND
/\ /\
AND 0 0 1
/\
0 0


Now we will be given a value which we need to get at root that can be either 0 or 1.
Now we need to find minimum number of gates we need to change in order to get the desired value at the root.

Value at any node is evaluated simply ='left->node' operation at node 'right->node'

like in this case if we need 1 at root then we require to change only one AND gate to OR gate.
ANS is 1.