## Spotify Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

LCA problem?

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

//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
{
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;

}

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

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

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

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

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

I am assuming m depth of tree can not be more than 99.

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

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

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

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.