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

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

}}

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

I would love to have some input on my code.

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

}``````

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

The above code has bug. Please ignore it.

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

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

}``````

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

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

``````import java.util.Queue;
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();
}
}``````

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 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.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);
}

}``````

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.