Builder pattern using Lombok

The idea of builder pattern is simple. It provides users with a better interface to construct a complex object - in other words better readability at the site an object is created. Another important aspect which is sometimes missed is that the patten helps in achieving immutability unlike having getter/setter methods with in the class.

When it comes to implementing the pattern, I am a bit biased towards the way Effective Java advocates. It preserves the class’s contract by specifying mandatory parameters through constructor.

Certainly when creating libraries or APIs its better to start off with builders if we want to create immutable objects and there are more than ‘x’ number of optional parameters. I generally consider 4 as a guideline for ‘x’.

Now all this can be easily achieved using lombok. @Builder annotation auto-generates the inner builder classes. What I don’t like is the lack of support of compile time check for mandatory attributes of a class. At the time of this writing there seems to be some thought process going on within lombok’s dev community to support the same as per this link.

Until then the tradeoff to use lombok is the ease to create builders versus the compile-time check for mandatory attributes. The consistency of the object's state can be managed through run time validations and hence the compile-time check is not a show stopper.

Overall I vote a Yes to use lombok's @Builder and am hoping that the support of compile time validation is available sooner than later.

Type conversion to Unit in Scala

In Scala we can write the following which raises the concern how the type conversion works for Unit type.

def f(a: Unit) = println("invoked f with Unit type: " + a)

f(42)

f("temp")

The type conversion is not based on any implicit conversions defined in Predef object or is not based on sub-typing.

As per Scala Language Specification (SLS) there is an implicit conversion performed by the compiler. Excerpt form the SLS below -

Value Discarding. If e has some value type and the expected type is Unit, e is converted to the expected type by embedding it in the term { e; () }.

The only value that Unit type can take is (). It does not represent any runtime object and is defined in the SLS section 12.2.3.

Moreover, a 0-tuple is also represented using the Unit value [SLS section 6.9]. It denotes the absence of any useful value, which makes sense since for a 0-tuple, there is no operation that seems to be useful. However, this results another type for tuples to deal with as if Tuple1, Tuple2, Tuple3.... Tuple22 wasn't enough.

PS: To generate a warning for this implicit conversion we can use scalacOptions += "-Ywarn-value-discard" in SBT configuration

To compare or not to compare !

It is well known that null and undefined are unique in Javascript. However the following behavior was not known to me and hence the post. Basically null is coerced to 0 when using >, <, >=, <= operators but not when == operator is used. Quirky at its best :)

Stack with getMin operation in O(1) time

This is a famous interview problem where the candidate is asked to design a stack so as to get minimum of the current elements present in the stack in O(1) time. I think having an auxiliary stack is the most general solution.

Found the following link to do it without using extra space obviously with some constraint on the data present in the stack, nonetheless solution deserves an "aha"!
http://stackoverflow.com/a/687945

Longest matching pattern

Given two strings find the longest matching pattern such that the pattern in the first string and the second string are permutation of each other.

Eg. - 
S1 = “ABCDEFG”
S2 = “DBCAPFG”
Then the output should be DBCA (length 4)
Assume there are no repeating characters.

Solution -
The idea is to transform S1 into clusters of indices of S2. So, for the example above we will get
Cluster 1 - 3, 1, 2, 0
Cluster 2 - 5, 6

Now, for each cluster find the longest portion (window) that satisfies the following property - 

• Max - Min + 1 = No of Elements

The longest portion (window) of the cluster will represent the indices of S2 that are contiguous and since the cluster itself is a a contiguous portion of transformed S1, the final solution will be the characters in S2 at the indices represented by such longest portion.

To find the longest portion satisfying the above property, we can recursively implement it as shown below in method getMaxCommonWindow. The idea is to find the maximum window starting with the first element satisfying the above property and then recusively find the maximum window not starting with the first element. The greater of these two windows will be the desired longest portion.

Count the number of six digit numbers possible

The problem is to calculate the number of 6-digit numbers that you can create using the following scheme of things.

0-9 digits are arranged like a phone keypad.
1 2 3
4 5 6
7 8 9
   0

