Category Archives: coding

Using Javadoc for documentation

What is Javadoc? Most of the times people confuse it with the actual HTML documentation for the Java code. This is somewhat true but not entirely. Javadoc, itself is not the documentation, it is a tool from SUN Microsystem that helps you generate the documents.

How does it work? Javadoc allows developers to add documentation for a code in the java file itself in some specially formatted comments. The tool will read these comments and create a HTML document file.

Why do we use Javadoc? Why can’t we just create documents on our own? Well That is possible. Javadoc is there to make your life simpler as a developer. It helps you keep your code and documentation information in the same file. Just imagine if you are keeping the documentation separately, everytime you make a change in code, you ill need to modify the documentation also. What if someone misses it? If it is in the same file it is easier to maintain and hard to miss.  Most importantly, you are not writing the whole documentation, but just adding some quick comments which will be interpreted by the Javadoc tool. Lot more easier and faster than actually writing the documentation.

How to implement it? Simple, just add some specially formatted comments in your code

Class Level comments

@author : Author of the class
@version : automatically provide accurate version and date updates.
@since :  Describes when this functionality has first existed.

Method Level

@param : method or constructor argument names and description
@return :  What does your method returns
@throws : Does this method throw an exception
@deprecated : 	Describes an outdated method.

General Commets

@see : Adds 'See also' entry
@link : Adds an inline link with a label for users of your API documentation

The final code will look something like

import java.util.ArrayList;

/**
 * This is a Java Class to find anagrams. Any class level description goes here
 *
 * @author kamal
 * @version 1.0
 * @since 21-Sep-2011
 */
public class test{

/**
 * This is the main method method
 *
 * use {@link #findAnagrams(String)}
 * @param str
 * 		Any param description goes here
 */
public static void main(String str[])
{
	try
	{
		 String finalString="TestString";
		 test t =new test();
		 t.findAnagrams(finalString);
	}
	catch(Exception e) {
	   e.printStackTrace();
	}
}

/**
 * This is another method and we will add the description here
 *
 * @param input
 * 		Any param description goes here
 * @return
 * @throws NullPointerException
 */
private ArrayList findAnagrams(String input) throws NullPointerException
{
	ArrayList retList=new ArrayList();
	if(input.equals("")) throw new NullPointerException();
	printAnagrams(retList, "",input);
	return retList;
}

/**
 * Yet another method description goes here
 *
 * @param retList
 * @param prefix
 * @param word
 */
public void printAnagrams( ArrayList retList, String prefix, String word) {

if(word.length() <= 1) {
	retList.add(prefix + word);
} else {
for(int i = 0; i < word.length(); i++) {
String cur = word.substring(i, i + 1);
String before = word.substring(0, i); // letters before cur
String after = word.substring(i + 1); // letters after cur
printAnagrams(retList,prefix + cur, before + after);
}
}
}
}

and your javadoc comments will look like

image link

testdoc

Rod Cutting problem

Input: A rod on X inches. Price list of Rod prices on n inches.

Problem: Cut a rod of X inches into pieces so that it can be sold at a maximum price.

Example

Input- 8 inch rod
Price list : 1 inch piece=1 Rs, 2=5, 3=8, 4=9, 5=10, 6=17, 7=17 and so on

Output= maximum price=22 (6+2 inch)


/**
* Problem definition: we need to calculate max revenue that can be generated by cutting
* a rod of given size (in inches)
* @author kamal
*
*/
public class CutRod {

//we will be given price based on an inch, 0 inch=0Rs, 1=1, 2=5 and so on
//append zeros where price is not known, so here we can sell max rod of 7 inches
private int prices[]={0,1,5,8,9, 10,17,17,0,0,0,0,0,0,0,0,0};//append n

//using dynamic programming, we will store any previously calculated max prices
private int revenue[]=new int[20];

/**
* Main Method
* @param s
*/
public static void main(String s[])
{
CutRod cr=new CutRod();
System.out.println(cr.fetchMaxPrice(8));
}


/**
* Recursively calls itself to fetch max price
* @param size
* @return
*/
private int fetchMaxPrice(int size)
{
int price=0;
if(size==0)
return 0;
if(revenue[size]>0)
return(revenue[size]);
//brute force
for(int i=1;i<=size;i++)

{

//ith cut price


price=getMax(price, prices[i]+this.fetchMaxPrice(size-i));

revenue[size]=price;

}

return price;

}


/**
* Returns maximum of 2 integers
* @param a
* @param b
* @return
*/

private int getMax(int a, int b)
{

if (a>=b)
return a;
else
return b;
}
}

Maximum Subarray Problem

Problem Definition- Find out a sub-array from n array of numbers where the sum is highest.

