A Dreamer's Blog

Keypad Question

2012-01-14T21:09:00.000-08:00

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:

#include<iostream>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<stdio.h>
using namespace std;

char digitmap[8][5] = {"abc","def","ghi", "jkl","mno","pqrs","tuv","wxyz"};

int lengths[] = {3, 3, 3, 3, 3, 4, 3, 4};

void PrintCombos(int N, int curr, char input[], char str[])
{
if(curr==N){
//cout<<"1"<<endl;
str[curr] = '\0';
printf("%s\n", str);
return;
}
else{
//cout<<"2"<<"\n"<<curr<<"\n";
for(int i=0; i<lengths[input[curr]-'0'-2] ; i++){
str[curr] = digitmap[input[curr]-'0'-2][i];
PrintCombos(N, curr+1, input, str);
}
}
}
int main()
{
char input[] = "23";
char str[100];
PrintCombos(2, 0, input, str);
return 0;
}

Vision

2012-01-13T06:34:00.000-08:00

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

2011-12-31T19:26:00.000-08:00

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

2011-12-31T01:45:00.000-08:00

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

2011-12-24T08:30:00.001-08:00

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

2011-12-18T05:39:00.000-08:00

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

2011-12-04T10:57:00.000-08:00

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

The algorithm I followed was simple. Construct a hash table for all the words in teh word list. Then using the same hash function, calculate has value for the same length of string in str and see whether it is in the table. If it is, match the actual string. If it matches, that means matching has started and now we need to see if the rest of the words are also there. If you don't find the next word in a continuous manner, then that means matching has not begun. So we start again, searching in the string.
The time complexity of my solution woudl be as follows:
Assume length of str is 'm'. Assume length of each word in word list is 'l'. Then the time complexity is O(m*l + n*l).
Space would be required for the hash table. I have taken it to be a bit larger than the maximum number of words expected (to reduce the possibility of a hash collision).
I am posting teh code as well for this one. I just wish I could have solved this one at that time. But no excuses. We live to fight another day.

If anyone of you has any better algorithm or can point out any bugs in the code, it would be welcome. :)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define FOR(i, a) for(i=0; i<a; i++)
#define MAXW 10
#define MAXH 1000

int table[MAXH] = {0};

void CalcHash(char s[][MAXW], int n, int l)
{
    int hash_key=0;
    int i, j;
    FOR(i, n){
        FOR(j, l){
            hash_key = (hash_key*10 + s[i][j]-'\0')%MAXH;
        }
        hash_key=hash_key%MAXH;
        table[hash_key] = i;
        hash_key=0;
    }
}

int CalcHashStr(char s[], int l)
{
    int i, hash_key;
    FOR(i, l){
        hash_key = (hash_key*10 + s[i]-'\0')%MAXH;
    }
    return (hash_key)%MAXH;
}

int CheckActualMatch(char *str, char *s, int l)
{
    int i=0;
    FOR(i, l){
        if(str[i]!=s[i])
            return 0;
    }
    return 1;
}

int CalcIdx(char s[][MAXW], char str[], int n, int l)
{
    int i, MatchStarted=0, Idx=-1, count=0, check_hash;
    CalcHash(s, n, l);

    i=0;
    while(i<strlen(str)){
        check_hash = CalcHashStr((str+i), l);

        if((table[check_hash]!=-1) && (MatchStarted==0)){
//            printf("1\n");

            if(CheckActualMatch(str+i, s[table[check_hash]], l)){
//                printf("11\n");
                MatchStarted=1;
                Idx=i;
                i=i+l;
                count++;
                continue;
                }
                else{
//                    printf("12\n");
                    MatchStarted=0;
                    Idx=-1;
                    count=0;
                    i++;
                    continue;
                }
        }
        else if((table[check_hash]!=-1) && (MatchStarted==1)){
  //          printf("2\n");
            if(CheckActualMatch(str+i, s[table[check_hash]], l)){
//                printf("21\n");
                i=i+l;
                count++;
                continue;
                }
            else{
//                printf("22\n");
                MatchStarted=0;
                Idx=-1;
                count=0;
                i++;
                continue;
                }
        }
        else if(count==n){
//            printf("3\n");
            return Idx;
        }
        else if(table[check_hash]==-1){
//            printf("4\n");
            MatchStarted=0;
            Idx=-1;
            count=0;
            i++;
            continue;
        }
    }
    return Idx;
}