The 6-digit number cannot start with 0. A digit can follow any other digit in the 6-digit number only if both the numbers are in the same row or column.
For eg. in a 6-digit number:
2 can follow 0
0 can follow 8
9 can follow 7
5 can follow 4
4 can follow 1
1 can follow 7
...
...
9 cannot follow 5
1 cannot follow 6
0 cannot follow 1
...
...

The idea of the solution is to use dynamic programming. A possible implementation is given below. To further optimize we can do memoization.

String rotation

Given a string of length N, rotate the string by K units. Eg. rotation of abcdef by 2 units will result in cdefab.

Solution approaches:-
1) Using a temp Array
2) 1 shift at a time 
3) Juggling algorithm - uses GCD(N,K) outer loop and inner loop till cycle is encountered
4) Gries algorithm - divide and conquer
5) Reversal algorithm - revert individual blocks and then revert the full string
 
Links:-
Source - http://www.cs.bell-labs.com/cm/cs/pearls/s02b.pdf
Solution - http://www.geeksforgeeks.org/archives/2398
Solution - http://www.geeksforgeeks.org/archives/2878
Solution - http://www.geeksforgeeks.org/archives/2838
Solution and Performance - http://www.drdobbs.com/article/print?articleId=232900395&siteSectionName=parallel
 
Juggling algorithm explanation:-
Taken from http://eli.thegreenplace.net/2008/08/29/space-efficient-list-rotation/

Now, are you asking yourself "Just when will the process come back to x[0], and how many elements will have been moved by that stage ?". So did I, and the answer turns out to be an exciting application of the greatest common divisor (GCD) function.

In the first iteration, the "juggling pointer" jumps i elements at a time and stops when it reaches 0. How many steps will this take ? Ignoring the modulo for a moment, To reach 0, the pointer must be a multiple of n, so 0 will be reached at an index that is a multiple of both i and n. The first such multiple, in fact.

The first multiple (also known as LCM – least common multiple) is easy to compute from the GCD.

The amount of steps is lcm(n, i) / i. This is n / gcd(n, i). Therefore, in each iteration, n / gcd(n, i) elements will be rotated. The next iteration will pick up at x[1], an keep hopping in steps of i from there, moving another n / gcd(n, i) elements. In special cases, like when n and i are coprime, the first iteration will run over all the elements in the vector, without the need for a second one.

In any case, the whole process will always make n steps in total, moving all the elements to their correct positions.

Shuffling

Q: Given an array, print a random permutation of it such that each permutation is equally likely.

• The first approach is to use a random number generator to generate a value between 0 - 1 and associate each element of the array with a random value. Now sort the array based on these random values associated with the array elements.
• The second approach is to iterate over the array and swap the current element with another randomly selected element - Knuth-Fisher-Yates algorithm.
• Care should be taken so that we do not perform biased shuffle as explained in the following blog entry http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html by Jeff Atwood

Java code for the second approach is given below. The biasedShuffle and knuthShuffle methods are called 100000 times each to gather statistics and to further corroborate the explanation by Jeff.

 

Repeating substring

Q: Given a string S find the smallest sub-string X such that S = (X)+, i.e. S is a repetition of one or more X's.

Soln approach: 

• Iterate string from start to end keeping 2 pointers pointing to certain indexes in the string
• The first one indicating endIndex of the sub-sequence X found till now
• The second one indicating the index with which we must compare the character read in the next iteration
• Update both the indexes in each iteration based on whether the character read matches the sub-sequence 
• At the end X will be the sub-string from 0 to the first index mentioned in first point above

Java code:

Array Product

Q: Given an unsorted array of I of N integers, find an array O of N integers such that O[i] is the product of all integers in I except I[i]. Solve without using division.

Soln approach: 
1. Break the product into two parts as O[i] = (I[0] * I[1] * ... * I[i-1]) * (I[i+1] * ... * I[N-1])

2. Calculate first part by iterating over I from 0 to N-1
3. Multiply the values from step 2 with the second part by iterating over I from N-1 to 0

Java code to do this:

Sum of bits set

Q: Given a positive integer N calculate the sum of bits set for all the numbers from 0 to N.

I will be using divide and conquer for this. 