Solution  type: Brute force, find out all the combination of arrays and pick the one with maximum sum

Order of complexity: N^2

Code:
public class maxsubarray {

public static void main(String s[])
{
int arr[]={-1,2,4,60,1,-3,2,-6,7,-9,1};

int maxsum=0;
int maxlow=0;
int maxhigh=0;
int low=0;
int high=0;
int sum=0;
int newsum=0;
for(int i=0;i<arr.length-1;i++)
{
sum=0;
newsum=0;
sum=arr[i]+arr[i+1];
newsum=sum;
low=i;
high=i+1;
for(int j=i+2;j<arr.length;j++)
{
newsum=newsum+arr[j];
if(sum<newsum)
{
sum=newsum;
high=j;

}
}
if(sum>maxsum)
{
maxsum=sum;
maxhigh=high;
maxlow=low;
}
}
System.out.println(“lower bound:”+maxlow);
System.out.println(“higher bound:”+maxhigh);
System.out.println(“maximum sum:”+maxsum);
}
}

Tortoise and Hare algorithm

In last post I discussed an algorithm to find out intersection point in 2 lists. A related problem to that is to figure out if a list has cycles. Say there are 10 nodes in list and 10th node is pointing back to 4th node. How ill we figure out if a list has such a cycle.

There can be many solutions, like storing previously traversed nodes, or simply adding a flag to each node indicating of the node was already traversed or not. But these solutions need extra space of order n.

A classic solution to above problem is ‘Tortoise and Hare algorithm’ or ‘Floyd’s cycle-finding algorithm’. The idea is to have two pointers, one will traverse list node by node or move one node at a time (tortoise) and another pointer moving two nodes at a time (hare). If the list has a cycle, the two pointers are bound to meet at some node, otherwise they will never meet. Try to dry run it, you will know what it means.

How to get intersection point of 2 linked lists.

There are 2 lists A and B (we know the root nodes for both). We know that these 2 lists intersect at some point and after that it is common list (they merge into each other, or think of it as a Y list).

example: list A->1->2->3->4->5->6->end
List B->11->12->4->5->6->end

Both the list intersect at node 4. This is what we need to find.

Solution-
1. Find length of A
2. Find length of B
3. Find diff=length A-length B
4. Traverse larger list diff nodes (we know after this nodes will be equal for both lists).
5. Now traverse both list simultaneously and find out the common node (this is our required node).

More solutions here.

I like the solution 5 as well from solution lists. It is simply reversing the list A (6->5->4->-3->2->1).

So when we are traversing list 2 now we will get like 11->12->4->3->2->1->end (as the pointers are reversed). So we are actually calculating length(sum) of non-common part, And we already know length of 2 lists.

length A=A’+C(Common part)
length B=B’+C
and A’+B’=L (length of non-common part we found by traversing list B after reversing list A)

Three unknowns(A’, B’ and C) and three equations. Can’t get simpler than this.

Time complexity of an Algorithm- Basic

Whenever we write a piece of code or algorithm to solve a problem, we need to understand how much time will the algorithm take to solve the given problem. This is important information as we have to make a decision based on amount of input data, that if the given solution will be sufficient or needs further improvement. The time complexity is mostly expressed in big O notation, called as- order of.

In simple words, complexity of the code can be known by checking amount of times a particular piece of code gets executed and how that is dependent on input data.

1. Lowest level of time complexity (hence best), which can be achieved is constant time complexity or is Order of 1, O(1). This means the time taken by algorithm will always be constant irrespective of input data.

e.g. Find sum of N consecutive numbers.

No matter what the value of N is, we just need to find (N*(N+1)/2).

OR print a string str 100 times.

for (i=0 to 100){print str;};

In above cases the code will take a constant time independent of the input.

2. Second best complexity that can be achieved by a code is of order of log n or O(log n). If you are familiar with logarithms, you already know what I am talking about. If you are not comfortable with logs, read on. When we say log n, we are by default assuming base as 2 (if not specified otherwise).

So if I say

log (base 2) n=x, this can also be thought of: n=2^x.

For further simplicity, all we are trying to say here is, that with every iteration of the code, the previous step problem dataset gets reduced to half (½).

A classic example for this would be binary search. We have a sorted array and we are trying to find put a number.

Array arr={1,3,6,8,11,13,17, 22, 28}

search if x=3 is available or not

Algo-

1. take 2 variables start and end at start(1) and end(28) of array.
2. Find mid of the array (position 5, No 11).
3. Check if it is the desired number x
4. if No at mid position is >x, set end to mid, else set start to mid.
5. Repeat 2 to 4
Notice that every time we execute step 4, we are reducing our data set from previous step to half.

