Spotify Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

First find the LCA(Lowest common ancestor) of two given nodes and then find the distance

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

I handled this probable as comparing distance from data1 and data2

Here is my Code:

{{

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


}


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

}
}

//Calling function

int data1 = 2;
int data2= 5;

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

}}

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

I would love to have some input on my code.

- tosha June 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FindShortestDistanceBetweenTwoNodes 
{
	static class Node
	{
		int data;
		Node left;
		Node right;
		
		public Node(int data)
		{
			this.data = data;
		}
	}
	
	public int findShortestDistance(Node root, int key1, int key2)
	{
		if (root == null)
			return 0;
		int lDistance = recursiveGetDistance(root.left, key1, key2);
		int rDistance = recursiveGetDistance(root.right, key1, key2);
		if (lDistance > 0 && rDistance ==0)
		{
			return findShortestDistance(root.left, key1, key2);
		}
		else if (lDistance == 0 && rDistance > 0)
		{
			return findShortestDistance(root.left, key1, key2);
		}
		else
		{
			return rDistance+lDistance+1;
		}
	}
	
	
	private int recursiveGetDistance(Node root, int key1, int key2)
	{
		if (root == null)
			return 0;
	    if (root.data == key1 || root.data == key2)
	    {
	    	return 1;
	    }
		
	    int lDistance = recursiveGetDistance(root.left, key1, key2);
	    int rDistance = recursiveGetDistance(root.left, key1, key2);
	    if (lDistance == 0 && rDistance == 0)
	    {
	    	return 0;
	    }
	    else
	    {
	    	return lDistance + rDistance;
	    }
	    
	    
	}


	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Node root = new Node(1);
		root.left = new Node(2);
		root.left.left  = new Node(4);
		root.left.right = new Node(5);
		
		root.right = new Node(3);
		root.right.right = new Node(7);
		root.right.right.right = new Node(8);
		root.right.left = new Node(6);
		
		int result = new FindShortestDistanceBetweenTwoNodes().
		                 findShortestDistance(root, 4, 5);
		System.out.println(result);
	}

}

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

The above code has bug. Please ignore it.

- Suman June 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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 -1;
    }
    return (PathDistance(p,i) + PathDistance(p,j) - 2);
}

//==============================Suman Code for Testing======================
int recursiveGetDistance(Node *root, int key1, int key2)
{
	if (root == NULL)
        {
	   return 0;
        }
 
	if (root->data == key1 || root->data == key2)
	{
	   return 1;
	}
		
	int lDistance = recursiveGetDistance(root->left, key1, key2);
	int rDistance = recursiveGetDistance(root->right, key1, key2);
	if (lDistance == 0 && rDistance == 0)
	{
	    return 0;
	}
	else
	{
	    return lDistance + rDistance+1;
	}
	        
}	

int findShortestDistance(Node *root, int key1, int key2)
{
   if (root == NULL)
   {
	return 0;
   }
   int lDistance = recursiveGetDistance(root->left, key1, key2);
   int rDistance = recursiveGetDistance(root->right, key1, key2);
   if (lDistance > 0 && rDistance ==0)
   {
	return findShortestDistance(root->left, key1, key2);
   }
   else if (lDistance == 0 && rDistance > 0)
   {
        return findShortestDistance(root->right, key1, key2);
   }
   else
   {
	return rDistance+lDistance+1;
   }
}
	
//=====================================================================

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<<"Suman Logic  "<<findShortestDistance(root1,23,18)<<endl;

   cout<<"My Logic"<<Distance(root1,23,18)<<endl;

   cout<<"Suman Logic  "<<findShortestDistance(root1,11,100)<<endl;

   cout<<"My Logic"<<Distance(root1,11,100)<<endl;

  return 0;

}

Output:- 

Suman Logic  1
My Logic3
Suman Logic  1
My Logic-1

- Kavita June 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I failed to take care of some corner cases in previous code. Fixed those issues.

public class FindShortestDistanceBetweenTwoNodes 
{
	static class Node
	{
		int data;
		Node left;
		Node right;
		
