Category Archives: coding

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?

Difference between visibility hidden vs display none

I spent almost an entire day on this, so wanted to share the information in case it might be helpful for others. We at times need to remove a DOM object (textbox/ label/ dropdown etc) from the UI. For which we use two things object.style.visibility=”hidden” and object.style.display=”none”. Though both of them can remove the object from UI, yet there is a significant difference between these two approaches. Whereas visibility hidden will “hide” the object, it will still leave the object on the UI (in hidden format). On the other hand display=”none” will completely remove the object from UI.

The differentiation is more important in a case, where the css being used here does not specify the x and y coordinates for DOM objects, it instead places one object after another. So the trick here is, if I make an object invisible by hiding it (visibility=”hidden”), it will still occupy that one space in the flow, and a blank cell will appear on the screen. Whereas if display is none, then the next object will take place of this object and hence no empty spaces are shown on the screen.

So both the approaches can be used as per ones requirement

Redundancy Vs. Reuse

We faced a typical software engineer problem recently, that should we have multiple copies of similar code? Obvious answer is “NO”

But Lets say, you are dealing with multi hundred thousand lines of code. There is a pressure of deadline. You know that there are already some module which is providing the similar solution as you want, and just adding one if else, and making some tweaking in that code will save you from writing hundreds of lines of code. Isn’t it tempting to do that.

Ideally, we would like to get that code which is common in both cases to some common util area, where both modules can use it. Moreover, future coders will get help if they face the similar situation. But again, that is ideal solution. Here we are talking about deadlines. We don’t have time to do this activity creation of this common util stuff is a task in itself.

Second best, which I would recommend, is to copy the code to your module and use. Concern- we have two copies of same code. hundreds of lines of code which is duplicated. I would argue, better duplicate then undauntedly dependent. Why to make two mutually exclusive units dependent. What if I want to delete one module completely tomorrow, how and “why” to think that some file somewhere might be used by some other module.

What say?