Fact: The sum of all set bits from 0 to (2 ^ n) - 1 is (2 ^ n-1) * n
This can be proved by induction or construction.

Approach:

1) Get the MSB location of the integer N, i.e. the left most bit which is set as 1, lets say it is X

2) Get the sum of all the bits till (2 ^ X) - 1 using the fact given above, lets say it is Sum

3) Now, add 1 for number (2 ^ X) to Sum

4) We are now left to calculate from (2 ^ X) + 1 to N. All these will have Xth bit set.
5) So add N - (2 ^ X) to Sum
6) Now we can solve for a smaller sub-problem using recursion. The numbers left are (2 ^ X) + 1 ..... N, with the Xth bit now turned off since we have already considered the Xth bit in step 5. This is equivalent to finding the sum of bits till N XOR (2 ^ X)

Code:
To get the MSB location we can again use divide and conquer to reduce the no. of steps.
http://graphics.stanford.edu/~seander/bithacks.html

Ideas taken from:
http://tech-queries.blogspot.in/2010/12/number-of-set-bits-till-n.html
http://code.rishibaldawa.com/count-all-set-bits-from-0-till-n-for-each-number

Duplicate & missing number

Q: In an unsorted array of first N natural numbers which has a duplicate number and a missing number, find the duplicate and missing numbers.

Soln approach: 

1. Sum of N numbers = n(n+1)/2

2. Sum of N^2 numbers = n(n+1)(2n+1)/6

3. Since there are 2 unknowns we can create 2 equations using the above formulae to solve them

Soln approach: 

1. Sum of N numbers = n(n+1)/2

2. Multiplication of N numbers / n! = Duplicate/Missing

3. Again we can solve for the 2 unknowns using the above formulae

Both the above approach assumes that N^2 or N! can be held in an int/double etc without overflow. In Java we can make use of BigInteger but there is another approach to solve the problem using bit operators.

Soln approach:

Let Ai be the ith element of the array, 0 <= i < n

Let Bi be i+1

1. Find Duplicate XOR Missing = X

    - XOR all Ai and Bi

2. Find which rightmost bit is 1 in X = Y

    - X & ~(X - 1)

3. Partition A and B such that A1 and B1 has Y set and A2 and B2 does not have Y set

    - Iterate and use & operator over Y and elements of A and B

4. XOR elements of A1 and B1 = VALUE1

5. XOR elements of A2 and B2 = VALUE2

6. If A1.length > B1.length then VALUE1 = Duplicate and VALUE2 = Missing

    else VALUE2 = Duplicate and VALUE1 = Missing

Online Image Manipulators

Today, I was just googling for the online image manipulators and found this blog entry worth keeping track of. Thanks for the info. Just to copy the most relevant information from that page:

A list of free online image editors:

* Snipshot
* Picnik
* FotoFlexer
* Pixer.us
* Pixlr
* Phixr
* WebPicTool
* Splashup
* Resizr
* Photoshop Express
* Imageeditor.net

JNDI and OC4J

Got stuck into something and considered it interesting to keep a note of. If you are a J2EE developer and using Oracle Application server (OC4J) then the following information may be useful.

In OC4J if you have user created threads (not implicit threads of Servlet etc) and you want to do a JNDI lookup in that thread, then an OC4J start-up option needs to be set, otherwise the lookup would fail. The option is "-userThreads" and can be set using EM console (OC4J -> Administration -> Server Properties -> Start-parameters: OC4J Options).

Here is the detail of all such available OC4J options.

IoC and DI

Good read on IoC and DI

http://martinfowler.com/bliki/InversionOfControl.html
http://martinfowler.com/articles/injection.html

Something that cleared my thought process (an excerpt from one of the articles)
Inversion of Control is a key part of what makes a framework different to a library.

Autoboxing and Equality

Tiger(JDK 5) has introduced a lot of features and in turn lots more to dig into. Here I want to explain the issues that arise due to equality comparisons and Autoboxing/Auto-unboxing.

Since, equality operator (==) can be used with reference variables and primitive types, the first question is what happens when we equate reference wrapper variable with its corresponding primitive type.

