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?

- glebstepanov1992 June 03, 2014 | Flag Reply
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
  {
    //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;

}

- Satveer Singh June 03, 2014 | Flag Reply
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);
}

- kbkunalb June 04, 2014 | Flag Reply
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

- tosha9 June 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- tosha9 June 05, 2014 | Flag
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; }
}

- jiangok2006 June 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

breadth first search

- metoo June 03, 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