int main()
{
    int i;
    char str[] = "acdsatcatratjahs";
    char s[3][10] = {
        "cat",
        "rat",
        "sat"
    };
    FOR(i, MAXH){
        table[i]=-1;
    }
    printf("%d\n", CalcIdx(s, str, 3, 3));
    return 0;
}

My Facebook Experience

2011-11-09T08:29:00.000-08:00

I recently gave an exam for Facebook. The process is as follows:

First there is an online test. Usually there is one programming question that is to be answered. The question concentrates on algorithms and datastructures. The time limit for it is about 60 minutes or 90 minutes depending on the question.
After you qualify the online test, you receive a call from Facebook and a phone interview is set up with one of their engineers. This interview again lasts for about an hour and you have to code online a solution to the question asked by the engineer while talking to him. You will have to optimize your code and remove bugs, etc. And explain your whole approach well.
If you qualify this telephonic screening round, you are called to Palo Alto for an on-site interview.

Conway's Game of Life

2011-10-01T01:05:00.000-07:00

Conway's Game of Life is a very famous problem in cellular automata. It is a zero player game which means no input is required, just a few rules and then evolution is determined by the initial state and the rules that define the existence.

The usual rules are described as follows. At each step in time, the following transitions occur:

Any live cell with fewer than two live neighbours dies, as if caused by under-population.
Any live cell with two or three live neighbours lives on to the next generation.
Any live cell with more than three live neighbours dies, as if by overcrowding.
Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

Initial pattern is known as the seed and at every step, the rules are applied again and again to see the evolution process.

Today I will be discussing the algorithmic implementation of this problem.

Input: A board describing the initial state of the system.

Output: It is continuously displayed showing the state of the system at every step. It can be in various ways, either an applet or an animation or just the static output of the system displaying the state of the system after a particular number of steps.

Datastructure to be Used: It can be a board of NxN (N specified by user) with each cell/node denoting whether the cell is alive, dead or empty. Call this Board[1...N][1...N]. Keep another such datastructure in hand known as NextState[1...N][1...N] and initially this structure has the same entries as Board[][].

Algorithm:

1. Call a function which checks the state of the system for satisfaction of any of the rules above stated. If any rule is satisfied, then update the changes in the NextState[][] structure.

2. After the changes have been made to the NextState[][] structure, call another fucntion FormNextGeneration() which updates Board[][] with values in NextState[][]. Board[][] now has the next state values in it.

3. To display these values or state of the system just call a function Display() which has the applet or simply sends the state to stdin.

Hence we have successfully implemented a simple version of Conway's Game of Life.

The complex version involves many other rules for reproduction, mutation, extinction et al.

Hope this one helped! :)

An Important Announcement!

2011-09-30T09:30:00.000-07:00

Hey, there is some good news I have to share. Stanford School of Engineering has made some of its classes available online.
You can register for them here: ml-class.org (for Machine Learning)
ai-class.com (for Artificial Intelligence)

I would seriously advise you to register for at least the basic courses. They have some really good material explained extremely well by some of teh really good researchers at Stanford like Andrew Ng (Professor at Stanford) for Machine Learning and Sebastian Thrun (Professor at Stanford) & Peter Norvig (works at Google as Director of Research). These people have done some commendable work in this field and I would definitely advise you to read some of their papers and/or their books in order to familiarize yourself with this field.

What Just Happened Back in There?

2011-09-04T21:25:00.000-07:00

Why O why?!
I did well, didn't I? Nothing went wrong. Well might not be enough.
Still, don't have any regrets or anger at myself at least.
Ah, maybe another day. We'll all float on alright.
(Sorry people this is pretty much random.)

Importance of Writing Professional Code

