Amazon Interview Question for Interns


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
2
of 6 vote

This is a question straight out of cracking the coding Interview..

- Ankush February 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

#include<stdio.h>
#include<stdlib.h>
struct node{
       int data;
       struct node *left;
       struct node *right;
};
struct node * newNode(int data){
       struct node * root = (struct node *)malloc(sizeof(struct node));
       root->data = data;
       root->left = NULL;
       root->right = NULL;
       return root;
}
int findPath(struct node *root, int value,int * a,int i){
    
     if(root==NULL){
               return 0;
     }
     if(root->data == value || findPath(root->left,value,a,i+1)||findPath(root->right,value,a,i+1)){
                   a[i] = root->data;
                   return i;
     }
     return 0;
}
int findAncestor(int a[],int b[],int i,int prev){
    if(a[i] == b[i]){
        prev = findAncestor(a,b,i+1,a[i]);    
        return prev;
    }
    else{
         return prev;
    }
}
int main(){
    struct node * root;
    int i =0,index1=0,index2=0;
    int path1[100];
    int path2[100];
    memset(path1,-1,sizeof(path1));
    memset(path1,-1,sizeof(path2));
    root= newNode(17);
    root->left = newNode(12);
    root->right = newNode(13);
    root->right->left = newNode(9);
    root->right->left->left = newNode(5);
    root->right->left->left->left = newNode(1);
    root->right->right = newNode(3);
    root->right->right->right = newNode(2);
    root->right->right->right->right = newNode(8);
    index1= findPath(root,1,path1,0);
    index2= findPath(root,8,path2,0);
    printf("%d",findAncestor(path1,path2,0,-1));
    getch();
}

- Amit February 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is the complexity of this code?

- xxx February 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Worst case complexity should be linear in terms of number of elements in the binary tree.

- Second Attempt March 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

FindPath of both the nodes from root.
then search for the last common nodes in both the path, that will be the LCA in a tree.

- sjain February 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

1. Do an inorder and post order traversal
2. find position of both elements in inorder array and note the range.
3. now find rank of all elements from this range in post order array.
4. last ranked element in post order is lowest common ancestor.
an O(N) solution wrt time complexity.

- Anshul February 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not O(n)....since you will be running two nested loops...outside inorder range, and inside postorder

- Gupt March 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Define your terms a little bit more I looked on wikipedia for Binary tree and I see the Distinction from the common BST but it does not mention a lowest common ancestor

- Mathcomp February 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How about "finding the node with largest depth such that it is the root of a subtree that contains both of the specified nodes"?

- Chih.Chiu.19 February 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I would say the answer lies in bubbling up from both nodes simaltaneously checking each step to see if they have reached there common ancestor

- Mathcomp February 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

in dt case! the nodes cud be at diff heights! so i don think bubbling up wud be a good idea!

- xxx February 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

One case would be traversing from ech of the two nodes till the root and comparing on common terms. All the common terms could be the common parents, provided they are in a sequence.
Now sort this list of common parents to get the lowest.

- tuxnani February 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

h**p://stackoverflow.com/questions/1484473/how-can-i-find-the-common-ancestor-of-two-nodes-in-a-binary-tree

- sexy boi February 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assumptions:
I'm printing the common ancestor.
II'm given a TreeNode structure that has a left and right pointer.
data is an int
a is 1000
b is 1

int common( TreeNode* root, int a, int b ){
	if ( root == null ) return 0;
	int leftCount = common(root->left, a, b);
	int rightCount = common(root->right, a,b);
	int mine;

	// can't be both, right?
	mine = ( root->data == a )? 1000: 0;
	mine = ( root->data == b )? 1: 0;
	
	// found already deeper in the tree
	if ( leftCount == 1001 || rightCount == 1001) return 1001;
	
	// nothing in my children, return my count
	if ( leftCount == rightCount == 0 )  return mine;

	// if we are here, the checks above arent true
	// so check if we found something
	if ( (leftCount + rightCount  == 1001)  
		|| (mine + leftCount + rightCount == 1001) ){
		// print
		 std::cout << "Here: " << root->data << std::endl;
		// found	
		return 1001;
	}


        // left and right children doesnt have a AND b, so we're here
        // possible they have either one though, 
        
        // mine isn't a or b so return children count
	if ( mine == 0 && (leftCount != rightCount) ) 
               return leftCount+rightCount ;
        // both children had the same node data ( both a or  both b) 	
	else if( mine == 0 && leftCount == rightCount ) return leftCount;
        // if I have same data as one of my children
        // just return their count
	else if ( mine == leftCount ) return leftCount ;
	else if( mine == rightCount ) return rightCount ;

        return mine;
}

