Mumbai terror attack

I have been itching from past few days to write a blog entry, but was busy with assignments and project. Here is quick update from my side:

I will finish my application process tomorrow for PhD program at Rice University. Florida has won SEC championship game, and hopefully will win National championship also. My best wishes are with coach Urban Meyer and his team. I followed Florida games throughout this season and am really impressed by Tim Tebow’s dedication. For those who don’t know, Tim Tebow is University of Florida quarterback, Heisman Trophy winner with a GPA of 3.7!!! And yes, he visited Philippines for missionary work in his spring break rather than going to Daytona or Miami beach.

I intend to address issues that came to my mind after November 2008 Mumbai attack. Interesting thing is I have to write date along the topic name, suggests “There have been more”. There have been 5 bombing incidents within a period of 8 months (Dec 6 2008, Jan 27 2003, July 28 2003, August 25 2003). Then there is July 11 2006 Mumbai train bombing. In fact, I was outside the Malad station, returning from Java class when these bombing incidents occurred. I had to walk from Malad to my place, since trains and bus services were stopped to prevent further attacks. Here is listing of all the terrorist attacks that took place in India: http://en.wikipedia.org/wiki/Chronology_of_terrorist_incidents_in_India

My heart fills with pain when I read and hear about this. As human being, I have extreme desire to end these kinds of attacks and bring peace in the world, and as a science student, I see it as a problem that it yet to be solved. I will try to address these emotions separately and hopefully, at end of this blog entry, I am able to put down thoughts that have been revolving in my mind (this is literal translation of an Hindi expression J ).

First, let me offer my prayers and condolences for those who have lost their lives. There was a candle light event at University of Florida campus. I was overwhelmed to see people from various countries (including Pakistan) share the same sentiments.

Now let’s address the issues rationally and methodically:

1. Is India prepared to handle terrorist attacks?

I believe Indian defense forces (which include Police) are capable to counter any kind of attack. But I must say we are not ready to predict such attacks. India does not have a centralized counter-terrorist plan (which should include local law enforcement agencies to RAW, navy and army). Efforts should be made to formulate such plan. It will require considerable investment in developing this infrastructure.

2. “Blame game” (as Mr Musharraf puts it) post-attack

I believe that both countries India and Pakistan cannot afford a war. Even if they could, they shouldn’t go for it. There is significant portion of people on both sides which hate other country and believe in war propaganda. These people were either victims of partition or war or probably are “brainwashed”. I use this term to generalize any kind of thought processes which is built up based on environment and which relies totally on emotions rather than logical and rational thinking. Both Pakistan and India have to make sure that such people are not the elected representative of people or into law enforcement.

