Keypad Question

This question has been asked in interviews of many giant tech companies. The statement is:
Given a string in the form of numbers on a keypad of a mobile phone, print all the combinations of alphabets that are possible if the numbers are typed on a phone. Assume that the numbers 0 and 1 are not typed.
e.g.
input = 3
output = {d, e, f}
input = 24
output = {ag, bg, cg, ah, bh, ch, ai, bi, ci}
The algorithm I used is a simple recursive one in which the characters are chosen according to the input alphabet and the current character being observed as shown below:

Vision

For quite some time, I had been struggling with choosing a name for this blog mainly because of a lack of vision as to what I want it to be. I could not point to my blog and say that this is what differentiates it from the gazillion other blogs out there on the internet.
But now, I have decided to give it a more concrete shape, an identity. This blog will continue to discuss algorithmic questions but I won't limit it to that only - this blog will also be a motivational blog. Thanks to my friend Pragya Agarwal for giving me the inspiration to take this step.

How To Print a Linked List in Reverse Order

The question is simple, print the contents of a linked list in reverse order. The question can be easily solved, the trick (as always) is to solve it efficiently. Let's first analyze the minimum time complexity that can be achieved. Since we have to print the contents of the list, the tie complexity cannot be lesser than O(n) where n is the number of nodes. The minimum space complexity can be O(1) which will be achieved as I move further and further.

The first and easiest way to think about solving this problem is recursion. Observe the following code (warning - all untested code):

void printRev(Node * root)
{
if(root==NULL)
return;
printRev(root->next);
printf("%d", &root->info);
}

But the usual problem with recursion - it uses stack space which we don't want it to. Moreover you might run out of space.

So a method I could come up with of O(n) tie complexity and O(1) space complexity is reversing the linked list, printing the info in the normal order and then reversing the linked list again (to ensure you've not changed your actual data). Since we are reversing and want to have O(1) space complexity obviously we cannot use a method for reversing that utilizes space greater than O(1). Hence I'm using the three pointer method to reverse the linked list.
The code for reversing and then printing:

void RevLL(Node * head)
{
Node *p, *q, *r;
if(head == NULL)
{
return;
}
p = head;
q = p->next;
p->next = NULL;
while (q != NULL)
{
r = q->next;
q->next = p;
p = q;
q = r;
}
head = p;
}


void printLL(Node * head)
{
if(head==NULL)
return;
Node * tmp= head;
while(tmp!=NULL){
printf("%d", tmp->info);
tmp=tmp->next;
}
}
void printRev(Node * head)
{
RevLL(head);
printLL(head);
RevLL(head);
}

Again a warning, the above code is untested and there will probably be bugs in it but my main intention was to develop the algorithm.
If someone has an idea to print the contents in reverse order without reversing the linked list and in one pass, they're very welcome.

The Year in Retrospect

As this year comes to a dramatic end, I’d like to say it has been a year of great personal learning.
I would like to thank everyone instrumental in helping me realize certain very important things in life, the first of which is –you can’t always get what you want but remember that you might just deserve better. Don’t ever doubt yourself, especially not for people who don’t understand you. Don’t let them break you.
Measure your own worth and don't let anyone underestimate that.
Don't make anyone a priority if you're just an option for them. Let this line sink in, before it gets late.
Sure it hurts to see your commitment and your fidelity to someone or something go to waste. But learn from it, analyze where you went wrong. Learn how to not repeat the same mistakes. Your faith deserves to be in better hands.
Take care of your character and your reputation will take care of itself.
Learn to look at life from another person's perspective. You cannot look at another's actions from a tainted glass just to prove your point. What might be moral for you, might be immoral for another human being.
Don't emulate false idols. Obsessing over the phonies doesn't teach you anything and ignoring people who matter for those phonies is atrocious.
If you believe you will have a deep and meaningful association with someone, pursue it and don't hesitate to take the first step. Sometimes, you meet true friends around unexpected corners. Value them.
Life teaches a lot, learn from it. Everything plays its part even if something appears to be for the worse or a failure. Holding on to a broken past will only pinch more. Let the pain subside and wisdom derived from it prevail. You'll not be moving on with a baggage of failure but a life of wisdom and experience.
As I said last year, there’s a lot remaining, a lot to be achieved, a lot to be done, a lot to be learnt and a lot of fun :-)
Lastly, thank you all the followers of this blog and apologies for not posting more often. :-)
Happy New Year!

An Enlightening Thought

From some blog I follow:

A failure is a project that doesn't work, an initiative that teaches you something at the same time the outcome doesn't move you directly closer to your goal.

A mistake is either a failure repeated, doing something for the second time when you should have known better, or a misguided attempt (because of carelessness, selfishness or hubris) that hindsight reminds you is worth avoiding.

We need a lot more failures, I think. Failures that don't kill us make us bolder, and teach us one more way that won't work, while opening the door to things that might.

School confuses us, so do bosses and families. Go ahead, fail. Try to avoid mistakes, though.

Grace Hopper Conference India

I recently attended the second Grace Hopper Conference India. Definitely an experience worth having for all women engineers, the whole event was well organized, extremely well thought out, had some of the best women engineers under one roof and was for me as well as for many present over there, I'm sure, quite a learning and inspiring experience.
The keynote speeches were one of the highlights. Specifically I would like to point out to the speech given by Dr. Sunita Maheshwari, Senior Consultant Pediatric Cardiologist and Chief Dreamer, RXDX and Teleradiology Solutions. Her speech showed how people from a completely academic background can also become successful entrepreneurs. If you haven't seen it already, I highly recommend it. I will post the links once I get them.
The sessions were divided into tracks including Student track, New Career track, mid-level/Senior Management track, Program Management track, Strategy Management track, Academic Research track, Technical tracks. Each track had a Moderator and a panel. Interesting discussions some of them.
Another thing about which I'm very proud is that a girl from my class in my college, Vrinda Vasisth, won the technical student "Are the Queen of Geekdom" contest from among 35 students. Hearty Congratulations to you Vrinda, you did the college proud :)
Another highlight of the conference was the Women Entrepreneur Quest with finalists who had some brilliant ideas for startups. I will talk more about this Entrepreneur Quest in a later blog post. The winner was a woman who had developed a website for the overall management of apartment societies.
Further information can be found here.

My Facebook Question

The Facebook question (which I could not solve then because I forgot to add one silly line in between despite having the same algorithm :( ) that I had for the written round is as follows:
Given a word list of n strings of the same length l and a large string str, which contains a permutation of all of those words in the wordlist in one continuous sequence without changing the words themselves, find the index of the starting position of that permutation.
e.g. n = 2;
s[][] = {"you", "mel"}
str = "sbakdabskdyoumeldbkasbdas"
Index = 10