2011-08-31T05:17:00.000-07:00

Sorry for not writing in a long time, recently gave my TOEFL exam but that wasn't the only reason for my absence. :)
So, coming back to the main topic, today I will talk about the importance of writing professional code and little little things that can help you how to walk that path.

Many people would argue that this is a completely futile post as they may have the opinion, "I can code, how does it matter where I leave space or whether I indent it or not!". There is no argument with the fact that it is of utmost importance to know how to code. But it is also important that other people be able to easily understand and develop over your code because when you work for a company, you ill not be developing every single thing from scratch. Inevitably, you will be using code developed by others and you will develop code that will be used by others. Because of this simple reason, it is very important that your code be easy to understand and trace through.
Secondly, it will be easier for you as well to understand your own code after some time. Yes, this does happen, at least it happened with me! I couldn't understand my own code after some time.
So here are a few things to keep in mind:
1. DO NOT write the function which computes the result in main. This is one of the most common mistakes that beginners make, I used to do that as well. Main is there to call functions which compute your result and not to actually perform the grunt work.
2. Make your code as modular as possible. If you have an algorithm which computes the answer using different algorithms/steps, you can have separate functions. This even helps in reducing the amount of code you have to write. How? e.g. if I want to write code for finding out the height of a tree, I will first construct the tree and add a few nodes. I don't need to write that part of the code again if I have a function previously coded already, I can just copy and paste.
3. This is again one of the most ignored basic rules of writing good code, make your variable names, function names, etc. extremely descriptive of what they represent. Even if it makes the name longer. Having numNodes is much better than 'n'. Having IsBalancedBST() is much easier to understand than ibbst() or any other short uninformative name. This helps a lot in remembering what those variables and/or functions represent and you can understand what a function does by just looking at its name. Makes life easier, doesn't it?

These are the only ones I could think of right now. If I come up with more, I will mention them later.

The Tanenbaum V/S Cormen Debate

2011-08-14T00:11:00.000-07:00

Before I begin this post I would like to point out that the opinions expressed in this post are solely mine. This strategy worked for me doesn't mean it will work for everyone. Everyone be the better judge for himself.
So this question has come up several times in the mind of freshmen et al in the field of computer science whether to study from the book Data Structures by Tanenbaum or Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.

