Amazon Interview Question for Software Engineer Interns


Country: United States
Interview Type: Phone Interview




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

/* In Order Traversal Using Recursion */
	private static void inOrderTraversalUsingRecrusion(BinaryTreeNode root) {
		if (root != null) {
			inOrderTraversalUsingRecrusion(root.getLeft());
			System.out.println(root.getData());
			inOrderTraversalUsingRecrusion(root.getRight());
		}
	}

- Vir Pratap Uttam May 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
9
of 11 vote

private static void inOrderTraversal(BinaryTreeNode root) {
		// TODO Auto-generated method stub
		Stack<BinaryTreeNode> s = new Stack<BinaryTreeNode>();
		while (true) {
			while (root != null) {
				s.push(root);
				root = root.getLeft();
			}
			if (s.isEmpty())
				return;

			root = (BinaryTreeNode) s.pop();
			System.out.println(root.getData());
			root = root.getRight();
		}

	}

- Vir Pratap Uttam May 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

/* Iterative method using stack */
Inordertraversal(struct btree *root)			
{
	while(1)
	{			
		while( root )
		{
			push(root);
			root = root->left;
		}
		if(Isstackempty(S))
			return;
		printf( S(top)->data);
		root = pop(S);
		root = root->right;
	}
}

- Sekhar Pedamallu February 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void inorder(Node n){
	if(n.left != null){
		inorder(n.left);
	}
	System.out.printlin(n.value);
	if(n.right != null){
		inorder(n.right);
	}
}

- mahdi.oraei February 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is a way to change a recursive method to a non-recursive method by stack!

Not considering that, I suggest this:

Node n = extractMin(root);
	while(n != null){
		System.out.println(n.value);
		n = successor(n);
	}

If you need to know how extractMin() and successor() works, let me know.

- mahdi.oraei February 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In a BST without any augmentation nor parent pointers, wouldn't this be O(n*h) time and O(h) space [implicity recursion stack] algorithm?

Once you get the min, you lose the information on the ancestors of the path to this min unless you have some sort of stack, right? Unless you have parent pointers that is.

Correct me if I'm wrong as I am not sure how you are going to implement the subroutines.

- S O U N D W A V E February 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Or are you missing parts ? Like creating links to remember state of paths.
There are tricky ways to do this, but you need some way to remember "state" of ancestors.

- S O U N D W A V E February 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@mahdi.oraei - Could you give a solution without using recursion?

- jas February 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public void iterativeInorder(Tree root) {
        Stack<Tree> stack = new Stack<Tree>();
        while (root != null || !(stack.isEmpty())) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                System.out.print(root.value + "->");
                root = root.right;
            }
        }
    }

- Anonymous February 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Before Algorithm I Should Say Something Here In This Recursion Stack Is Maintained By The Compiler It Intern Take care Of All The Things.Recursion Makes Coder To Do But MAke The Computer To Do More

Algorithm:
#include<stdio.h>
struct tree
{
int data;
struct tree *left;
struct tree *right;
}
main()
{
struct tree *tree1=newnode(1);
tree1->left=newnode(2);
tree1->right=newnode(3);
tree1->left->left=newnode(4);
tree1->left->right=newnode(5);
}
void inorder(struct tree *tree1)
{
if(tree1==NULL)
{
return;
}
inorder(tree1->left);
printf(" %d",tree1->data);
inorder(tree1->right);
}
struct tree *newnode(int data)
{
struct tree *tree1;
tree1=(struct tree *)malloc(sizeof(struct tree);
tree1->left=NULL;
tree1->right=NULL;
return tree1;
}

- Uda Anil Kumar March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void InOrder(Node root)
{
  if(root != NULL)
   {
       InOrder(root.left);
       System.out.println(root.data);
      InOrder(root.right);
  }

- Danish Shaikh (danishshaikh556@gmail.com) March 16, 2014 | 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