Zinda ho tum?

Dilon mein tum apni betabiyan leke chal rahe ho.
Toh zinda ho tum!
Nazar mein khwaabon ki bijliyan leke chal rahe ho
Toh zinda ho tum!

Hawa ke jhonkon ke jaise aazad rehna seekho
Tum ek dariya ke jaise, leharon mein behna seekho
Har ek lamhe se tum milo khole apni baahein
Har ek pal ek naya samaa dekhe ye nigahein

Jo apni aankhon mein hairaniyan leke chal rahe ho
Toh zinda ho tum!
Dilon mein tum apni betabiyan leke chal rahe ho
Toh zinda ho tum!

-Javed Akhtar

Insertion Sorting

Insertion sorting, as the name suggest, is about inserting the elements of an unsorted array to their correct position one by one. To make it clearer, lets say we have an unsorted array. We take another array, which is empty initially and then we will keep adding numbers one by one into this array at their correct positions.

Say the original array A is

5, 3, 7, 2, 6

Now we take first element and add to zeroth position of a new array B, so B is now containing 5

next we pick 3 from original array and add to first position of B, it becomes 3, 5

After step 3 B is, 3, 5, 7 and then 2, 3, 5, 7 and finally 2, 3, 5, 6, 7

We have taken 2 arrays just to make things clear, the sorting functionality can be achieved with 1 array only. Instead of taking an additional array, we will think of original array as 2 sub-parts, at any given time first N-x elements are sorted and remaining x are not sorted.

Again taking the original array A

5, 3, 7, 2, 6

Step 1: 5 (sorted till here), 3, 7, 2, 6
Step 2: 3, 5 (sorted till here), 7, 2, 6
Step 3: 3, 5, 7 (S), 2, 6
Step 4: 2, 3, 5, 7, (S) 6
Step 5: 2, 3, 5, 6, 7 – Final

Complexity:

If there are N elements in array, at Nth point, we know we have N-x sorted and x unsorted. We pick up next element (N-x+1)st, and need to insert it into proper position in for N-x+1 elements. So in worst case we need to make N-x comparisons (in best case 1 comparison). The process has to be repeated N times for N elements.

So in worst case we have comparisons like

1+2+3+.. +N= N*(N-1)/2 which is quadratic i.e. N*N.

In best case (sorted array) we have 1+1+1+.. N times comparison which is order of N (linear).

We generally take worst case complexity so we will say Insertion sort has complexity of N^2.

Abusing Foreign Keys

Recently I came across a database design which made me think that upto what extent one should be using Foreign keys. A colleague created a new table in an existing schema and used maximum number of foreign key constraints possible to make sure no junk data gets entered into this table. On one hand it is a good idea to use foreign key constraints to make sure your data is clean all the time, on the other hand it might introduce some unwanted conditions on your code.

Let me take an example. You have 2 tables employee and salary. Employee has a primary key employee_id which you use as foreign key in your salary table. Sounds smooth, if we have salary entry, we must have the employee, and if employee is moving out(record getting deleted), delete the salary entry. Lets say I have another table called print_history which stores who all has printed salary slips for an employee. Now this table has 2 employee Ids, one for the manager who printed the slip (say Manager_id) and second is the employee whose slip was printed (say emp_id). Now we know that logically these 2 Ids should be in employee table, but is it necessary to add the constraint. It will work fine while insertion of the records, but say there is a case when an employee record is getting deleted, should we enforce deletion of print_history record? should we stop employee record from being deleted if there is an print_history entry? (I know soft deletes might help, but still, why to add unnecessary constraints?

Deleting duplicate rows from a table

Recently faced an issue of having duplicate rows in a table of production database. Normally to delete or insert data into table, primary key is used, but due to bad database design somehow duplicate rows got added. Exact same data, each column was same.

A little bit googling solved the issue.

delete from temp_table where rowid not in (select min(rowid) from temp_table group by column1, column2);

Note that this might not straight away work for a table with huge data. A simple way to solve that issue is to create a temporary table, say temp_table2, copy data for duplicate rows from temp_table to temp_table2. Now clean up temp_table2 using above delete command and delete all the duplicate rows form temp_table. Insert back all the remaining, cleaned up, rows from temp_table2 to temp_table.

Antivirus Marketing strategy?

It has happened to me twice now. Days before my anti-virus subscription is about to finish, I start getting messages that some virus or worm has infected my system which was successfully cleaned up by the anti-virus. Just wondering if this is some marketing strategy by these anti-virus companies to tell us about the importance of their software or a sheer coincidence?

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

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).