Tuesday, December 24, 2013

Static Class in Java

Consider a class with utility methods. In this case instantiating an instance every time we need those methods, does not make sense. So what exactly should be done.

Should we go with abstract class? An abstract class may not make sense as we do not expect derived classes to provide any implementation. We can go with a static class (Here I mean a class with static methods).

So, When do we need to write a static class?
When we have a bunch of utility methods and instantiation of the class seems nonsensical.

So what is the best way to write a static class?1
Enforce noninstantiability  by using private constructor (from Effective Java, Item 4)
  1. Attempting to enforce noninstantiability by making a class abstract does not work.
  2. A default constructor is generated only if a class contains no explicit constructors, so a class can be made noninstantiable by including a private constructor:
So we need: A class with private constructor and static methods.

As the constructor is private it is not accessible to outside world so there can not be any derived class. Though not needed, we can also make the class final as there is no harm in being explicit.
// Noninstantiable utility class
public class UtilityClass
{
    // Suppress default constructor for noninstantiability
    private UtilityClass() {
        throw new AssertionError();
    }
}

An Assertion Error is a good idea as it ensures us in case the constructor is invoked accidentally with in the class. As a side effect this class cannot be extended now.

We should keep in mind one thing: Static methods are death to testability. Also they do not participate in Object Oriented world and therefore are considered bad by few people.

In the above article I used the term Static class to mean the class with static methods. Otherwise only nested classes can be static.
class OuterClass{
    public static class StaticNestedClass{
    }

    public class InnerClass{
    }

    public InnerClass getAnInnerClass(){
        return new InnerClass();
    }

    //This method doesn't work
    public static InnerClass getAnInnerClassStatically(){
        return new InnerClass();
    }
}

class OtherClass{
    //Use of a static nested class:
    private OuterClass.StaticNestedClass staticNestedClass = new OuterClass.StaticNestedClass();

    //Doesn't work
    private OuterClass.InnerClass innerClass = new OuterClass.InnerClass();

    //Use of an inner class:
    private OuterClass outerclass= new OuterClass();
    private OuterClass.InnerClass innerClass2 = outerclass.getAnInnerClass();
    private OuterClass.InnerClass innerClass3 = outerclass.new InnerClass();
}
All static methods (in fact all the methods) and static variables are stored in the PermGem section of the heap, since they are part of the reflection data (class related method and not instance related). The variables (or variable definitions) are store in PermGen section but the objects they refer to get stored somewhere on the heap. More can be found here.

More about garbage collection and memory allocation can be read here and here.

Monday, December 16, 2013

Algorithms:Intersection point of two linked lists in Y shape

Algorithms Series

We are given two linked lists that intersect at a point and then become one. The number of nodes in each list before they intersect are unknown and they may be different (m and n say). We need an algorithm to find the intersection point. This can be shown by this image:
Linked Lists

The simplest is to go with brute force where each node of the first is compared with every other node of the other list. The matching node pointers will lead us to the intersecting node. 
Lame Approach

Time complexity: O (mn)             Space Complexity: O (1)




Can we use Hash Table? Yes. 
 The approach is:
  1. Select the list having less number of nodes and store it in hash table.
  2. Traverse the second list and check whether the same node pointer exists in the hash table.
  3. If it does we get intersection point.


Intersection using marker
Time complexity: Time for creating the hash table + time for scanning the second list
O (m) + O (n)

 Space Complexity: O (n) or O (m)

Can we use stacks to solve it? Yes. The approach is as:
  1. Push both the lists on stacks. The top of both will have the last element of the lists.
  2.  Compare the top elements on two stacks.
    1. If they are same pop them and store them.
    2. If they are not, it means the common element has just popped out in previous step.
  3. The value popped out in previous step can then be returned.
Time complexity:  O (m + n)                       Space complexity: O (m + n)

Can we use the first repeating number? Yes.
  1.  Create an array and keep all the next pointers of both the lists in the array.
  2.  In the array find the first repeating element in the array. The first repeating number is the intersection point.

