Spotify Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
//Given a binary tree, write a method to determine shortest distance between
//two two nodes.
//The node does not have a pointer to its parent
#include<iostream>
#include<vector>
#include<algorithm>
#include<deque>
#include<stack>
using namespace std;
struct Node
{
int data;
Node *left;
Node *right;
public:
Node(int d = 0, Node * l = NULL, Node * r = NULL): data(d),left(l),right(r)
{
}
};
void Insert(Node **root, int d)
{
if(*root == NULL)
{
*root = new Node(d);
return;
}
Node* temp = *root;
if(temp->data > d)
{
Insert(&(temp->left),d);
}
else if(temp->data < d)
{
Insert(&(temp->right),d);
}
else//To allow duplicate keys do not return from here
{
//return;//Already present key
Insert(&(temp->right),d);
}
}
int Max(int i, int j)
{
return i>j?i:j;
}
int Height(Node* root)
{
if(root == NULL) return 0;
return Max(Height(root->left),Height(root->right))+1;
}
Node* lcabt(Node* root, int i, int j, bool &flag1, bool &flag2)
{
if(root == NULL)
return NULL;
Node *p1 = lcabt(root->left,i,j,flag1,flag2);
Node *p2 = lcabt(root->right,i,j,flag1,flag2);
if(p1 != NULL && p2 != NULL)
{
return root;
}
//Do not place these checkers before recursion
if(root->data == i)
{
flag1 = true;
return root;
}
if(root->data == j)
{
flag2 = true;
return root;
}
return p1==NULL ? p2 : p1;
}
int PathDistance(Node* root, int i)
{
if(root == NULL)
return 0;
if(root->data == i)
return 1;
int x = PathDistance(root->left,i);
int y = PathDistance(root->right,i);
if(x > 0 || y > 0)
{
return (Max(x,y)+1);
}
return 0;
}
int Distance(Node* root, int i, int j)
{
if(root == NULL) return 0;
if(i == j) return 0;
bool flag1 = false;
bool flag2 = false;
Node* p = lcabt(root,i,j,flag1, flag2);
if(flag1 == false || flag2 == false || p == NULL)
{
return 0;
}
return (PathDistance(p,i) + PathDistance(p,j) - 2);
}
int main()
{
Node *root1 = NULL;
Insert(&root1,12);
Insert(&root1,18);
Insert(&root1,7);
Insert(&root1,9);
Insert(&root1,11);
Insert(&root1,13);
Insert(&root1,17);
Insert(&root1,19);
Insert(&root1,21);
Insert(&root1,23);
cout<<9<<" "<<13<<" "<<Distance(root1,9,21)<<endl;
cout<<13<<" "<<23<<" "<<Distance(root1,13,23)<<endl;
}
/* Create binary tree and find the shortest path between 2 nodes */
#include<stdio.h>
int tot=0;
int sp=0;
int count=0;
struct btree
{
int data;
struct btree * left;
struct btree * right;
};
int insert(struct btree ** parent,int nodedata)
{
int i=0;
struct btree * temp;
printf("\n Inside INSERT \n");
if((*parent)==NULL)
{
printf("\n Populating node for <%d> data \n",nodedata);
temp=(struct btree *)malloc(sizeof(struct btree));
temp->data=nodedata;
temp->right=NULL;
temp->left=NULL;
(*parent)=temp;
tot++;
}
else
{
if((*parent)->data > nodedata)
{
printf("\n Insert to the left of <%d> \n",(*parent)->data);
insert(&((*parent)->left),nodedata);
}
else if((*parent)->data < nodedata)
{
printf("\n Insert to the right of <%d> \n",(*parent)->data);
insert(&((*parent)->right),nodedata);
}
else
{
printf("\n return \n");
return 0;
}
}
}
int find_path(struct btree **parent,int node,int path[])
{
printf("\n Inside find_path for node <%d> at node <%d> \n",node,(*parent)->data);
if((*parent)==NULL)
{
printf("\n Binary tree is empty or node doesnt exist \n");
return 0;
}
else
{
if(((*parent)->data > node))
{
path[count++]=(*parent)->data;
find_path(&((*parent)->left),node,path);
}
else if(((*parent)->data < node))
{
path[count++]=(*parent)->data;
find_path(&((*parent)->right),node,path);
}
else
{
printf("\n Row found \n");
path[count++]=(*parent)->data;
return(count);
}
}
}
void main()
{
int s,i=1,j=0,node1,node2,count1,count2;
int path1[10],path2[10];
struct btree * parent=NULL,*temp2;
printf("\n Inside MAIN \n");
temp2=(struct btree * ) malloc(sizeof(struct btree));
printf("\n Data to be inserted is \n");
scanf("%d",&j);
temp2->data=j;
temp2->right=NULL;
temp2->right=NULL;
parent=temp2;
printf("insert another node \n 1 YES \n 2 NO \n");
scanf("%d",&i);
while(i==1)
{
printf("Insert node \n");
printf("\n Data to be inserted is \n");
scanf("%d",&j);
insert(&parent,j);
printf("insert another node \n 1 YES \n 2 NO \n");
scanf("%d",&i);
}
printf("\n find the distance between 2 nodes \n");
printf("\n NODE 1 :\n");
scanf("%d",&node1);
printf("\n NODE 2 :\n");
scanf("%d",&node2);
count=0;
count1=find_path(&parent,node1,path1);
count1=count;
printf("\n count1 is <%d> \n",count1);
for(i=0;i<count1;i++)
{
printf("path1[%d] is <%d> \n",i,path1[i]);
}
count=0;
count2=find_path(&parent,node2,path2);
printf("\n count is <%d> \n",count);
count2=count;
for(i=0;i<count2;i++)
{
printf("path2[%d] is <%d> \n",i,path2[i]);
}
if(count1<count2)
count=count1;
else
count=count2;
s=0;
for(i=0;i<count;i++)
{
if(path1[i]==path2[i])
{
s=s+2;
}
else
break;
}
printf("s is %d \n",s);
s=count1+count2-s;
printf("\n shortest path is <%d> \n",s);
}
I basically compared data given in tree with depth from root and found the difference between them.
Calling code
int data1 = 2; //example
int data2= 5; //example
int depth = TreeNode.distanceBetweenNodes(data1, data2, root);
if(depth > 0 )
{
System.out.println("Distance between data "+data1 +" and "+data2+" is "+depth);
}
else
{
System.out.println("Data1 = "+ data1 + " or Data2 "+data2+" not in tree");
}
My tree structure looks like following
public class TreeNode
{
private int data;
private TreeNode leftchild;
private TreeNode rightchild;
public TreeNode(int data)
{
this.data = data;
leftchild = null;
rightchild = null;
}
public static TreeNode insert(int value, TreeNode node)
{
if(node==null)
{
//System.out.println("Assign value "+value);
node = new TreeNode(value);
// return node;
}
else
{
//System.out.println("Comparing data value with "+node.data +" and "+value);
if(node.data >= value)
{
// System.out.println("moving left");
node.setLeftchild(insert(value,node.getLeftchild()));
}
else
{
// System.out.println("moving right");
node.setRightchild(insert(value,node.getRightchild()));
}
}
return node;
}
public static int distanceBetweenNodes(int data1, int data2, TreeNode root)
{
int distance1 = distanceFromRoot(data1, root);
int distance2 = distanceFromRoot(data2, root);
System.out.println("Distance from root is "+ distance1 );
System.out.println("Distance from root is "+ distance2);
if((distance1 < 0) || (distance2 < 0))
{
System.err.println("The distance is "+distance1);
return -1;
}
else
{
return Math.abs(distanceFromRoot(data1, root) - distanceFromRoot(data2, root));
}
}
public static int distanceFromRoot(int value ,TreeNode node)
{
if(node == null)
{
return -100;
}
else if (node.getData() == value)
{
return 1;
}
return Math.max((1+distanceFromRoot(value, node.getLeftchild())), (1+distanceFromRoot(value, node.getRightchild())));
}
The node structure follows:
public class TreeNode
{
private int data;
private TreeNode leftchild;
private TreeNode rightchild;
public TreeNode(int data)
{
this.data = data;
leftchild = null;
rightchild = null;
} //end of constructor
public static int distanceBetweenNodes(int data1, int data2, TreeNode root)
{
int distance1 = distanceFromRoot(data1, root);
int distance2 = distanceFromRoot(data2, root);
System.out.println("Distance from root is "+ distance1 );
System.out.println("Distance from root is "+ distance2);
if( (distance1 != 0) && (distance2 != 0))
{
return -1;
}
else
{
return Math.abs(distanceFromRoot(data1, root) - distanceFromRoot(data2, root));
}
}//end of function
public static int distanceFromRoot(int value ,TreeNode node)
{
if(node == null)
{
return 0;
}
else if (node.getData() == value)
{
return 1;
}
return Math.max((1+distanceFromRoot(value, node.getLeftchild())), (1+distanceFromRoot(value, node.getRightchild())));
} //end of function
}//end of class
// C#
int mainfunc(Node r, Node t1, Node t2)
{
// sum is the minimum distance
// dt1 is the distance from r to t1
// dt2 is the distance from r to t2
int sum=0, dt1, dt2;
sum=dt1=dt2=0;
f(r, t1, t2, ref sum, ref dt1, ref dt2);
return sum;
}
void f(Node r, Node t1, Node t2, ref int sum, ref int dt1, ref int dt2)
{
if(r==null || sum>0) return;
if(dt1>0)
{
if(r==t2) { dt2=1; return;}
f(r.left, t1, t2, ref sum, ref dt1, ref dt2);
if(dt2>0) { dt2++; return;}
f(r.right, t1, t2, ref sum, ref dt1, ref dt2);
if(dt2>0) { dt2++; return; }
}
if(dt2>0)
{
if(r==t1) { dt1=1; return;}
f(r.left, t1, t2, ref sum, ref dt1, ref dt2);
if(dt1>0) { dt1++; return;}
f(r.right, t1, t2, ref sum, ref dt1, ref dt2);
if(dt1>0) { dt1++; return;}
}
if(r==t1)
{
f(r.left, t1, t2, ref sum, ref dt1, ref dt2);
if(dt2>0) { sum=dt2; return;}
f(r.right, t1, t2, ref sum, ref dt1, ref dt2);
if(dt2>0) { sum=dt2; return;}
dt1=1; return;
}
if(r==t2)
{
f(r.left, t1, t2, ref sum, ref dt1, ref dt2);
if(dt1>0) { sum=dt1; return;}
f(r.right, t1, t2, ref sum, ref dt1, ref dt2);
if(dt1>0) { sum=dt1; return;}
dt2=1; return;
}
f(r.right, t1, t2, ref sum, ref dt1, ref dt2);
if(sum>0) return;
if(dt1>0 && dt2>0) { sum=dt1+dt2-1; return;}
if(dt1>0) { dt1++; return; }
if(dt2>0) { dt2++; return; }
}
LCA problem?
- glebstepanov1992 June 03, 2014