int i = 1;
Integer iObj = new Integer(i);
System.out.println(i==iObj);

Here, the iObj will be unboxed to a primitive type and the result of the expression would be similar to the comparison of int value with iObj.intValue().

If we equate two reference wrapper variables it is not the value comparisons but object comparison.

Also, JLS recommends that the same wrapper objects should be returned on autoboxing for lower values of the integer primitives. This accounts for some of the unusual behaviour of the equality expressions.

The program and the output below self-explains the issues

package autoboxing;

public class EqualityTest {

 public static void main(String[] args) {
  // any arbitrary value
  int i = 236459;
  Integer iObj = new Integer(i);
  
  /*
   *  if wrapper object is equated with primitive 
   *  types wrapper object would be converted to 
   *  primitive type and then compared
   */
  
  if(i == iObj) {
   System.out.println("Integers are equal: " + i);
  }
  
  for(int loop = -128; loop < Integer.MAX_VALUE; loop++) {
   Integer iObj1 = loop;
   Integer iObj2 = loop;
   
   /*
    * this is a reference equality check and not value 
    * comparison 
    */ 
   if(iObj1 == iObj2) {
    
   } else {
    System.out.println("Integers are not equal: " + loop);
    break;
   }
  }
  
  for(int loop = -128; loop < Integer.MAX_VALUE; loop++) {
   Integer iObj1 = new Integer(loop);
   Integer iObj2 = new Integer(loop);
   
   /*
    * this is a reference equality check and not value 
    * comparison 
    */ 
   if(iObj1 == iObj2) {
    
   } else {
    System.out.println("Integers are not equal: " + loop);
    break;
   }
  }
 }
}


Output:
Integers are equal: 236459
Integers are not equal: 128
Integers are not equal: -128

Calling non-public methods

A very small and simple hack to call non-public methods in Java.

Problem
~~~~~~~
A non-public method of a class has to be called from another class. Both the classes are in different packages.

package apipackage;
public class APIClass {
 void methodA() {
   System.out.println("methodA Called");
 }
}

package clientpackage;
public class ClientClass {
 void methodACaller() {
 ...
 ...
 ...
 }
}

Fill in the dotted lines to call methodA of APIClass.

Solution
~~~~~~~~

package clientpackage;
// import statements
public class ClientClass {
 void methodACaller() {
  apipackage.APIClass apiObject = new apipackage.APIClass();
  Method methodA = apipackage.APIClass.class.getDeclaredMethod("methodA", null);
  methodA.setAccessible(true); // this makes it possible to invoke methodA
  methodA.invoke(apiObject, null);
 }
}

One important thing to remember is to call "getDeclaredMethod" and not "getMethod" to obtain the Method object.

From Java docs:
"getMethod returns a Method object that reflects the specified public member method of the class"

/*
   This would not work
   Method methodA = apipackage.APIClass.class.getMethod("methodA", null);
*/

JavaSpecialists Notes - II

Issue 18: Class names don't identify a class

We can also let these two "A" classes have a common superclass. For example, 
say we have a superclass called Parent.java located in the root directory:

//: Parent.java
public class Parent {
  public String toString() {
    return "Thanks for caring... but what do you want??? ";
  }
}

And our A.java classes are now written as:

//: a1/A.java
public class A extends Parent {
  public String toString() {
    return super.toString() + "This is the first class";
  }
}
//: a2/A.java
public class A extends Parent {
  public String toString() {
    return super.toString() + "This is the second class";
  }
}

We then need to have a common parent ClassLoader which we use to load the 
Parent.class file. We have to specify the location to start looking for 
Parent.class, and the locations are searched in a hierarchical fasion. Note that the 
compile-time Parent class is loaded with a different ClassLoader to the one loaded 
with the URLClassLoader called "parent" so they refer to a different class 
altogether, which means we cannot type-cast an instance of "A" to a Parent. Also, if 
we load the class "Parent" without using the classloader, we will see that it is not 
equal to the superclass of "c1".

