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.

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.

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.

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.

How free(pointer) works?

MMU(Memory Management Unit) simply stores the number of bytes allocated at say p location and then you get to store the content starting from p th position up till n bytes.
So when free(p) is to be used MMU simply sees the values stored at p and deallocates that much amount of bytes.

Quad Tree Algorithm

aGiven a city in the form of a square.There are various cell towers located at various points in the square city(say (x,y)).The distribution of towers is totally random.Now given an (x,y) point,design a data structure that help you tell whether the cell tower is present in the location or not.

Ans: We can solve it using quad tree.