Monthly Archives: December 2010

Java Inheritance- Method and Variable overriding

A very simple example to understand overriding concept in java

Parent Class-

public class parent {

int pval=10;
parent()
{
System.out.println(“creating parent”);
}

public void area()
{
System.out.print(“area of parent:”);
System.out.println(pval);
}
}

Child class-

public class child extends parent{
int cval=5;
int pval=15;
child()
{
System.out.println(“creating child”);
}

child(String str)
{
System.out.println(“hello:”+str);
}

public void area()
{
System.out.print(“area of child:”);
System.out.println(cval);
}

public static void main(String s[])
{
child c=new child();
c.area();
System.out.println(“c.pval:”+c.pval);
System.out.println(“—————————-“);
child c1=new child(“kamal”);
System.out.println(“—————————-“);
parent p=new parent();
p.area();
System.out.println(“p.pval:”+p.pval);
System.out.println(“—————————-“);
parent pc=new child();
pc.area();
System.out.println(“pc.pval:”+pc.pval);
System.out.println(“—————————–“);
}

}

output

creating parent
creating child
area of child:5
c.pval:15
—————————-
creating parent
hello:kamal
—————————-
creating parent
area of parent:10
p.pval:10
—————————-
creating parent
creating child
area of child:5
pc.pval:10
—————————–

Look closely at the last set of output, that is interesting. You can see when we refer to child object with parent class reference, the method being called is from child class as method was overridden, but the pval member variable was not overridden.

Now as member variables are not overridden, compiler uses static binding as it already know which variable is being referred to, whereas in case of parent class object calling a method which is overridden, compiler will not know beforehand which method should be called, so it will leave that decision to runtime, hence dynamic binding.

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?

Spreading the Wisdom

A couple of days back I had to provide estimate for a requirement from Clients. I thought of checking some estimation techniques on internet to cross verify. I searched for term ‘estimation techniques’ and started browsing. The first link was some article (very informative) and then I clicked on second link and to my surprise, I found a powerpoint which I created 3-4 years ago to give a session to my team. I uploaded the ppt on slideshare and since then it had more than 19000 hits. I am so happy that people are still using what I created long time back 🙂

Software Estimation Techniques

View more presentations from kamal.

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");
}
}
}