		public Node(int data)
		{
			this.data = data;
		}
	}
	
	public int findShortestDistance(Node root, int key1, int key2)
	{
		if (root == null)
			return 0;
		if (root.data == key1)
		{
			int lDistance = recursiveGetDistance(root.left,  key2);
			int rDistance = recursiveGetDistance(root.right, key2);
			if (lDistance > 0)
			{
				return lDistance+1;
			}
			else if (rDistance > 0)
			{
				return rDistance+1;
			}
			else
			{
				return -1;
			}
		}
		else if (root.data == key2)
		{
			int lDistance = recursiveGetDistance(root.left,  key1);
			int rDistance = recursiveGetDistance(root.right, key1);
			if (lDistance > 0)
			{
				return lDistance+1;
			}
			else if (rDistance > 0)
			{
				return rDistance+1;
			}			
			else
			{
				return -1;
			}
		}
		else
		{
			int lDistance = recursiveGetDistance(root.left, key1, key2);
			int rDistance = recursiveGetDistance(root.right, key1, key2);
			if (lDistance > 0 && rDistance ==0)
			{
				return findShortestDistance(root.left, key1, key2);
			}
			else if (lDistance == 0 && rDistance > 0)
			{
				return findShortestDistance(root.right, key1, key2);
			}
			else if (lDistance > 0 && rDistance > 0)
			{			
				return rDistance+lDistance+1;
			}
			else
			{
				return -1;
			}
		}
	}
	
	
	private int recursiveGetDistance(Node root, int key)
	{
		if (root == null)
		   return 0;
	    if (root.data == key)
	    {
	    	return 1;
	    }
	    int lDistance = recursiveGetDistance(root.left, key);
	    int rDistance = recursiveGetDistance(root.right, key);
	    if (lDistance == 0 && rDistance == 0)
	    {
	    	return 0;
	    }
	    else
	    {
	    	return lDistance + rDistance+1;
	    }		
	}


	private int recursiveGetDistance(Node root, int key1, int key2)
	{
		if (root == null)
			return 0;
	    if (root.data == key1 || root.data == key2)
	    {
	    	return 1;
	    }
		
	    int lDistance = recursiveGetDistance(root.left, key1, key2);
	    int rDistance = recursiveGetDistance(root.right, key1, key2);
	    if (lDistance == 0 && rDistance == 0)
	    {
	    	return 0;
	    }
	    else
	    {
	    	return lDistance + rDistance+1;
	    }
	    
	    
	}

//	
//      1
//    /    \
//   2      3
//  / \    / \
// 4   5  6   7
//         \   \
//          8   9 

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Node root = new Node(1);
		root.left = new Node(2);
		root.left.left  = new Node(4);
		root.left.right = new Node(5);
		
		root.right = new Node(3);
		root.right.right = new Node(7);
		root.right.right.right = new Node(9);
		root.right.left = new Node(6);
		root.right.left.right = new Node(8);
		
		int result = new FindShortestDistanceBetweenTwoNodes().
		                 findShortestDistance(root, 2,8);
		System.out.println(result);
	}

}

- Suman June 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