//: Loader.java
import java.net.*;
public class Loader {
  public static void main(String[] args) throws Exception {
    ClassLoader parent = new URLClassLoader(
 new URL[] {new URL("file:./")}, null);
    ClassLoader a1 = new URLClassLoader(
 new URL[] {new URL("file:a1/")}, parent);
    ClassLoader a2 = new URLClassLoader(
 new URL[] {new URL("file:a2/")}, parent);
    Class c1 = a1.loadClass("A");
    Class c2 = a2.loadClass("A");
    System.out.println(c1.newInstance());
    System.out.println(c2.newInstance());
    System.out.println(
 c1.getSuperclass().equals(c2.getSuperclass()));
    System.out.println(
 Class.forName("Parent").equals(c1.getSuperclass()));
    try {
 Parent p = (Parent)c1.newInstance();
    } catch(ClassCastException ex) {
 ex.printStackTrace();
    }
    System.out.println("We expected to get ClassCastException");
  }
}

Thanks for caring... but what do you want??? This is the first class
Thanks for caring... but what do you want??? This is the second class
true
false
java.lang.ClassCastException: A
        at Loader.main(Loader.java:18)
We expected to get ClassCastException

Note that the super classes of both "A" classes are equal.

Where is this all this useful? It is very useful when you have an application server 
into which you want to deploy business objects written by different people. It is 
entirely feasible that you have two developers with different versions of classes 
deploying their applications onto the same server. You don't necessarily want to 
start a new VM for each deployment, and so with ClassLoaders it is possible to have 
lots of classes with the same name running in the same memory space but not 
conflicting with one another. They would also share the common JDK classes with one 
another, so we would not have to have a java.util.ArrayList class loaded for each of 
the ClassLoaders. 

JavaSpecialists Notes - I

This is the first part of a series of blogs that I would write in order to keep the crux of all the JavaSpecialists Newsletters at one place for a quick reference. It would include the links and excerpts from the original newsletter.

Issue 1: Deadlocks

In Swing, all GUI components have to be changed from within the Swing thread. 
This means that you cannot execute jLabel1.setText("blabla") from within any thread 
besides the Swing thread. 
If you have change any GUI from another thread you should rather say: 
SwingUtilities.invokeLater(new Runnable() {
  public void run() {
    jLabel1.setText("blabla");
  }
}

Issue 2: Anonymous Inner Classes

If you wanted to pass in a Collection instead of an array it would look as follows:

Collection temp_names = new Vector(3);
temp_names.add("Heinz");
temp_names.add("John");
temp_names.add("Anton");
universityRegistration.addNames(temp_names);

The ability to avoid local temporary variables with arrays was always a strong 
deciding factor in defining interfaces to my classes because I could get away with 
one line of code instead of five, and the less lines of code the better. I would 
therefore rather define addNames(String[] names) than addNames(Collection names) even
if it meant I would have to convert backwards and forwards between arrays and 
collections. However, with anonymous inner classes we can get the same effect seen 
above but with collections:

universityRegistration.addNames(new Vector(3)
  {{ add("Heinz"); add("John"); add("Anton"); }});

Issue 8: boolean comparisons

boolean pentiumTMcpu = Utils.isCpuAPentium();
if (pentiumTMcpu == true) {
  /* work out incorrect salary using double */
}

This will compile fine in Java, but so will the following, which assigns true to 
pentiumTMcpu and will always work out the salary using the Pentium bug (younger 
readers would not remember):

boolean pentiumTMcpu = Utils.isCpuAPentium();
if (pentiumTMcpu = true) {
  /* this code will always be executed */
}

Instead, it would be a lot safer to write

boolean pentiumTMcpu = Utils.isCpuAPentium();
if (pentiumTMcpu) {
  /* work out incorrect salary using double */
}
.........
.........
.........
There is a technique used alot in Microsoft's C++ libraries in which they would have 
written the comparison as:

boolean pentiumTMcpu = Utils.isCpuAPentium();
if (true == pentiumTMcpu) {
  /* work out incorrect salary using double */
}

More would follow as and when I would read other issues. :)

Java XML binding

A nice article on Java-XML binding using VTD-XML. Especially, I liked the first comment, may be "contrarian" fascination.