Spotify Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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");
}
}}
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);
}
}
#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
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);
}
}
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;
};
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();
}
}
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)
}
}
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)
}
}
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);
}
}
First find the LCA(Lowest common ancestor) of two given nodes and then find the distance
- akshay June 03, 2014