My Own Private India

Joel Stein writes in an article for Time about how Edison, NJ has become home to one of the largest Indian communities. My only question to Mr. Joel

"You sure are aware that right now American troops are in Afghanistan, Iraq right? If you are so pissed off having Indians in Edison, NJ just imagine how Iraqis and Afghanis are right now feeling? "

Seriously TIME, don't you even think twice before publishing an article. I mean did you even read the article? Is that the journalistic levels you had to stoop to. I will have to say here that I am not a regular reader of TIME magazine. Occasionally when CNN links to TIME, I do read some articles or if any of my friends forward a link from TIME. From few articles I read in TIME magazine, it seems to suffer from Indophobia. For instance search for this article - An Indian Muslim in Crisis by Aryn Baker. (This article appeared in Time during Mumbai Terror attacks).  And I never heard of Mr. Joel Stein before this. So my views on Joel Stein are strictly related to this article alone. Well after reading this article I don't think I will be reading Joel's articles anymore.

Update: I was reading other blogs like Sepia Mutiny(mostly written like a rant rather than response ) and few other comments. Do read them. 8asians.com asks a very good question : What if in the article, Indians were replaced by Latinos and what if the Joel Stein had written "Now we know why Mexico is so damn poor".

Another interesting thing I found out was "White Flight". Do read about it in wikipedia.

Read the opinion piece in The Hindu http://www.thehindu.com/opinion/lead/article495461.ece?homepage=true

Dear Friend Hitler

There has been surge of reports in news papers, blogs all around the world about India's new found fascination for Hitler. Some unknown director(well atleast I have never heard of him), is planning to make a movie on Hitler's last days in bunker. The title of the movie is taken from Gandhi's letter to Hitler. The movie also deals with Hitler's alleged love interest Eva Braun and their marriage.

Any movie maker who tries glorify Hitler has to be in some mental asylum. I won't jump to conclusion here and say the director would have glorified Hitler since I did not see the script nor the movie has been made. So even before the movie has been made, what I did not understand was why New York Times, Gaurdian, Gawker have reported that there is renewed interest for Hitler in India. It is true that some fringe right wing parties in India have sometimes idolized Hitler but come on every country has sociopaths. Just because there is KKK in US you cannot say that US has renewed interest on white supremacy.

India is one of the countries where Jews were not persecuted and even though India was fighting for the freedom from British, India fought the world war 2 against the Germans. Indian freedom fighters and policy makers realized that German imperialism is much more dangerous than that of the British imperialism.

PS: Anupam Kher, veteran bollywood actor who was supposed to play Hitler in the movie withdrew from the role after the controversy.

PS: I was planning to write this blog long time back, but I was busy preparing for interviews. So I think I am a week late to respond to the controversy.

update: today I read an opinion piece in Wall Street Journal by Sadanand Dhume explaining India's fetish for Hitler. Read it here http://bit.ly/aBE3HC

Maximum Value Contiguous Subsequence

I was asked this question in first round of onsite interview.

geeksforgeeks.org seems to have almost all of the interview questions I faced. they also write the code in C and show all possible ways of doing the problem. If only I had time to go through their collection of 1000+ interview questions collections before my interviews...

Since this question is also present in http://geeksforgeeks.org/?p=576 I would just give the link to their page. Below is the code which I wrote during interview.

int maxSumSubSequence( int a[] )
    {
        int maxSum = a[0];
        int currentSum = 0;
        int alen = sizeof(a)/sizeof(a[0]);
        for( int i = 0; i < alen; i++ )
        {
            currentSum += a[ i ];

            if( currentSum > maxSum )
            {
                maxSum = currentSum ;
            }
            if( currentSum < 0 )
            {
                currentSum = 0;
            }
        }

        return maxSum;
    }

Test cases: All 0's, all positives, all negatives, mixture of positive and negatives. Major case where this will fail is if the array contains all MaxInts.

time complexity : linear

Find the Diameter of a binary tree?

What is the diameter of a binary tree?? I was asked this question in second round of onsite interview. The interviewer first asked me to flip the adjacent nodes of a linked list. He asked if I know the question and since the question seemed easy and doable, I said I know the algorithm and can be done. So he changed the question and asked me to find the diameter of binary tree. I did not know what is the diameter of binary tree. So he helped me to come up with the algorithm and I coded it. Diameter of binary tree is the length of the longest path present in a binary tree.

int max(int a, int b)
{
  return (a >= b)? a: b;
}

int maxDepth(struct bTreeNode *root)
{
    if(root == NULL)
    {
        return 0;
    }
    else
    {
        int ld = maxDepth(root->lNode);
        int rd = maxDepth(root->rNode);
        if( ld > rd)
            return ld+1;
        else
            return rd+1;
    }
}

int diameter(struct bTreeNode *root)
{
    if(root == NULL)
    {
        return 0;
    }
    else
    {
        int ld = diameter(root->lNode);
        int rd = diameter(root->rNode);
        int lh = maxDepth(root->lNode);
        int rh = maxDepth(root->rNode);
        return max(lh + rh + 1, max(ld, rd));
    }
}

Source : http://geeksforgeeks.org/?p=5687

Its also important to come up with test cases, to show that your code is working. For this problem there are three cases that needs to be tested. You need to give inputs such a way that you get all 3 possible answers for the respective input i.e. lh+rh+1 or ld or rd. .

ps: I am posting only rough code and I am in no way responsible if the code is wrong. I am also giving other links which have posted proper code and I felt there is no point in writing the same code here. Please refer to those sites.  

Prepare for interviews along with me. Find if two linked lists are merging.

I will be posting some interesting interview questions I was asked. Hopefully it may be of some help to you all.

1) Find if the two linked lists merge at any point? Find the node where they are intersecting?
Ans) There are many ways to do this problem. GeeksforGeeks.com has listed few solutions. I am giving the most efficient and easiest way here. For other kind of solutions you can do google search.

First we can check if two linked lists merge by checking if the last node of both the linked lists is same.

Second to find the node where they are merging, find the lengths of both linked lists. let it be L1 and L2.
The difference will be L1-L2 (assuming L1>L2. can take absolute value as well).
The node where they are merging is the (L1-L2)th node on smaller linked list.

You need to advance the pointer on longer linked list by (L1-L2) number of nodes. Then traverse on both the linked lists simultaneously. The place where the pointers meet is the merge point.
Time complexity O(m+n) where m and n is the length of two linked lists.

Few sources for code: http://geeksforgeeks.org/?p=2405
http://blogs.msdn.com/b/abhinaba/archive/2007/08/16/interesting-linked-list-problem.aspx
http://stackoverflow.com/questions/1826501/best-possible-algorithm-to-check-if-two-linked-lists-are-merging-at-any-point-if
http://stackoverflow.com/questions/1594061/linked-list-interview-question