## Goldman Sachs Interview Question for Software Engineer / Developers

• 0

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

``````int distance(Node *n, int key, int dist){

// if node is null, key couldn't be found
if(!n) return 0;

if(n->val == val) return 0;

distance(n->left, val, dist+1);
distance(n->right, val, dist+1);
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

thi 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..

Comment hidden because of low score. Click to expand.
-1
of 1 vote

a slight change and think this would work

``````int distance(Node *n, int key, int dist){

// if node is null, key couldn't be found
if(!n) return 0;

if(n->val == key) return dist;

distance(n->left, val, dist+1);
distance(n->right, val, dist+1);
}``````

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

is it binary search treE??

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

Shanshank code is working for all the cases but a small drawback is that it is not efficient when the parent pointer overhead occurs....

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

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

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

Shanshank is working fine for all the cases but the problem raises when the parent pointer overhead occurs...

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

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);
}

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

//call with height=1

``````int distance(int num,tree *temp,int height)
{
if(temp==NULL) return 0;
if(temp->val==n)
return height;
else return (distance(n,temp->left,height+1) | distance(n,temp->right,height+1));
}``````

//finally check if height=0 then element doesnt exist...

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

distance of any node to any other node that is below it. Assume: n2 is below n1.

Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2*Dist(root, lca)

in this, Dist(n1, n2) = Dist(root, n2) - Dist(root, n1)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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);

}
}

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

This is wrong.Every time it is incrementing the height.Say the data is the first node of the right tree.Your code will give result as heIght of left +1.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

<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>

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

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);
}
}

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

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!

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

and to distinguish between error and success, the output will be -1 if not found.

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.

### 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.