Amazon Interview Question for Dev Leads Dev Leads


Team: Software development engineer II
Country: United States
Interview Type: Phone Interview




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

The question is not clear at all. Can you explain in clear English.

- random September 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have rephrased the question as requested with a eg to make it clear

- argho.chatterjee.001 September 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about using an ArrayList instead of a stack? That way you can find the appropriate parent desired. Then track results with a HashSet.

public static TreeNode[] getNParent(TreeNode node, int generation){
  //bad inputs
  if(node == null){
    return null;
  }
  if(generation < 1){
    throw new IllegalArgumentException();
  }
  //tracking values
  ArrayList<TreeNode> results= new ArrayList<TreeNode>();
  getNParent(node, results, generation);
  return results.toArray(new int[results.size()]);
}

private static int getNParent(TreeNode node, ArrayList<TreeNode> results, int generation){
  int left = 0;
  if(node.left != null){
    left = getNParent(node.left, results, generation);
  }
  int right = 0;
  if(node.right != null){
    right = getNParent(node.right, results, generation);
  }
  if(left == generation || right == generation){
    results.add(node);
  }

  return (left > right)? left+1 : right+1;
}

- zortlord October 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void PrintTreeAndLastNodes(Tree root, int n)
        {
            Stack<Tree> stack = new Stack<Tree>();
            int count = 0;
            while (true)
            {
                // while a tree 
                while (root != null)
                {
                    stack.Push(root);
                    root = root.Left;
                }
                if (stack.Count == 0)
                    break;
                if (stack.Count > 0)
                {
                    root = stack.Pop();
                    if (root.Right == null && root.Left == null)
                    {
                        //This is a Lead Node we need to capure 

                    }
                    else
                    {
                        count++;
                        if (count == n)
                        {
                            count = 0;
                            Console.WriteLine(root.data);
                        }
                    }

                    root = root.Right;
                }
            }

}

- Jayhack January 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

depth of node = max( depth of node->lChild , depth of node-> rChild) +1
when it is equal to n then print value. base algo can be
int Tree::TreeDepth(treePtr root)
{
if(!root)
return 0;
else
{
int lDepth=TreeDepth(root->lChild);
int rDepth=TreeDepth(root->rChild);
int currDepth;
if(lDepth>rDepth)
currDepth = lDepth+1;
else
currDepth = rDepth+1;
if(currDepth==N)
cout <<root->value<<endl;
return currDepth;
}
}

- hjain1011 September 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

BFS is the right choice because you want to get all nodes in same level. DFS goes to deep first, not the nodes in the same level. And you should use a queue.

Below code while making BFS, when reached to the specified level, breaks from the loop.
So we have only the specified level in the queue. We print them.

I used classical node and some aux variable to keep track of current level. But may be putting level info to Node class can be more readable choice. But this time for every node we have to add an integer to every node.

private static void findLengthTree(Node root,int printLevel ) {
	    int currentLevel = 0;
	    String levelStart = "";
	    Node currentNode = null;
	    LinkedList<Node> child = new LinkedList<>();
	    
	    child.add(root);
	    levelStart = root.data;
	    while(!child.isEmpty()) {
	        currentNode = child.peek();
	        
	        if(levelStart == "" || currentNode.data == levelStart) {
	             if(currentLevel == printLevel) 
	                break;
	            
	            if(currentNode.left !=null) {
    	            levelStart= currentNode.left.data;
    	            currentLevel++;
	            }
    	        else if(currentNode.right != null) {
    	             levelStart= currentNode.right.data;
    	             currentLevel++;
    	        }
    	        else levelStart = "";
	        }
	        
	        child.poll();
	        if(currentNode.left !=null)
	            child.add(currentNode.left);
	        if(currentNode.right != null)
	            child.add(currentNode.right);
	        
	    }
	    
	    System.out.println("Data in level:" + printLevel);
	    while(!child.isEmpty()) {
	        System.out.println(child.poll().data);
	    }
	}

- Turquoise September 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It says going from leaf node up to a certain level, not from the root down to the certain level. If you use BFS, you won't know which level it is above the leaf node.

- ravio September 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what you suggested is only for balanced tree, the tree in question is unbalanced b-tree

for balanced tree it is very simple

h=height of tree
if(n==2){
BFS and print all elements in level (h-n) level
}

- argho.chatterjee.001 September 24, 2014 | Flag


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