- bunnybare February 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class TreeNode {
    int val;
    TreeNode leftchild;
    TreeNode rightchild;
}

public class Solution {
    public static TreeNode findCommonAncestor(TreeNode root, TreeNode a, TreeNode b) {
	if (root == null || a == null || b == null) {
	    return null;
	}
	TreeNode ret = null;
	traverse(root, a, b, ret);
	return ret;
    }

    public static int traverse(TreeNode root, TreeNode a, TreeNode b, TreeNode ret) {
	if (root == null) {
	    return 0;
	}
	if (root == a || root == b) {
	    return 1;
	}
	int value = traverse(root.leftchild, a, b, ret)+traverse(root.rightchild, a, b, ret);
	if (value == 2) {
	    ret = root;
	    return 3;
	}
	else {
	    return value;
	}
    }
}

- duo.xu.1@stonybrook.edu February 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

NodeType* lowest(NodeType* root,NodeType* p,NodeType*q){
if(root==NULL)return NULL;
if(root==p||root==q)return root;
NodeType* left=lowest(root->left,p,q);
NodeType* right=lowest(root->right,p,q);
if(left!=NULL||right!=NULL)return root;
if(left!=NULL)return left;
if(right!=NULL)return right;
return NULL;
}

- stevenh47 February 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Step1: traverse postorder ex:8,2,5,25,19,21,15,17,29,20,10,40,50,30,9
Step2: traverse preorder ex:9,10,15,5,8,2,21,25,19,20,17,29,30,40,50
Step 3: if our two node 8 and 19 then in postorder the element after 19 ...21,15,17,29,20,10,40,50,30,9 and the elemnet before 8 in preorder 9,10,15,5
step 4: find the commen element in both ex. 9,10,15
Step 5: find the min in this arrey ex. from 9,10,15 is 9 so lowest commen ancester is 9.
Ex our tree is 9
10 / \30
15 / \ 20 40/ \ 50
5/ \ 21 17 / \29
8/ \2 25/ \19

- Mukesh Kumar Dhaker February 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public Node findAncestor(Node n, Node m){
		
		if(n == null || m == null) return null;
		
		Set<Node> nodeSet = new HashSet<Node>();
		
		while(n!=null || m!=null){

			if(n!=null && !nodeSet.contains(n.parent)){

				nodeSet.add(n.parent);
				
				n = n.parent;

			}else{

				return n.parent;

			}
			
			if(m!=null && !nodeSet.contains(m.parent)){
				
				nodeSet.add(m.parent);
				
				m = m.parent;
				
			}else{

				return m.parent;

			}

		}

		return null;
	}

- Anup February 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h> #include <stdlib.h> #include <malloc.h>   typedef struct treeNode* treeNodePtr; struct treeNode{         int data;         treeNodePtr left;         treeNodePtr right; };   treeNodePtr findLCA(treeNodePtr root, int p, int q) {           // no root no LCA.         if(!root) {                 return NULL;         }             // if either p or q are direct child of root then root is LCA.         if(root->data==p || root->data==q) {                 return root;         } else {                 // get LCA of p and q in left subtree.                 treeNodePtr l=findLCA(root->left , p , q);                   // get LCA of p and q in right subtree.                 treeNodePtr r=findLCA(root->right , p, q);                   // if one of p or q is in leftsubtree and other is in right                 // then root it the LCA.                 if(l && r) {                         return root;                 }                 // else if l is not null, l is LCA.                 else if(l) {                         return l;                 } else {                         return r;                 }         } }   treeNodePtr newNode(int data) {         treeNodePtr newNode = malloc(sizeof(struct treeNode));         if(!newNode) {                 fprintf(stderr,"Error allocating memory\n");                 exit(1);         }         newNode->data = data;         newNode->left = NULL;         newNode->right = NULL;           return newNode; }   int main() {   /*                  5                 / \                7   6               /\   /\              1  2 3  4             /\            0  8 */           treeNodePtr root = newNode(5);         treeNodePtr tmp;         root->left = newNode(7);         root->right = newNode(6);         root->left->left = newNode(1);         root->left->right = newNode(2);         root->right->left = newNode(3);         root->right->right = newNode(4);         root->left->left->left = newNode(0);         root->left->left->right = newNode(8);           int arr[] = {0,1,2,3,4,5,6,7,8};         int size = sizeof(arr)/sizeof(*arr);         int i,j;           for(i=0;i<size;i++) {                 for(j=i+1;j<size;j++) {                         tmp = findLCA(root,arr[i],arr[j]);                         printf("LCA of %d %d is %d\n",arr[i],arr[j],tmp->data);                 }         }           return 0; }

