Amazon Interview Question
Developer Program EngineersTeam: Alexa
Country: canada
/* Not the best solution */
#include <iostream>
#include <queue>
using namespace std;
class node{
public :
int data;
node* left;
node* right;
node(int data, node* left, node* right){
this->data = data;
this->left = left;
this->right = right;
}
};
node* insert(int x, node* root){
if(root == NULL){
root = new node(x, NULL, NULL);
}else if(root->data > x ){
root->left = insert(x, root->left);
}else if(root->data < x){
root->right = insert(x, root->right);
}
return root;
}
int distance_node(int x, node* root, int index){
if(root->data == x){
return index;
}else if(root->data > x){
return distance_node(x, root->left, index-1);
}else if(root->data < x){
return distance_node(x, root->right, index+1);
}
return 0;
}
int main(){
node* root = NULL;
root = insert(7, root);
root = insert(3, root);
root = insert(1, root);
root = insert(2, root);
root = insert(8, root);
root = insert(9, root);
int distance = abs(distance_node(1, root, 0) - distance_node(8, root, 0));
cout<<distance<<endl;
return 0;
}
Yes, it's a BST. Here is my probably inelegant solution:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Amazaon_Test
{
class Solution
{
static void Main(string[] args)
{
int fVal = Int32.Parse(Console.ReadLine()); // Node A
int sVal = Int32.Parse(Console.ReadLine()); // Node B (We need to get the distance between the two)
int count = Int32.Parse(Console.ReadLine()); // # of nodes in the tree
string[] nodesStr = Console.ReadLine().Split(' '); // All nodes in one line
List<int> nodes = new List<int>();
for (int i = 0; i < count; i++)
nodes.Add(Int32.Parse(nodesStr[i]));
BinaryTree bTree = new BinaryTree(nodes, fVal, sVal);
bTree.PrintPreOrder();
Console.ReadKey();
}
}
class BinaryTree
{
public List<int> Nodes;
Node root;
int count;
public BinaryTree(List<int> nodes, int v1, int v2)
{
//count = nodes.Count;
count = 0;
Nodes = nodes;
root = new Node();
root.Value = nodes[0];
root.Left = ContructTree(nodes, Int16.MinValue, nodes[0], root);
root.Right = ContructTree(nodes, nodes[0], Int16.MaxValue, root);
PrintDistance(v1, v2);
}
public Node ContructTree(List<int> nodes, int r1, int r2, Node parent)
{
count++;
if (count >= nodes.Count)
{
count--;
return null;
}
Node n = new Node();
n.Value = nodes[count];
if (r1 <= n.Value && r2 >= n.Value)
{
n.Left = ContructTree(nodes, r1, n.Value, n);
n.Right = ContructTree(nodes, n.Value, r2, n);
}
else
{
count--;
return null;
}
n.Parent = parent;
return n;
}
public void PrintPreOrder()
{
Console.Write(root.Value + " ");
PrintNode(root.Left);
PrintNode(root.Right);
}
public void PrintNode(Node n)
{
if (n != null)
{
Console.Write(n.Value + " ");
}
else
return;
if (n.Left != null)
PrintNode(n.Left);
if (n.Right != null)
PrintNode(n.Right);
}
public int GetHeight(int v1, Node n, int height)
{
if (v1 == n.Value)
return height;
if (n.Left == null && n.Right == null)
return -1;
else if (v1 <= n.Value)
return GetHeight(v1, n.Left, height + 1);
else
return GetHeight(v1, n.Right, height + 1);
}
public void PrintDistance(int v1, int v2)
{
Node p = FindCommonParent(v1, v2);
int h1 = GetHeight(v1, p, 0);
int h2 = GetHeight(v2, p, 0);
Console.WriteLine(h1 + h2);
}
public Node FindCommonParent(int v1, int v2)
{
List<Node> l1 = GetAllParents(v1);
List<Node> l2 = GetAllParents(v2);
List<Node> intersectNodes = l1.Intersect(l2).ToList();
Node imidiateParent = intersectNodes.ElementAt(0);
if (imidiateParent == null)
return null;
else
return imidiateParent;
}
public List<Node> GetAllParents(int n)
{
List<Node> nodes = new List<Node>();
Node node = FindNode(n, root);
if (node != null)
{
Node p = node.Parent;
while (p != null)
{
nodes.Add(p);
p = p.Parent;
}
}
return nodes;
}
public Node FindNode(int n, Node node)
{
if (node.Value == n)
return node;
else if (n <= node.Value)
return FindNode(n, node.Left);
else
return FindNode(n, node.Right);
}
}
class Node
{
public int Value;
public Node Parent;
public Node Left;
public Node Right;
}
}
class Node:
__init__(self, n):
self.value = n
self.right = None
self.left = None
def insert(head, new):
if new.value <= head.value:
if head.right:
insert(head.right, new)
else:
head.right = new
else:
if head.left:
insert(head.left)
else:
head.left = new
def makeTree(array):
head=Node(array[0])
for value in array[1::]:
insert(head, Node(value))
def distHead(head, node):
distance=0
currentNode=head
while(currentNode.value!=node.value):
if currentNode.value > node.value:
currentNode = currentNode.left
elif currentNode.value < node.value:
currentNode = currentNode.right
distance+=1
return distance
def distance(head, node1, node2):
return abs(distHead(head, node1) - distHead(head, node2))
Constructing a binary tree with just preorder traversal is not possible unless the binary tree is BST.
- anuragplus1 April 28, 2016