Adobe Interview Question for Computer Scientists






Comment hidden because of low score. Click to expand.
0
of 0 vote

void printAllPath (node* root, int* pPath, int index)
{
	int i;
	if((root->lChild == 0) && (root->lChild == 0))
	{
		pPath[index]=root->data;
		for(i=0;i<=index;i++)
		{
			printf("[%d]",pPath[i]);
		}
		printf("\n");
	}
	else
	{
		pPath[index]=root->data;
		if(root->lChild)
		{
			printAllPath(root->lChild,pPath,index+1);
		}
		if(root->rChild)
		{
			printAllPath(root->rChild,pPath,index+1);
		}
	}
}

- Anonymous June 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Did you try to run this.
This code does not clears the pPath array so after first leaf path it will produce incorrect path.
Correct me if I am missing something.

- King@Work June 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think calling it separately for left sub tree and right sub tree will solve this issue.

- King@Work June 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Upt: I doubt that u understand the recursion. Trace it properly u'll come to know. BTW its tested code.

- Anonymous June 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you are correct. Can you post some link from where I can learn about recursion. I searched and found lots of them. Just asking in case if you have bookmark of any.

- King@Work June 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What I was thinking is we have a pointer to pPath which is an array and we never delete any element from it. Also the printing is done from 0 to index. So say if we consider right sub tree it should give correct results but when it comes to the left sub tree what will happen?

Try to help me that where I am going wrong.

- King@Work June 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now I got it, the index value is retained in each call and so does the array gets right values.

- King@Work June 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think you need to correct this.
if((root->lChild == 0) && (root->lChild == 0))

- King@Work June 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

correct;

- Anonymous June 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The above code works, no problem with the code. Only one change, the if condition when he is printing the path should be lchild && rchild.

- jay June 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a working function code that prints all paths from root to the leaves :
Note I have created a dummy main() to test the function.

#include<iostream>	/* Generic Headers */
using namespace std;

typedef unsigned int Uint;
struct node{
string val;
node* leftChild;
node* rightChild;
} *root, *A,*B,*C,*D,*E,*F,*G;

void printPath(node *p,string path)
{
    if(p->leftChild==NULL&&p->rightChild==NULL)
        { cout<<(path+"->"+p->val)<<endl; return; }
    if(p->leftChild!=NULL)
        printPath(p->leftChild,(path+"->"+p->val));
    if(p->rightChild!=NULL)
        printPath(p->rightChild,(path+"->"+p->val));
}

int main()
{
    A = new node; A->val = "A";
    B = new node; B->val = "B";
    C = new node; C->val = "C";
    D = new node; D->val = "D";
    E = new node; E->val = "E";
    F = new node; F->val = "F";
    G = new node; G->val = "G";
    A->leftChild = B; A->rightChild = D;
    B->leftChild = NULL; B->rightChild = C;
    C->leftChild = NULL; C->rightChild = NULL;
    D->leftChild = E; D->rightChild = F;
    E->leftChild = NULL; E->rightChild = G;
    F->leftChild = NULL; F->rightChild = NULL;
    G->leftChild = NULL; G->rightChild = NULL;
    root = A;
    printPath(root,"Start");
}

- puppet_master September 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Working tested code....

int printpath(tree *root)
{
    static int count;
    int i;
    if(!root)
    {
        return 0;
    }
    if(root->left == NULL && root->right==NULL)
    {
        a[count++]= root->data;
        for(i=0;i<count;i++)
            printf("__%d__",a[i]);
        printf("\n");
        return 0;
    }
    a[count++]= root->data;
    if(root->left!=NULL)
    {
        printpath(root->left);
        count--;
    }
    if(root->right!=NULL)
    {
        printpath(root->right);
        count--;
    }
    return 0;
}

- Mridul Malpani April 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
#include "iostream"
using namespace std;
struct node
{
node* left;
node* right;
string val;

node(string data )
{
val=data;
left=NULL;
right=NULL;
}
};


void printPaths(node* nd, string path)
{
if(nd==NULL)
return;

if(path.empty())
path = nd->val;
else
path+= nd->val;

if(nd->left==NULL && nd->right==NULL)
{
unsigned int i = 0;
while(i<path.size())
{
cout << path[i];
i+=1;
}
cout << endl;
return;
}
printPaths(nd->left,path);
printPaths(nd->right,path);
}

int main()
{
node* root = new node("A");
root->left=new node("B");
root->right=new node("C");
root->left->left=new node("D");
root->left->right=new node("K");
root->right->left=new node("Z");
root->right->right=new node("E");

printPaths(root,"");
}
}

- newB February 22, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More