## Goldman Sachs Interview Question

Software Engineer / Developersthi s pretty much wrong i guess

if the first node is not the one we are looking for then it will return 0 and the program would end..

HI Sneha, have a look & let me know if for any test cases it will fail

shashank7s dot blogspot dot com/2011/05/wap-to-implement-addsubtractmultiplicat dot html

PS:put . in place of dot & remove spaces"

Shashank

static int DistanceRec(btree *p, int nodeVal, int depth);

int Distance(btree *p, int nodeVal)

{

int depth;

depth = DistanceRec(p, nodeVal, 0);

if(depth >= 0)

return depth;

else

{

printf("error");

return -1;

}

}

static int DistanceRec(btree *p, int nodeVal, int depth)

{

int dep;

if(p == NULL)

return -1;

if(p->key == nodeVal)

return depth;

dep = DistanceRec(p->left, nodeVal, depth+1);

if(dep > 0)

return dep;

return DistanceRec(p->right, nodeVal, depth+1);

}

int finddistance(int n,tree *temp,int height=0)

{

if(temp->val==n)

return height;

else

{

if(temp->left!=NULL)

return findheight(n,temp->left,height+1);

if(temp->right!=NULL)

return findheight(n,temp->right,height+1);

}

}

<pre lang="" line="1" title="CodeMonkey76273" class="run-this">void findDistance(node *root, int find, int distance, int& maxdistance)

{

if(!root) return;

if(root->data==find) { maxdistance=distance; return; }

findDistance(root->left,find,distance+1,maxdistance);

findDistance(root->right,find,distance+1,maxdistance);

}

int main()

{

node *root=createTree();

int maxdistance=-1;

findDistance(root,25,0,maxdistance);

cout<<"The distance is "<<maxdistance;

cin.ignore(2);

return 0;

}</pre><pre title="CodeMonkey76273" input="yes">

</pre>

This is clearly wrong. No distinction is made between error case and success case. Node is searched in the right sub-tree even if it is already found in the left sub-tree. Should be modified to :

void findDistance(node *root, int find, int distance, int& maxdistance)

{

if(!root) return;

if(root->data==find) { maxdistance=distance; return; }

findDistance(root->left,find,distance+1,maxdistance);

if(maxdistance == -1){

findDistance(root->right,find,distance+1,maxdistance);

}

}

Do you know what 'wrong' means? This code is working for every situation. Not searching if already found is a good thing to incorporate but not doing so, in no way, makes the code wrong!

- desparate_prash June 11, 2011