BinaryTree.prototype.distanceBetweenNodes = function (p, q) {
	var lca = this.findLCA(this.root, p, q);

	if (lca === null) {
		return 0;
	}

	return this.getDistance(lca, p, 0) + this.getDistance(lca, q, 0);

BinaryTree.prototype.getDistance = function (node, data, count) {
	if (node === null) {
		return 0;
	}

	if (node.data === data) {
		return count;
	}

	return this.getDistance(node.left, data, count + 1) + this.getDistance(node.right, data, count + 1); 
};

BinaryTree.prototype.findLCA = function (node, p, q) {
	if (node === null) {
		return null;
	}

	if (node.data === p || node.data === q) {
		return node;
	}

	var leftNode = this.findLCA(node.left, p, q);
	var rightNode = this.findLCA(node.right, p, q);

	if (leftNode && rightNode) {
		return node;
	}

	return leftNode ? leftNode : rightNode;
};

- ... June 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Queue;
import java.util.LinkedList;
public class TreeTraverse
{
 private static class Node
 {
  public Node left; 
  public Node right;
  public String data;
  public Node( String data)
  {
   this.data = data;
  }
  public Node getLeft()
  {
   return this.left;
  }
  public void setLeft(Node left)
  {
   this.left = left;
  }
  public Node getRight()
  {
   return this.right;
  }
  public void setRight(Node right)
  {
   this.right = right;
  }
 }
public static int findLevel(Node n,Node a,int d){ 
	if(n== null) 
		return -1;
	else{
		if(Integer.parseInt(n.data) == Integer.parseInt(a.data))
			return d;
		else if(Integer.parseInt(n.data) < Integer.parseInt(a.data))
			return findLevel(n.left,a,d+1);
		return findLevel(n.right,a,d+1);
	}
}
public static int findLCDistance(Node root, Node a,Node b){
	Node lca = LCA(root,a,b);
	int d1 = findLevel(lca,a,0);
	int d2 = findLevel(lca,b,0);
		if(d1 !=-1 && d2 !=-1)
			return d1+d2;
		else
			return -1;
}
public static Node LCA(Node root, Node a, Node b) {
   if (root == null) {
       return null;
   }
   if (root == a || root == b) {
       return root;
   }
   Node left = LCA(root.left, a, b);
   Node right = LCA(root.right, a, b);
   if (left != null && right != null) {
      return root;
   }

   return (left != null) ? left : right; 
}
public static void main(final String[] args)
 {
  Node one = new Node("1");
  Node two = new Node("2");
  Node three = new Node("3");
  Node four = new Node("4");
  Node five = new Node("5");
  Node six = new Node("6");
  Node seven = new Node("7");
  Node eight = new Node("8");
  Node nine = new Node("9");
  six.setLeft(four);
  six.setRight(seven);
  four.setLeft(three);
  four.setRight(five);
  three.setLeft(one);
  three.setRight(two);
  seven.setLeft(eight);
  seven.setRight(nine);
  Node n = LCA(six,one,nine);
  System.out.print("\nLowest Common Ancestor \t: "+n.data+"\n");
  int d = findLCDistance(six ,one,nine);
  System.out.print("The least distance between 2 nodes is ="+d);
  System.out.println();
 }
}

- Prefect November 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import scala.annotation.tailrec

case class Tree(root: Int, left: Option[Tree], right: Option[Tree])

object Tree {
  //  def apply(root: Int, left: Option[Tree], right: Option[Tree]) = new Tree(root, left, right)
  def apply(value: Int) = new Tree(value, None, None)
  def apply(root: Int, left: Tree, right: Tree) = new Tree(root, Some(left), Some(right))
}
object NodeDistance {
  def distance(tree: Tree, node1: Int, node2: Int): Option[Int] = {
    @tailrec
    def findDistance(path1: List[Int], path2: List[Int]): Int = {
      (path1, path2) match {
        case (x::xs, y::ys) if x == y => findDistance(xs, ys) // Found common ancestor: Go in deeper first
        case (x,     y)               => x.size + y.size      // Roots reparated so parent was common ancestor. Return the sum of the sizes of the lists
      }
    }

    def findPath(tree: Tree, node: Int): Option[List[Int]] = {
      if(tree.root == node) Some(List(tree.root))
      else {
        def lazyPath(t: Option[Tree]) = t.flatMap(t => findPath(t, node)).map(p => tree.root :: p)
        lazyPath(tree.left).orElse(lazyPath(tree.right))
      }
    }

    for(
      path1 <- findPath(tree, node1);
      path2 <- findPath(tree, node2)
    ) yield findDistance(path1, path2)
  }

  def main(args: Array[String]) {
    val t = Tree(1,
      Tree(2),
      Tree(3, Tree(4), Tree(5)))
    println(distance(t, 1, 3).contains(1))
    println(distance(t, 2, 3).contains(2))
    println(distance(t, 3, 3).contains(0))
    println(distance(t, 3, 4).contains(1))
    println(distance(t, 3, 5).contains(1))
    println(distance(t, 4, 5).contains(2))
    println(distance(t, 1, 5).contains(2))
    println(distance(t, 2, 5).contains(3))
    println(distance(t, 999, 5).isEmpty)
  }
}

- akmo75 November 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import scala.annotation.tailrec

case class Tree(root: Int, left: Option[Tree], right: Option[Tree])

object Tree {
  //  def apply(root: Int, left: Option[Tree], right: Option[Tree]) = new Tree(root, left, right)
  def apply(value: Int) = new Tree(value, None, None)
  def apply(root: Int, left: Tree, right: Tree) = new Tree(root, Some(left), Some(right))
}
object NodeDistance {
  def distance(tree: Tree, node1: Int, node2: Int): Option[Int] = {
    @tailrec
    def findDistance(path1: List[Int], path2: List[Int]): Int = {
      (path1, path2) match {
        case (x::xs, y::ys) if x == y => findDistance(xs, ys) // Found common ancestor: Go in deeper first
        case (x,     y)               => x.size + y.size      // Roots reparated so parent was common ancestor. Return the sum of the sizes of the lists
      }
    }

    def findPath(tree: Tree, node: Int): Option[List[Int]] = {
      if(tree.root == node) Some(List(tree.root))
      else {
        def lazyPath(t: Option[Tree]) = t.flatMap(t => findPath(t, node)).map(p => tree.root :: p)
        lazyPath(tree.left).orElse(lazyPath(tree.right))
      }
    }

    for(
      path1 <- findPath(tree, node1);
      path2 <- findPath(tree, node2)
    ) yield findDistance(path1, path2)
  }

  def main(args: Array[String]) {
    val t = Tree(1,
      Tree(2),
      Tree(3, Tree(4), Tree(5)))
    println(distance(t, 1, 3).contains(1))
    println(distance(t, 2, 3).contains(2))
    println(distance(t, 3, 3).contains(0))
    println(distance(t, 3, 4).contains(1))
    println(distance(t, 3, 5).contains(1))
    println(distance(t, 4, 5).contains(2))
    println(distance(t, 1, 5).contains(2))
    println(distance(t, 2, 5).contains(3))
    println(distance(t, 999, 5).isEmpty)
  }
}

- akmo75 November 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Please ignore the previous code

public class FindShortestDistanceBetweenTwoNodes 
{
	static class Node
	{
		int data;
		Node left;
		Node right;
		
		public Node(int data)
		{
			this.data = data;
		}
	}
	
	public int findShortestDistance(Node root, int key1, int key2)
	{
		if (root == null)
			return 0;
		int lDistance = recursiveGetDistance(root.left, key1, key2);
		int rDistance = recursiveGetDistance(root.right, key1, key2);
		if (lDistance > 0 && rDistance ==0)
		{
			return findShortestDistance(root.left, key1, key2);
		}
		else if (lDistance == 0 && rDistance > 0)
		{
			return findShortestDistance(root.right, key1, key2);
		}
		else
		{
			return rDistance+lDistance+1;
		}
	}
	
	
	private int recursiveGetDistance(Node root, int key1, int key2)
	{
		if (root == null)
			return 0;
	    if (root.data == key1 || root.data == key2)
	    {
	    	return 1;
	    }
		
	    int lDistance = recursiveGetDistance(root.left, key1, key2);
	    int rDistance = recursiveGetDistance(root.right, key1, key2);
	    if (lDistance == 0 && rDistance == 0)
	    {
	    	return 0;
	    }
	    else
	    {
	    	return lDistance + rDistance+1;
	    }
	    
	    
	}


	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Node root = new Node(1);
		root.left = new Node(2);
		root.left.left  = new Node(4);
		root.left.right = new Node(5);
		
		root.right = new Node(3);
		root.right.right = new Node(7);
		root.right.right.right = new Node(8);
		root.right.left = new Node(6);
		
		int result = new FindShortestDistanceBetweenTwoNodes().
		                 findShortestDistance(root, 4,6);
		System.out.println(result);
	}

}

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