People usually prefer the pure clear explanation given by Cormen rather than the lengthy discussion given by Tanenbaum. Tanenbaum treats the problem at every level and describes an indepth analysis of the solution presented (which comprises of complete code) and then discusses further modification which can improve the implementation even further. Cormen (LCRS) on the other hand describes the algorithm straight away and provides pseudocode. It does not delve into a deep discussion of the data structure or algorithm in question like Tanenbaum does. Even though I prefer reading the pseudocode to the actual code, I personally prefer the book Tanenbaum and studying from it has what made the difference for me (caveat: many people would differ from me saying that Tanenbaum is actually an extremely boring book which they don't feel like studying from so decide for yourself). Tanenbaum not only describes the data structure and its implementation, the operations that would be performed on it, etc but also discusses the data structure from an application point of view. This is where the difference comes in. By studying from Cormen you will easily be able to learn a data structure, algorithms associated with it but when it comes to a real life problem when you actually have to act as an engineer, you would need to think really hard in order to understand where all can this particular data structure be used and where all it should be used. Tanenbaum even discusses real life problem by providing an example of queues in a bank in the chapter on Linked Lists and then he discusses a scheduling problem and solves it with the help of graphs in the chapter Graphs. All of these topics most of the people don't even study but these examples help to develop a thinking with regard to its applications in a real world.
Of course, sometimes it is just too difficult to study from the verbose style that Tanenbaum has (Initially even I was stuck in several places). In that case, one can study the algorithm and data structure from Cormen first and then go over Tanenbaum.
Ultimately it depends on your learning style. Some people just can't study that much verbose text, they might want only clear cut pseudocode. I draw an analogy here by saying that I prefer reading classics while most people don't. So this really is a subjective thing.

Who Am I?

2011-08-04T19:37:00.000-07:00

I apologize friends, amidst all this coding I forgot to write an introductory paragraph about myself. Why should you even read my blog? And who am I to advise you?

I am a student of Netaji Subhas Institute of Technology, University of Delhi (this college ranks better than DCE if you are unaware of it) and currently in my senior year. I am a student of Computer Engineering. As ironical as it may sound, there are not many computer science courses in our syllabus for Computer Engineering so he students just have to learn and find out what to learn everything by themselves. So like the rest of the students in my college I started to research about different things in computer science from my second year onwards (my first year I spent watching movies and listening to bands if you really want to know :P). Computer science is such a vast field, SUCH a vast field that you have so many options whether you're into coding or just system analysis. Some of the different fields are machine learning, data mining, networking, if you're on the hardware side then architecture, or artificial intelligence if you are into the fun stuff (referred to as fun here because it's fun for me :) ), operating systems, database management systems, computer vision, natural language processing, computational neuroscience (another very interesting subject), and the list goes on.
I started to work in a startup in my second year and that is when I really got to know what's out there in the world, what all engineers are supposed to know, how much most of them actually know, how stuff works, et al.
I am really interested in machine learning and artificial intelligence. I have done projects in natural language processing and image processing. I am working currently on another project in the field of machine learning (more like thinking about the problem first). Details shall be posted once I'm ready with the implementation of the solution.
I have 2 publications as of now, one titled “A March Towards Constructivism based on Storytelling, Gaming and Collaboration”, Published at The Fifth International Conference of Learning International Networks Consortium (LINC), MIT May 23rd – 26th 2010 and another one titled "‘ShruthLaikh’: Employing Python to Develop Vocabulary Enhancing Application" describing the artificial intelligence techniques employed in the application at Pycon Asia Pacific.
Furthermore I am recipient of Google Women in Engineering Award, 2011.
So despite the fact that I am not much of a coder, I believe I am a good solution developer and can develop systems components etc. well. I can think well from a higher view of the whole problem rather than the actual coding-level implementation. Which is why most of the time I work with MATLAB. C/C++ are the other two languages I work a lot with. We all have our strengths and weaknesses. I have mine too. And it's always good to know yours.

How I Reached Adobe Final Round and Got Rejected :(

2011-08-02T10:38:00.000-07:00

So basically there was a written round first in which there were 3 sections

Quant & Analytical (Puzzles) : Quant was pretty easy. Analytical took time but definitely not tough. Can be cracked. Just try to do some logical puzzles preferably from careercup
C : This tested some basic knowledge of C. Do Test Your C Skills from Kanetkar and you'll do fine.
Data Structures : This was the tricky part. No specified syllabus in this. Some questions were easy like reversing a linked list but some were difficult, algorithmic. Some required you to think a lot like the ones from Operating Systems. Do OS well, they ask from it a lot and that too all conceptual.

The written exam was given by around 140 people and 23 were selected for the interviews.

The interviews were basically 3 Technical and 1 HR although you can be eliminated before giving all 3 technical. My first round was pretty easy. I could solve most of the questions with time efficient solutions. 2nd round was more about resume and puzzles. And that too don't expect them to throw a puzzle at you right out of some book/website. They will ask for generalized solutions and you will have to think.

3rd round was the dip for me. Easy questions again but I didn't quite remember STL stuff of C otherwise there was not much to it.

After the 3rd round I wasn't called for the HR. End of story.

Anyway, may be some other day.

Heap Sort

2011-07-30T11:14:00.001-07:00

This is another sorting algorithm working in O(nlogn) time.

//WORKING FINALLY! :)

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
#define MAXS 100
#define LEFT(i) (2*i+1)
#define RIGHT(i) (2*i+2)
#define PARENT(i) ((i-1)/2)
#define FOR(i, a) for(int i=0; i<a; i++)
using namespace std;

int HeapSize;

void SWAP(int *a, int *b)
{
     int tmp;
     tmp=(*a); (*a)=(*b); (*b)=tmp;
     }

void Heapify(int A[], int i)
{
     if(i<HeapSize){
         int l = LEFT(i);
         int r = RIGHT(i);
         int largest;
         if(l<HeapSize && A[l]>A[i])
                        largest = l;
         else largest = i;
         if(r<HeapSize && A[r]>A[largest])
                        largest = r;
         if(largest!=i){
                       SWAP(&A[i], &A[largest]);
                         Heapify(A, largest);
                       }
         }
         else return;
     }

void BuildHeap(int A[], int n)
{
     HeapSize = n;
     for(int i=(n-1)/2; i>=0; i--){
            Heapify(A, i);
            }
     }

void HeapSort(int A[], int n)
{
     BuildHeap(A, n);
     for(int i=n-1; i>=1; i--){
             SWAP(&A[0], &A[i]);
             HeapSize--;
             Heapify(A, 0);
             }
     FOR(i, n)
     cout<<A[i]<<endl;     
     }
int main()
{
    int A[] = {3, 61, 9, 2, 55, 100, 4};
    int n=7;
    HeapSort(A, 7);
    getch();
    }

Young's Tableau (Matrix Sorted Row & Column Wise)

2011-07-20T05:50:00.000-07:00

An m x n Young tableau is an m x n matrix such that the entries of each row are in sorted order
from left to right and the entries of each column are in sorted order from top to bottom. Some of the
entries of a Young tableau may be 1, which we treat as nonexistent elements. Thus a Young tableau
can be used to hold r <= mn numbers.
Given such a matrix, find an element in the best time.

Searching for an element in Young's Tableau

//WORKING PERFECT!

#include<iostream>
#include<conio.h>
#include<cstring>
#include<cmath>
#define FOR(i, a) for(int i=0;i<a;i++)
#define MAXS 100
using namespace std;

bool SearchYoungTableau(int a[][MAXS], int *x, int *y, int ele, int m, int n)
{
*x = m-1;
*y = 0;
while((*x)<m && (*y)<n){
if(a[*x][*y]==ele) {return true;}
if(a[*x][*y]>ele){ 
(*x)--; 
continue;
}
else if(a[*x][*y]<ele){
(*y)++;
continue;
}
}
return false;
}

int main()
{
int x, y;
int a[MAXS][MAXS];
a[0][0] = 1;
a[0][1] = 2;                    
a[1][0] = 3;
a[1][1] = 4;
cout<<SearchYoungTableau(a, &x, &y, 2, 2, 2)<<endl;
cout<<"x, y = "<<x<<", "<<y<<"\n";
getch();
return 0;
}

Sum of Nodes Which Have no Siblings Using Recursion

2011-07-20T05:44:00.000-07:00

Find the sum of all nodes in a BST which have no siblings.

//WORKING FNE

#include<iostream>
#include<conio.h>
#include<cstring>
#include<cmath>
#define FOR(i, a) for(int i=0;i<a;i++)
#define LEFT(i) (i*2+1)
#define RIGHT(i) (i*2+2)
#define MAXS 100
using namespace std;

struct node{  
int info;  
struct node *left, *right;  
};  
typedef struct node * N;  
N tree=NULL; 

N search(int x)  
{  
N p, q;  
p=tree;  
q=NULL;  
if(p==NULL) {cout<<"Not Found"; return NULL;}  
while(p!=NULL){  
q=p;  
if(p->info==x) {cout<<"Found\n"; return p;}  
p=(x<p->info)?(p->left):(p->right);  
}  
if(p==NULL && q!=NULL) {cout<<"Not found\n"; return NULL;}  
}  

void insert(int x)  
{  
N p, q, tmp;  
p=tree;  
q=NULL;  
tmp = (N)malloc(sizeof(struct node));  
tmp->info=x;  
tmp->left=NULL;  
tmp->right=NULL;  
if(p==NULL) {tree=tmp; return;}  
while(p!=NULL){  
q=p;  
p=(x<p->info)?(p->left):(p->right);  
}  
if(x<=q->info) {q->left=tmp; return;}  
else { q->right = tmp; return; }  
} 

int sum;

void SiblingSum(N root)
{
if(root==NULL || (root->left==NULL && root->right==NULL))
return;
if((root->left==NULL) && root->right!=NULL){
sum+=root->right->info;
SiblingSum(root->right);
}
else if((root->right==NULL) && root->left!=NULL){
sum+=root->left->info;
SiblingSum(root->left);
}     
else{
SiblingSum(root->left);          
SiblingSum(root->right);                    
}
}

int main()  
{  
int ans, x, h, index;  
char * s, *t;
s = (char*)malloc(sizeof(char)*20);
do{  
cout<<"Choose\n1.Insert\n2.Find\n3.SiblingSum\n4.Height\n5.Diameter\n6.Exit\n";  
cin>>ans;  
if(ans==1){  
cin>>x;  
insert(x);  
}  
else if(ans==2){  
cin>>x;  
search(x);  
}  
else if(ans==3){  
SiblingSum(tree);  
cout<<sum<<endl;
sum=0;
} 
}while(ans!=6);  
getch();  
return 0;  
}

Breadth First Search of a Graph Using Adjacency Matrix

2011-07-20T05:42:00.000-07:00

//WORKING!

#include<iostream>
#include<conio.h>
#include<cstring>
#include<cmath>
#define FOR(i, a) for(int i=0;i<a;i++)
#define MAXS 100
using namespace std;

int gMat[MAXS][MAXS], data[MAXS], visited[MAXS];

struct Queue{
int front, back;
int item[MAXS];
};
struct Queue q;

void EnQ(int j)
{
q.back++;
q.item[q.back] = j;
if(q.front==-1)
q.front=q.back;
return;
}

void init()
{
q.front=q.back=-1;
}

bool isEmpty()
{
return q.front==q.back;
}

int DeQ()
{
int tmp = q.item[q.front];
q.front++;
return tmp;
}

void BFS(int n)
{
int i=0;
EnQ(i);
while(!isEmpty()){
i = DeQ();
if(!visited[i])
printf("%d\n", data[i]);
visited[i]=1;
for(int j=0; j<n; j++){
if(gMat[i][j]){
EnQ(j);
}
}

}//while ends
}

int main()
{
int n;
cin>>n;
FOR(i, n)
FOR(j, n)
cin>>gMat[i][j];
FOR(i, n) cin>>data[i];
BFS(n);
getch();
}

Implementation of Trie

2011-07-20T05:40:00.000-07:00

This is the implementation of a trie which is a data structure that can reduce the time complexity of searching for a word to O(L) where L is the length of that particular word. This means that even if we have a dictionary with 45,000 words, searching time would still remain O(L). Pretty cool, isn't it!

//Woohoo, this is working!
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
#define FOR(i, a) for(int i=0; i<a; i++)
using namespace std;

struct Trie{
int next[26];
};
typedef struct Trie T;
T nodes[1000];
static int last;

void addNode(char s[], int m)
{
int current = 0;
FOR(i, m){
if(nodes[current].next[s[i]-'a']==-1){
nodes[current].next[s[i]-'a'] = (last+1);
last++;
FOR(j, 26) nodes[last].next[j]=-1;
current = last;
}
else{
current = nodes[current].next[s[i]-'a'];
}
}
}

bool exists(char s[], int m)
{
int current = 0;
FOR(i, m){
if(nodes[current].next[s[i]-'a']==-1) return false;
else{
current = nodes[current].next[s[i]-'a'];
}
}
return true;
}

int main()
{
char s[20];
int ans;
int m;
FOR(i, 26)
nodes[0].next[i] = -1;
cin>>s>>m;
addNode(s, m);
do{
printf("What do you want to do?\n1.Enter a word\n2.Exist\n3.Exit\n");
cin>>ans;
if(ans==1) { cin>>s>>m; addNode(s, m); }
else if(ans==2) {cin>>s>>m; printf("%d\n", exists(s, m));}
}while(ans!=3);
return 0;
}

Searching for an Element in a Rotated Array

2011-07-19T06:41:00.000-07:00

//Rotated Array
#include<iostream>
#include<conio.h>
#include<cstring>
#define FOR(i, a) for(int i=0;i<a;i++)
#define MAXS 100
using namespace std;

int FindSpike(int a[], int lo, int high, int n)
{
int mid = (lo+high)/2;
while(1){
mid = (lo+high)/2;
if(mid!=0 && mid!=n-1){
if(a[mid]<a[mid-1] && a[mid]<a[mid+1]) {return mid;}
else if(a[mid]>a[mid-1] && a[mid]>a[mid+1]) {return mid;}
}
if(a[mid]<a[lo] && a[mid]<a[high]) {high = mid; continue;}
else if(a[mid]>a[high] && a[mid]>a[lo]) {lo = mid; continue;}
}
return mid;
}

bool BinSearch(int a[], int start, int end, int x)
{
int mid;
while(start<end){
mid = (start+end)/2;
if(a[mid]==x) return true;
else if(a[mid]>x) {end = mid-1; continue;}
else {start=mid+1; continue;}
}
if(start==end && a[start]==x) return true;
return false;
}

int FindEle(int a[], int n, int x)
{
int pt = FindSpike(a, 0, n-1, n);
if(x<=a[pt-1] && x>=a[0])  return BinSearch(a, 0, pt-1, x);
else return BinSearch(a, pt, n-1, x);
}

int main()
{
int a[] = {6, 7, 8, 1, 2, 3, 4, 5};
cout<<FindSpike(a, 0, 7, 7)<<endl;
int x=11;
cout<<FindEle(a, 8, x)<<endl;
getch();
return 0;
}

Check Whether Two Strings are Anagrams

2011-07-19T06:40:00.000-07:00

//WORKING!

//Check whether 2 strings are angrams of each other in O(n) time

#include<iostream>  
#include<conio.h>  
#include<cstring>  
#include<algorithm>  
#define FOR(i, a) for(int i=0; i<a; i++)  
#define MAXS 10  
#define INF 32000 
#define SIZE 256 
#define MIN(a, b, c) ((a>b)?(b<c?b:c):(a<c?a:c))  
using namespace std;

int CharSet[SIZE];

bool CheckAnagrams(char A[], char B[])
{
if(strlen(A)!=strlen(B))
return false;
for(int i=0; i<strlen(A); i++){
CharSet[A[i]-'a']++;
CharSet[B[i]-'a']--;
}
FOR(j, SIZE){
if(CharSet[j]!=0)
return false;
}
return true;
}

int main()
{
char A[] = "abcd";
char B[] = "cbae";
cout<<CheckAnagrams(A, B);
getch();
}

Median of Two Sorted Arrays after Merging in log(N) Time

2011-07-19T06:39:00.001-07:00

//WORKING SWEET!
//Median of 2 Sorted Arrays in logn Time

#include<iostream>  
#include<conio.h>  
#include<cstring>  
#include<algorithm>  
#define FOR(i, a) for(int i=0; i<a; i++)  
#define MAXS 10  
#define INF 32000  
#define MIN(a, b, c) ((a>b)?(b<c?b:c):(a<c?a:c))  
using namespace std; 

int MedianSortedArrays(int A[], int B[], int higha, int lowa, int highb, int lowb)
{
int mida = (higha+lowa)/2;
int midb = (highb+lowb)/2;    
if(mida==midb) return A[mida];
if(higha==lowa && highb==lowb) return (A[higha]+B[highb])/2;
if(mida>midb){
return MedianSortedArrays(A, B, mida-1, lowa, highb, midb+1);
}
if(mida<midb){
return MedianSortedArrays(A, B, higha, mida+1, midb-1, lowb);
}
}

int main()
{
int ar1[] = {1, 12, 15, 26, 38};   
int ar2[] = {2, 13, 17, 30, 45}; 
cout<<MedianSortedArrays(ar1, ar2, 4, 0, 4, 0);
getch();
}

Construction Of BST Using Inorder and Preorder Traversal

2011-07-19T06:37:00.000-07:00

//WORKING FINE!

//Construct a BST from inorder and preorder traversal

#include<iostream>  
#include<conio.h>  
#include<cstring>  
#include<algorithm>  
#define FOR(i, a) for(int i=0; i<a; i++)  
#define MAXS 10  
#define INF 32000 
#define SIZE 256 
#define MIN(a, b, c) ((a>b)?(b<c?b:c):(a<c?a:c))  
using namespace std;

struct node{  
int info;  
struct node *left, *right;  
int maxSum;
};  
typedef struct node * N;  
N tree=NULL; 

N ConstructBSTInorderPreorder(int inOrder[], int preOrder[], int start, int end)
{
static int idx = 0;
int inIdx=0;
if(start>end)     return NULL;
N tmp;
tmp = (N)malloc(sizeof(struct node));
tmp->info = preOrder[idx++];
tmp->left=NULL;
tmp->right=NULL;
if(start==end)
return tmp;
for(inIdx=start; inIdx<=end; inIdx++){
if(tmp->info==inOrder[inIdx])
break;
}
tmp->left = ConstructBSTInorderPreorder(inOrder, preOrder, start, inIdx-1);
tmp->right = ConstructBSTInorderPreorder(inOrder, preOrder, inIdx+1, end);
return tmp;
}

void inorder(N p)
{
if(p==NULL) return;
inorder(p->left);
printf("%d\n", p->info);
inorder(p->right);
}

void preorder(N p)
{
if(p==NULL) return;
printf("%d\n", p->info);
preorder(p->left);
preorder(p->right);
}

int main()
{
int in[] = {1, 2, 3, 4, 5, 6};
int pre[] = {4, 2, 1, 3, 5, 6};
int len;    
len = sizeof(in)/sizeof(int);
tree = ConstructBSTInorderPreorder(in, pre, 0, len-1);
inorder(tree);
cout<<"\n";
preorder(tree);
getch();
}

Construction Of BST Using Inorder and Postorder Traversal

2011-07-19T06:36:00.000-07:00

//WORKING FINE!

//Construct a BST from inorder and preorder traversal

#include<iostream>  
#include<conio.h>  
#include<cstring>  
#include<algorithm>  
#define FOR(i, a) for(int i=0; i<a; i++)  
#define MAXS 10  
#define INF 32000 
#define SIZE 256 
#define MIN(a, b, c) ((a>b)?(b<c?b:c):(a<c?a:c))  
using namespace std;

struct node{  
int info;  
struct node *left, *right;  
int maxSum;
};  
typedef struct node * N;  
N tree=NULL; 

N ConstructBSTInorderPostorder(int inOrder[], int postOrder[], int start, int end, int idx)
{
int inIdx=0;
if(start>end)     return NULL;
N tmp;
tmp = (N)malloc(sizeof(struct node));
tmp->info = postOrder[idx];
tmp->left=NULL;
tmp->right=NULL;
if(start==end)
return tmp;
for(inIdx=start; inIdx<=end; inIdx++){
if(tmp->info==inOrder[inIdx])
break;
}
tmp->right = ConstructBSTInorderPostorder(inOrder, postOrder, inIdx+1, end, idx-1);
tmp->left = ConstructBSTInorderPostorder(inOrder, postOrder, start, inIdx-1, idx-1-(end-inIdx));
return tmp;
}

void inorder(N p)
{
if(p==NULL) return;
inorder(p->left);
printf("%d\n", p->info);
inorder(p->right);
}

void preorder(N p)
{
if(p==NULL) return;
printf("%d\n", p->info);
preorder(p->left);
preorder(p->right);
}

int main()
{
int in[] = {1, 2, 3, 4, 5, 6};
int pre[] = {4, 2, 1, 3, 5, 6};
int post[] = {1, 3, 2, 6, 5, 4};
int len;    
len = sizeof(in)/sizeof(int);
tree = ConstructBSTInorderPostorder(in, post, 0, len-1, len-1);
inorder(tree);
cout<<"\n";
preorder(tree);
getch();
}