Amazon Interview Question for Developer Program Engineers


Team: Alexa
Country: canada




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

Constructing a binary tree with just preorder traversal is not possible unless the binary tree is BST.

- anuragplus1 April 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2*Dist(root, lca)
'n1' and 'n2' are the two given keys
'root' is root of given Binary Tree.
'lca' is lowest common ancestor of n1 and n2
Dist(n1, n2) is the distance between n1 and n2.

- Anonymous April 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

/* 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;
}

- rhenobudiasa April 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is tree BST ?

- EPavlova April 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think all assume that it is BST

- EPavlova April 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- EsmailDini May 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Azeezah May 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

t8SinX ideone

- raghu.aok May 19, 2016 | 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