3. Complexity of order N, O(N)that is directly proportional to number of input data set. Note when we say O(N), actual complexity can be 1*N, 2*N, 100*N, k*N where k is any constants which does not change with N.

A very simple example here would be searching a number in a random array

Array arr={4, 3, 88, 15, 67, 13, 56}

find x= 15

we just need to loop through whole array once (in worst case), from 0 to N and check if the number is available at the position.

4. O(n log n).If you look carefully, we have just added above 2 complexities for log n and n. So we are talking about a code which has complexity of log n and gets executed n number of times.

A very simple example is of tree sorting, where we create a binary search tree for a given array. We know insertion in binary search tree taken log n time. Now instead of adding just one element, we are trying to add n elements (whole array), so we are talking about n* log n complexity.

5. O (n^2). If you have n elements as input, and you have to loop twice all these elements, we are using n*n steps. Example would be bubble or selection sorting

Array arr={4, 3, 88, 15, 67, 13, 56}

Task- sort the array

for ( i=0 to N-1)
for(j=i+1 to N-1)
{
if(arr[i] is greater than arr[j])
swap(arr[i],arr[j]);
}

Why Markup Interfaces?

I wonder why java provides markup interfaces? like serializeable or Cloneable, they just tell the compiler that a particular class object can be serialized or cloned. In other words they mark the class with some special property. But then why are these interfaces, why not just keywords? Thoughts?

Understanding Recursion

Did you ever get confused how the stack is maintained while recursion. Try executing this code and you will understand


public class test {

public static void main(String s[])
{
try{
recursive();
}
finally{
System.out.println("FINALLY");
}
}

public static void recursive()
{
try{
System.out.println("add call to stack");
recursive();
System.out.println("remove call from stack");
}
finally{
System.out.println("from finally call recursion again");
recursive();
System.out.println("call from finally is over");
}
}
}

Call by Reference in Java

Does Java pass object by value or by reference? Answer is a bit complex- it passes reference of object by value. Confused? Here is an example which will explain


public class test {

int a;

public static void alter(test obj)
{
//setting value of variable a.
obj.a=10;
//creating a temp object and assigning to main object
test temp=new test();
temp.a=15;
obj=temp;
}

public static void main(String s[])
{
try
{
test obj=new test();
obj.a=5;
//shows 5
System.out.println("Before call obj.a:"+obj.a);
alter(obj);
//shows 10 not 15
System.out.println("After call obj.a:"+obj.a);
}
catch(Exception e)
{
e.printStackTrace();
}
}
}

Stress Testing the application!

Yesterday I needed to quickly test one of web modules for performance. Easiest way was to do some stress testing, simulate real world environment (100 users hitting url at the same time) and then checking the service response time. It looked simple, I just needed a stress-testing tool, which could take url of my webpage and return me the performance data. But it turned out much more complex than that.

First shock came when I came to know that not many professionals are doing stress testing for their applications. I checked with some of my friends and got the same answer that they were not doing stress testing. How could I blame others when I did stress testing for one of my applications like 4 years ago.

Anyway, I knew that I would have to figure out things from scratch. I was told about Apache Benchmark (ab).  That looked promising to start with and I was able to get some performance data for static sites. But I was not able to look at the output, that ab was bringing back from the site. I tried to figure out how to check it for some time, but it turned out to be complex process, and I wanted to get over with the testing as soon as possible as other pending work was waiting.

So I though of using some UI based tool rather then command based (that’s the disadvantage of getting used to Windows). I googled around and found Jmeter, which looked very promising, and my kind of tool (open source). Again it started off well. And this time I was able to get back the output. The Jmeter could show the output in multiple formats, including HTML. This also helped to see that the output I was getting back from website was actually an error message instead of the correct page. The tool was showing the test case as success, because the error message was actually embedded in the correct HTML page (based on some conditions, it was to be shown or hidden). Now I figured out that this was because the tool was not able to set values in session for multiple test cases. Jmeter looked promising and I was sure that there must be some place where I could set the session settings (it had a lots of settings options for cache/ cookies etc). But too many setting options could only confuse. I again spent a couple of hours on this tool before giving up.

Time was running out, and I needed a tool that could help me testing my application without much complexity. So I thought of trying trial version (14 days or some limited features) of some paid software, when I figured out webserver stress tool’s. That worked like piece of cake. All the required settings were just 3-4 screens. Setting up sessions meant just checking the check-box for cookies. Clear output files with detailed logs, Summary log, and logs for each user simulated, url logs etc made it easier to compare different performance parameters. The paid version is also cheap (less than 250$) for this.

Anyone has better ideas for load/ stress/ performance testing of the application?