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.