Time complexity:  O (m + n)                       Space complexity: O (m + n)

Do we have any other approach? Yes by combining sorting and searching.
  1.  Create an array and keep all the next pointers of first list in the array.
  2.  Sort it (assume binary sort is used O (logn) ).
  3. Then for each element in second list, search it in this sorted array.
    1. If we find it then it is intersection point.

Time complexity:  Time for sorting + Time for searching = O (Max (mlogm, nlogn))                          
Space complexity: O (Max (m, n))

Do we have any efficient approach? Yes.
The approach is to compute lengths of the two lists in linear time. Then advance the longer list by difference in length of two lists and then start comparing.
  1.  Find lengths (L1 and L2) of both the lists. O(n) + O(m) = O( Max (m, n))
  2.  Take the difference (d) of the lengths. O(1)
  3.  Make d steps in longer list. O(d)
  4. Step in both lists in parallel until links to next node match. O (Min (m, n)).

Time complexity:  O (Max (m, n))            Space Complexity: O (1)

ListNode FindIntersectingNode(ListNode list1, ListNode list2)
{
  int L1=0, L2=0, diff=0;
  ListNode head1 = list1, head2 = list2;
  while(head1 != null) {
   L1++;
   head1 = head1.getNext();
  }
  while(head2 != null) {
   L2++;
   head2 = head2.getNext();
  }
  diff = L1 – L2;
  if( L1 < L2) {
    head1 = list2;
    head2 = list1;
    diff = L2 – L1;
  }
  for(int count = 0; count < diff; count++) head1 = head1.getNext();
  while(head1 != null && head2 !+ null) {
    if(head1 == head2) return head1.getData();
    head1 = head1.getNext();
    head2 = head2.getNext();
  }
  return null;
}

Disclaimer: The images and various examples are taken from internet. I do not claim them as my own ideas. I have tried to mark the proper references but in case anything is missing please let me know.

Saturday, December 14, 2013

Algorithms:Partition of a Number

Algorithms Series

So if you do not know what do I mean by partition of a number, then here it is:

A partition of a positive integer n is, a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition (For example 1+2+3 and 1+3+2 are same). If order matters then the sum becomes a composition.

Partition(4) = 5
 
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

Then we have another related term Restricted Partition which is partition having some constraints. For example partition having only odd numbers, partition having only 1 and 2 etc.

In number theory, the partition function p(n) represents the number of possible partitions of a natural number n, which is the number of distinct ways of representing n as a sum of natural numbers.
\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \left(\frac {1}{1-x^k} \right).

The right side term on expansion becomes:
(1 + x + x2 + x3 + ...)(1 + x2 + x4 + x6 + ...)(1 + x3 + x6 + x9 + ...) ....




Partitions can also be visualized by Young diagrams or Ferrous diagrams. 

Young Diagram makes use of boxes and Ferrous Diagrams make use of dots to represent the same information  (as shown below).


The partition 6 + 4 + 3 + 1 of the positive number 14 can be represented by:
****
***
***
**
*
*

So the problem is to write an algorithm that will print all the partitions for a number. There is one very good implementation at Princeton university page under the topic of recursion. Here it is reproduced:

public class Partition { 

    public static void partition(int n) {
        partition(n, n, "");
    }
    public static void partition(int n, int max, String prefix) {
        if (n == 0) {
            StdOut.println(prefix);
            return;
        }
  
        for (int i = Math.min(max, n); i >= 1; i--) {
            partition(n-i, i, prefix + " " + i);
        }
    }


    public static void main(String[] args) { 
        int N = Integer.parseInt(args[0]);
        partition(N);
    }

}

% java Partition 4      % java Partition 6
4                       6
3 1                     5 1
2 2                     4 2
2 1 1                   4 1 1
1 1 1 1                 3 3
                        3 2 1
                        3 1 1 1
                        2 2 2
                        2 2 1 1
                        2 1 1 1 1
                        1 1 1 1 1 1

Let me know your feedback. Thanks.