- helper March 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h> #include <stdlib.h> #include <malloc.h> typedef struct treeNode* treeNodePtr; struct treeNode{ int data; treeNodePtr left; treeNodePtr right; }; treeNodePtr findLCA(treeNodePtr root, int p, int q) { // no root no LCA. if(!root) { return NULL; } // if either p or q are direct child of root then root is LCA. if(root->data==p || root->data==q) { return root; } else { // get LCA of p and q in left subtree. treeNodePtr l=findLCA(root->left , p , q); // get LCA of p and q in right subtree. treeNodePtr r=findLCA(root->right , p, q); // if one of p or q is in leftsubtree and other is in right // then root it the LCA. if(l && r) { return root; } // else if l is not null, l is LCA. else if(l) { return l; } else { return r; } } } treeNodePtr newNode(int data) { treeNodePtr newNode = malloc(sizeof(struct treeNode)); if(!newNode) { fprintf(stderr,"Error allocating memory\n"); exit(1); } newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode; } int main() { /* 5 / \ 7 6 /\ /\ 1 2 3 4 /\ 0 8 */ treeNodePtr root = newNode(5); treeNodePtr tmp; root->left = newNode(7); root->right = newNode(6); root->left->left = newNode(1); root->left->right = newNode(2); root->right->left = newNode(3); root->right->right = newNode(4); root->left->left->left = newNode(0); root->left->left->right = newNode(8); int arr[] = {0,1,2,3,4,5,6,7,8}; int size = sizeof(arr)/sizeof(*arr); int i,j; for(i=0;i<size;i++) { for(j=i+1;j<size;j++) { tmp = findLCA(root,arr[i],arr[j]); printf("LCA of %d %d is %d\n",arr[i],arr[j],tmp->data); } } return 0; }

- helper March 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool lca(const T &a, const T &b, T &result, std::function<int(const T &, const T &)> compare) {
      Node *popNode;
      Stack<Node *> stack;

      std::vector<const T *> elements = { &a, &b };

      std::function<bool(Node *)> findNode;
      findNode = [&](Node *node) -> bool {
        if (!node)
          return false;

        if (elements.size() == 2)
          stack.push(node);

        auto it = elements.begin();
        while (it != elements.end()) {
          if (compare(node->m_data, *(*it)) == 0) {
            elements.erase(it);
     
            stack.pop(popNode);
            if (popNode != node)
              stack.push(popNode);

            return true;
          }
          else
            ++it;
        }

        if (findNode(node->m_left) && elements.empty())
          return true;

        if (findNode(node->m_right) && elements.empty())
          return true;

        stack.pop(popNode);
        if (popNode != node)
          stack.push(popNode);

        return false;
      };

      struct Node *node;
      if (findNode(m_root) && stack.pop(node)) {
        result = node->m_data;

        return true;
      }

      return false; 
    }

- Anonymous March 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

[1] Traverse tree using BFS. Stop as you notice that both given nodes have been seen.
[2] Meanwhile use Hashtable to keep track of parent of each node.
[3] Create path from each node to root using hashtable.
[4] the first common node between paths of each node is the answer.

- Anonymous April 02, 2013 | 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