I am sure that Pakistani government did not authorize this attack, but it is also confirmed that this attack was masterminded in Pakistan and Pakistani nationals were involved in this attack (See: http://broadband.indiatimes.com/toishowvideo/3800626.cms). Also, I disagree with the fact that it is just India’s internal problem. If there is a citizen of your country, who promotes terrorist activities, it is responsibility of the government to act against such person (even if he is from your intelligence services). I think Pakistan government should investigate into this and ban any terror camps.

Again, I want to summarize by saying, I do not believe in war, but I think Pakistan should make considerable efforts to eliminate terrorist camps in their region. Also, I think peace talks with Pakistan should be continued and efforts should be made by Indian government to coordinate with Pakistan government to take action against people involved in this attack.

3. Islam and terrorism

I respect Islam and think it has something wonderful to offer to world, eg: “Zakat” (alms-giving). But, I feel sad for people who misinterpret Quran and believe in killing other people in name of Jihad (See http://www.youtube.com/watch?v=Bxk5AAA5FbI). I am sure God will not absolve them of such sins. I have many Muslim friends who are very nice people. It is unfortunate that they are categorized because of these terrorist. I would like to point out the fact that Indian Muslims condemned this terrorist attack and even refused to bury the terrorists in Mumbai. Hanif Nalkhande, a spokesman for the Muslim Jama Masjid Trust, said: "People who committed this heinous crime cannot be called Muslim. Islam does not permit this sort of barbaric crime." (See http://www.timesonline.co.uk/tol/news/world/asia/article5267860.ece)

I believe any religion (including Hinduism) should not tolerate harming other people in its name. I am against anyone who is involved in Mumbai and Gujarat riots.

4. Responsibility of media

I think media should not abuse the freedom of speech and should be discreet in case of such emergency. I hate to point out that terrorist were watching the television which displayed all the movements of India defense forces, which may have delayed the operation and cause further casualties. (See http://news.bbc.co.uk/2/hi/south_asia/7760754.stm).

5. Assessment of manpower and equipments of Indian police is necessary (See http://news.bbc.co.uk/2/hi/south_asia/7760460.stm). I understand it is not a step function, but steps should be taken to ensure gradual progress of Indian forces.

These are my personal opinion, and do not intend to harm anyone or any sect. I also do not intend to finger point at any country. If you feel I have hurt your feelings or am being unfair or incorrect, please write back to me and I will modify or probably delete this blog.

I would like to conclude with two sayings:

“Eye for an eye would make the whole world blind” – Mahatma Gandhi.

“All that is necessary for the triumph of evil is that good men do nothing” – Edmund Burke.

Microsoft Internship

My interview experience with Microsoft:

1. Questions asked
2. Pictures

Here are some more pictures:

1. Intern Event
2. Soccer Match, DSP Event, My office (building 34)

I also visited couple of other places during internship:

1. Canada
2. Oregon

Overall the experience was awesome. I got an offer at end of internship, but had to refuse it to pursue PhD. My team lead was Bogdan Crivat and my manager was Raman Iyer. Both of them are amazing guys and it was a great learning experience. I contributed a "little" in development of Table Analysis Tool for Cloud. In all, I think it is amazing product. If you haven't tried it, I encourage you to do so (atleast the online version).

GatorMemo version 3.0 is ready !!!

After I decided to do PhD, I always wanted to improve my study process (especially my notes management system). After several discussions with my internship manager Raman Iyer, my friends Raja Nadar and Kishore Malani, I decided to go ahead with GatorMemo. It is build on principles of SuperMemo (spaced learning) and Mindmaps.

It started out as Windows Form application which resulted in version 2.0. I feel the user interface is too complicated for normal user, so decided to build it again from scratch using WPF instead of WinForms. Functionally, there is no difference between these two versions (except WPF doesnt have facility to play audio/video files. I might add them as soon as I get time to work on it).

Suggestions:
1. Read a book, research paper, or go through lectures/podcast/videos, etc ...
2. Then, create a mindmap after completing understanding the topic. I usually refer to 3 or more books and then organize my thoughts into mindmap. I strongly suggest to put huge amount of efforts to create a good mindmap.
3. Now, create card for each node. Front side of card can be a question about the node or simply node name and Back side can be the answer or description about the topic that the node represents.
4. I recommend adding mnemonics and bibliography to mindmap and cards. Mnemonic will help you recollect the subject matter and Bibliography will be extremely useful if you are planning to write a research paper.
5. Periodically, revise the card by using the Autolearn under Action tab (This software uses SuperMemo algorithm developed by Piotr Woznaik).
6. I also suggest using Lateral Thinking especially if you are planning to write a research papers.

Here is link to setup version 3.0: (I encourage you to to use this version)
http://niketan2.googlepages.com/GatorMemoSetup.msi

You can import following file (see Action tab):
http://niketan2.googlepages.com/OSMindMap.zip to see how s/w works :)

It is still in Beta phase, so expect bugs / exceptions :) ... (Infact I am so busy with my studies/assignments, that I did not time to any kind of corner case testing). Please mail me if you find bugs and help me improve the software.

If you are interested in improving the software, go ahead and download the code and modify it.

My new wiki

http://niketanpansare.wikidot.com/

Invictus by William Ernest Henley

Out of the night that covers me,
Black as the Pit from pole to pole,
I thank whatever gods may be
For my unconquerable soul.

In the fell clutch of Circumstance
I have not winced nor cried aloud.
Under the bludgeonings of Chance
My head is bloody, but unbowed.

Beyond this place of wrath and tears
Looms but the Horror of the shade,
And yet the menace of the years
Finds, and shall find me, unafraid.

It matters not how strait the gate,
How charged with punishments the scroll,
I am the master of my fate:
I am the captain of my soul.

Random Quotes

If

If you can keep your head when all about you
Are losing theirs and blaming it on you;
If you can trust yourself when all men doubt you,
But make allowance for their doubting too;
If you can wait and not be tired by waiting,
Or, being lied about, don't deal in lies,
Or, being hated, don't give way to hating,
And yet don't look too good, nor talk too wise;

If you can dream - and not make dreams your master;
If you can think - and not make thoughts your aim;
If you can meet with triumph and disaster
And treat those two imposters just the same;
If you can bear to hear the truth you've spoken
Twisted by knaves to make a trap for fools,
Or watch the things you gave your life to broken,
And stoop and build 'em up with wornout tools;

If you can make one heap of all your winnings
And risk it on one turn of pitch-and-toss,
And lose, and start again at your beginnings
And never breath a word about your loss;
If you can force your heart and nerve and sinew
To serve your turn long after they are gone,
And so hold on when there is nothing in you
Except the Will which says to them: "Hold on";

If you can talk with crowds and keep your virtue,
Or walk with kings - nor lose the common touch;
If neither foes nor loving friends can hurt you;
If all men count with you, but none too much;
If you can fill the unforgiving minute
With sixty seconds' worth of distance run -
Yours is the Earth and everything that's in it,
And - which is more - you'll be a Man my son
- Rudyard Kipling


Nothing in the world can take the place of persistence.
Talent will not; nothing is more common than unsuccessful men with talent.
Genius will not; unrewarded genius is almost a proverb.
8Education will not; the world is full of educated derelicts.
Persistence and determination alone are omnipotent.
The slogan "Press On!" has solved and always will solve the problems of the human race
- Calvin Coolidge


When I do good, I feel good. When I do bad, I feel bad. That's my religion.
- Abraham Lincoln


All that I have seen teaches me to trust the Creator for all I have not seen.
- Ralph Waldo Emerson


Our deepest fear is not that we are inadequate. Our deepest fear is that we are powerful beyond measure.
- Marianne Williamson

Developers are born brave :)

P versus NP

Never heard about it ?

Its an unsolved problem in computer Science. Infact, if you could find a solution to it, you will get a million dollars. Well, I am not kidding (http://www.claymath.org/millennium/).
Now aren't you curious ?

Here is the official problem description: http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf

I will try to explain it to you in more simpler way. It is extremely titillating problem because it is very simple to understand it and first time when you hear it, it seems that you can crack it witihin a day or two.

I will assume few things:You know what an algorithm is and what is worst, average and best case complexities (asymtotic notations) are. You may want to refer to Chapter 1,2 and 3 in Introduction to Algorithm by Cormen

Section 1: Lower bound
Say you are given a problem and you find an algorithm that solves that problem in O(n^2) time. What is the lower bound of your algorithm (or should I say the problem -- Hmmm, I will use algorithm and the problem interchangeably) ?
If your answer is O(n^2), you may want to read this section further, else you can skip this and go to the next section.

Lower bound is not about a particular algorithm, but about all possible algorithms for solving that problem.

I know 2 ways to find lower bound of the algorithms:

1. Decision tree based approach:
Eg: Lower bound of Comparison based Sorting (See this: http://www.ics.uci.edu/~eppstein/161/960116.html)

In short, comparison sort can be mapped to a decision tree (binary tree with yes and no). Longest path in binary tree with k leaves = log k.Since we know a number can be arranged in n! ways => n! leaves of decision trees.There, number of comparisions = log(n!) = n log(n) - O(n) .... using Stirling's formula.

2. Reduction:
Reduce an algorithm whose lower bound you already know to your algorithm (Thats right ... not the other way round).
Eg. Say you somehow prove that Sorting <= (O(n)) Ur algorithm, ie. Sorting is reducible to your algorithm in polynomial timeThen you can state that lower bound of your algorithm is nlogn.This in essense means that your algorithm is atleast as difficult as sorting. So, how to prove this ? Prove that by some crazy way, "Sorting can be done by your algorithm"

Section 2: Definitions
Decision problems: Problem with output either "YES" or "NO", depending on values of some input parameters

P: Class of decision problems that are "solvable" in polynomial time.

NP: Class of the decision problem that can be "verified" in polynomial time.
Eg: Sorting is NP since given a list, we can verify that it is sorted or not in polynomial time.Also, Sorting is P since it is solvable in polynomial time (O(nlogn)).
Infact, Every P problem is NP (ie to verify a P problem, we can simply solve it in polynomial time and compare the input with the output). i.e P belongsto NPWhether there exists any NP problem that is not P is yet unproven.
Trivial Solution - Every NP problem can be solved in 2^n, ie simply enumerating all cases.

NP-hard: For all problems L in NP, if L is reducible to L1 in polynomial time, then L1 is NP-hard.
NP-Complete: A problem is NP-Complete iff it is both NP and NP-hard.

See this Venn diagram for big picture.

co-NP: If complement of your problem is in NP, then your problem is in co-NP.
Eg: NP - Given a graph, is there a path of length less than k from some source node s to destination node t.co-NP - Given a graph, are all path of length greater than k
Again, whether NP = co-NP is unknown ?

Oracle: Consider Oracle to be GOD who knows everything and whom you can trust (So, computer scientist believe in GOD ... may be not in way as religion, but maybe yes to some extent)

We "pray" to GOD to give guidance. Similarly, we ask Oracle to help us with the problem.

GOD give us omens. Oracle gives us a certificate (an input sequence that will probably reveal the "TRUTH"). So you try to verify the certificate by your polynomial time verification algorithm (assuming it is NP).

Now here is a trick:

If the answer to that certificate is "YES" ... cool ... you have solved the problem !!!

If the answer is "NO" .... you ask for a new certificate from the Oracle.

(You could argue that since we trust Oracle, we should output "NO". But, we don't do that because Oracle gives a random certificate for undecidable problems. This makes it indeterministic, hence NP => nondeterministic polynomial).

Section 3: The real stuff
The biggest breakthrough in this area: Stephen Cook proved that Boolean Satisfiability problem (SAT) is NP-Complete.

So, if you could prove one of this things, you probably don't have to work any more for your thesis or field's medal:
1. SAT has polynomial time algorithm
2. Give non-polynomial time lower bound argument for SAT

If you prove 1 => you have proven P = NP
If you prove 2 => you have proven P != NP

OK. Let me makes things a little easy for you. Instead of SAT, you can do above things on any one of these problems

And yippee .... you will be more popular than Donald Knuth in Computer Science field.

I would encourage you to read "Computers and Intractability: A Guide to the Theory of NP-Completeness" or atleast a chapter in "Introduction to Algorithms - by Cormen, Rivest" to see how reduction actually works. Some of them are really cool and mind boggling techniques.

Random C++ tricks - GDB, Valgrind and Makefile

1. Perfect programming is hard - even the best programmers make mistakes.
2. A line of code that you haven't tested is a line of code with a bug.

Cardinal rule for debugging: If you are using gcc or g++, compile your program with -g option.
(Btw, to link a library with gcc, you use -l option. Eg: to link math library, use:
gcc filename -o outputfile -lm)

Segmentation Faults:

Any access outside that area (memory area assigned to the program) will cause a segmentation fault.

Common mistakes of segmentation faults:
1. Deferencing
a. NULL
b. an uninitialized pointer
c. a pointer that has been freed (or deleted, in C++) or that has gone out of scope (in the case of arrays declared in functions)
2. writing off the end of an array
3. Calling a recursive function that uses all of the stack space (On some systems, this will cause a "stack overflow" report)

Attacking segfaults:

1.a Deferencing NULL

$gdb myPgm core
The core file contains all the information needed by GDB to reconstruct the state of execution when the invalid operation caused a segmentation fault.

It will o/p:

Some copyright info
Core was generated by `myPgm'.
Program terminated with signal 11, Segmentation fault.
Some information about loading symbols
#0 0x0804838c in foo() () at myPgm.cpp:4
4 *x = 3;

This tells us that the execution stopped inside the function called foo() on line 4, which happened to be the assignment of the number 3 to the location pointed to by x.

(gdb) list
1 void foo()
2 {
3 char *x = 0;
4 *x = 3;
5 }
6
7 int main()
8 {
9 foo();
10 return 0;
(gdb) print x
$1 = 0x0

A little complicated eg: execution crashing inside a system call or library function (perhaps because we passed an uninitialized pointer)

#0 0x40194f93 in strcat () from /lib/tls/libc.so.6
(gdb) bt
#0 0x40194f93 in strcat () from /lib/tls/libc.so.6
#1 0x080483c9 in foo() () at t.cpp:6
#2 0x080483e3 in main () at t.cpp:11

so now we are in strcat stack but we want to see variable that was passed to strcat:

(gdb) up
#1 0x080483c9 in foo() () at t.cpp:6
6 strcat(x, "end");
(gdb) print x
$1 = 0x0

A common mistake is to not check the return from malloc to make sure that the system isn't out of memory. Another common mistake is to assume that a function that calls malloc doesn't return NULL even though it returns the result of malloc. Note that in C++, when you call new, it will throw an exception, bad_alloc, if sufficient memory cannot be allocated. Your code should be prepared to handle this situation cleanly, and if you choose to catch the exception and return NULL inside a function that ordinarily returns a new'ed pointer, this advice still holds.

1.b Deferencing an uninitialized pointer
Figuring out whether or not a pointer has been initialized is a bit harder than figuring out whether a pointer is NULL. The best way to avoid using an uninitialized pointer is to set your pointers to NULL when you declare them (or immediately initialize them).

You might need to figure out if 0x4025e800 is valid memory. One way you can get a sense of this in GDB is by printing out the addresses stored in other pointers you've allocated. If they're fairly close together, you've probably correctly allocated memory. Of course, there's no guarantee that this rule of thumb will hold on all systems.

In some cases, your debugger can tell you that an address is invalid based on the value stored in the pointer.

(gdb) print x
$1 = 0x1e <out of bounds>
(gdb) print *x
Cannot access memory at address 0x1e

1.c Dereferencing Freed Memory
This is another tricky bug to find because you're working with memory addresses that look valid. The best way to handle such a situation is again preventative: set your pointer to point to NULL as soon as you've freed it.

Another form of this bug is the problem of dealing with memory that has gone out of scope.

char *return_buffer()
{
char x[10];
strncpy(x, "a string", sizeof(x));
return x;
}

This is a really tricky bug to find because once again the memory address will look valid when you print it out in GDB.

If that pointer is causing you trouble, check the function and look for whether the pointer is pointing to a local variable in the function. Note that it is perfectly fine to return a pointer to memory allocated in the function using new or malloc, but not to return a pointer to a statically declared array (e.g., char x[10]).

2. writing off the end of an array
Valgrind will help you catch this bug on dynamically allocated arrays. See point 2 below.

Trick:
If notice that some of your variable values are changing periodically and unexpectedly. This is a tough bug to crack; one option is to set up your debugger to watch a variable for changes and run your program until the variable's value changes. Your debugger will break on that instruction, and you can poke around to figure out if that behavior is unexpected.

(gdb) watch [variable name]
Hardware watchpoint 1: [variable name]
(gdb) continue
...
Hardware watchpoint 1: [variable name]

Old value = [value1]
New value = [value2]

This approach can get tricky when you're dealing with a lot of dynamically allocated memory and it's not entirely clear what you should watch.

3. Stack overflow:
To diagnose a stack overflow in GDB, typically you just need to do a backtrace. If you find a single function call piling up an awfully large number of times, this is a good indication of a stack overflow.

(gdb) backtrace
#0 foo() () at t.cpp:5
#1 0x08048404 in foo() () at t.cpp:5
#2 0x08048404 in foo() () at t.cpp:5
#3 0x08048404 in foo() () at t.cpp:5
[...]
#20 0x08048404 in foo() () at t.cpp:5
#21 0x08048404 in foo() () at t.cpp:5
#22 0x08048404 in foo() () at t.cpp:5
---Type to continue, or q to quit---

Typically, you need to analyze your recursive function to make sure that all the base cases (the cases in which the function should not call itself) are covered correctly.

Other cool tricks with gdb:
We discussed bt, p (print), list, up

To set a breakpoint, type break <line number>
<line number> can be <sourcefile>:<line number>

Use n (or next) to progress through the loop one line at a time, r to run the program and c to continue.

There is also another set of commands, although they are not very commonly used; these commands actually modify the program as it is running. The call command, for example, will call a particular function; the set variable command will set a variable in the program to a particular value, for example, set variable i = 0. Return will make the current function return to the caller.

Using valgrind:

1. Finding memory leaks:
Compile your program with -g option.

$valgrind --tool=memcheck program_name

If number of allocs and the number of frees will differ in o/p, the try

$valgrind --tool=memcheck --leak-check=yes --show-reachable=yes program_name

O/p is somewhat like:

==pid== 100 bytes in 1 blocks are definitely lost in loss record 1 of 1
==pid== at 0x1B900DD0: malloc (vg_replace_malloc.c:131)
==pid== by 0x804840F: main (myPgm.c:5)

This means that there is a memory leak at line 5 in myPgm.c

2. Finding invalid pointers:
Warning of form:
'Invalid read of size X'or 'Invalid write of size X'
where X is the amount of memory we try to read.

Eg: if you allocate an array with malloc or new and then try to access a location past the end of the array:

int main()
{
char *x = malloc(10);
x[10] = 'a';
return 0;
}

$valgrind --tool=memcheck --leak-check=yes --show-reachable=yes program_name

This will give o/p:

==pid== Invalid write of size 1
==pid== at 0x804841E: main (myPgm2.c:6)
==pid== Address 0x1BA3607A is 0 bytes after a block of size 10 alloc'd
==pid== at 0x1B900DD0: malloc (vg_replace_malloc.c:131)
==pid== by 0x804840F: main (myPgm2.c:5)

3. Detecting the use of uninitialized variables:
Warning: 'uninitialised' value(s)

Eg:

int foo(int x)
{
if(x < 10)
{
printf("x is less than 10\n");
}
}

int main()
{
int y;
foo(y);
}

o/p:

==pid== Conditional jump or move depends on uninitialised value(s)
==pid== at 0x8048366: foo (myPgm3.c:5)
==pid== by 0x8048394: main (myPgm3.c:14)

4. Other improper use of memory:

4.a: If you call free twice on the same pointer value, Valgrind will detect this for you; you'll get an error:

Invalid free()

This is also called "double free attack":

free(x);
/* code */
free(x);

The easiest way to avoid it is simply to set your pointer to point to NULL once you've freed it:

free(x); x = NULL;
/* code */
free(x);

4.b: free should be matched with corresponding malloc. Similarly, delete with new and delete[] with new[].
If you do mismatch, you will get following error:

Mismatched free() / delete / delete []

What won't Valgrind find?
Valgrind doesn't perform bounds checking on static arrays (allocated on the stack).
Eg:

int main()
{
char x[10];
x[11] = 'a';
}

Valgrind won't alert you!

Also, if you don't test for buffer overflows by using long input strings, Valgrind won't tell you that your code is capable of writing over memory that it shouldn't be touching.

------------------------

Some common bugs in C/C++:
1. Uninitialized variables
2. Using a single equal sign to check equality:
while(x='Y') { ....}
3. Extra Semicolons:

int x;
for(x=0; x<100; x++);
Do something with x;

4. Overstepping array boundaries (especially if it static array):

int array[10];
//...
for(int x=1; x<=10; x++) do something with array[x];

-------------------------
Make file: Simple eg:

CC = gcc
FILES = in_one.c in_two.c
OUT_EXE = out_executable

build: $(FILES)
$(CC) -o $(OUT_EXE) $(FILES)

clean:
rm -f *.o core

rebuild: clean build

Advanced eg:
1. $@ is the name of the target.

client: client.c
$(CC) client.c -o $@

server: server.c
$(CC) server.c -o $@

List of dependents
$? - more recent than the target(i.e., those that have changed since the last time make was invoked for the given target)
$^ - all dependencies, regardless of whether they are more recent than the target, but removes duplicate names
$+ - like $^, but it keeps duplicates
$> - first dependency

Wildcard Matching in Targets (percent sign, %)
When a % appears in the dependencies list, it replaces the same string of text throughout the command in makefile target. If you wish to use the matched text in the target itself, use the special variable $*.
Eg:

%.c:
gcc -o $* $*.c

Implicit Targets

.c:
$(CC) -o $@ $@.c

This rule says that for any target that corresponds to a .c file, make should compile it using the name of the implicit target as the output, and the name plus the .c extension as the file to compile.

Replacing Text
To specify that OBJ is equivalent to SRC, except with the .c extension replaced with a .o extension:

OBJ = $(SRC:.c=.o)

Visit CProgramming.com for more details

Poem: The Road Not Taken by Robert Frost

Poem:

TWO roads diverged in a yellow wood,
And sorry I could not travel both
And be one traveler, long I stood
And looked down one as far as I could
To where it bent in the undergrowth;

Then took the other, as just as fair,
And having perhaps the better claim,
Because it was grassy and wanted wear;
Though as for that the passing there
Had worn them really about the same,

And both that morning equally lay
In leaves no step had trodden black.
Oh, I kept the first for another day!
Yet knowing how way leads on to way,
I doubted if I should ever come back.
I shall be telling this with a sigh
Somewhere ages and ages hence:
Two roads diverged in a wood, and
I took the one less traveled by,
And that has made all the difference.

Explanation and interpretation:
1. One possible interpretation of this poem can be summarized by Keating's quote from "Dead Poet Society" (movie) :
"We all are driven by conformity; difficulty in maintaining our own belief. We all have great need for acceptance, but you must trust that your belief are unique, even though others may think they are odd or unpopular."

2. The Road Not Taken seems to illustrate that once one takes a certain road, there's no turning back, although one might change paths later on, they still can't change the past.

Remembering names of Indian states

If someone asked us, how many states is India divided into ? Probably most of us won't be able to answer that. Even worse, what if we are asked to enumerate them.

Here is a simple way to remember all the states:

Btw, India is divided into 28 states and six union territories (Andaman-Nicobar, Daman-Diu, Chandigarh, Delhi, Dadara-Nagar Haveli, Lakshadeep and Pondicherry)

I have 3 mnemonics (Also see mnemonic for Periodic table)




(Ignore vowels)
1. JK par game kar ke Tao West Bengal gaye
(Jammu Kashmir, Punjab Rajasthan, Gujarat Maharashtra, Karnataka Kerala, Tamil Nadu Andra Pradesh Orissa, West Bengal)

Goa is below Maharashtra :)

2. HP hara MAC jhab UP UK gaye
(Himachal Pradesh, Harayana, Madhya Pradesh Chattisgarh, Jharkhand Bihar,Uttar Pradesh, UttarKhand)

Sikkim separates 1,2 from 3

3. Arun & Megha Assam trip mi nagmani ko dekha
(Arunachal Pradesh, Meghalaya, Tripura, Mizoram, Nagaland Manipur)

Computer Problem Solving

I found this interesting pic about "How to be Computer Genius". Funny and sarcastic :)

Microsoft Interview

I had an interview for internship at Microsoft. I was interviewed by SQL Server Analysis Services and SQL Server Reporting Services (I got offer from both :) ).

I was briefed by my recruitment coordinator at building 19. I had my interviews in building 34 and 35.

My interview questions were pretty easy. Here are some of them:
1. Write a program to create a balanced binary tree from a sorted array of integer.
>> Find the middle element. Make it root. recursively call the function for left and right subarray with root->left and root->right respectively.

2. Write a program to find angle between clock's minute and hour hand
>> assert(h >= 0 && m >=0)
return ( abs( 0.5*((h%12)*60 + m%60) - 6*(m%60)));

3. Consider there are 2 types of characters:
1byte character - has value less than 128
2 byte character - whose first byte has value >= 128
Given a random pointer in a byte array find the previous character

I was asked to solve the simpler version of the problem: i.e I was given the pointer to beginning of array.
>> Start from beginning of array till pointer (also keep track of prev character), if value <> 1 byte character. Goto next byte.
If value >= 128, => 2 byte character, move 2 bytes.

Lets assume if I was not given the begin pointer:
>> Assuming turing tape: the problem has atleast 1 non halting solution. Consider, tape filled with 128. :)

4. Given a string, reverse first n characters in each word of the string.
Eg: if string is "abcd ef"
and n =2 => o/p: "badc fe"
and if n =3 => o/p: "cbad ef" (if less than n characters, donot reverse)

5. Some probability based questions: 3 types of ball in bag with equal probability. Some of the atleast, atmax kind of questions. I am sure almost everyone has solved these type of questions in their undergrad.

6. Problem with Concurrent Reader, Exclusive Writer (CREW):
A writer may wait forever.
How to solve it?
Assign reader_priority = writer_priority = normal
When number of readers exceeds a threshold, --reader_priority
When writer writes and if reader_priority < normal, ++reader_priority

If reader_priority < norm, and if a reader comes, it will wait if there is writer waiting in the queue.

My suggestions:
Be confident. Revise Data Structures and Algorithms. Write few programs for practice.
Also talk to interviewer, clarify assumptions and state your algorithm before starting to write on the white board. Always check for boundary conditions (this is where most candidates get filtered).