Amazon Interview Question for Applications Developers


Country: United States
Interview Type: In-Person




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

struct List* Result[] //array for holding LinkList at each level
int i //index for Result for each level
void LevelOrderList(struct Node * root)
{
struct Node* Temp;
if(!root)
return;
Struct Queue* Q=CreateQue();
Enque(Q,root);
Enque(Q,NULL);
while(IsQueEmty())//return 1 if not empty else 0
{
Temp=Deque();
if(Temp==NULL) //one level done so create marker for other level
{
Enqueue(Q,NULL);
i++;
}
else
{
if(Temp->left)
Enqueue(Temp->left);
if(Temp->Right)
Enqueue(Temp->Right);
CreateLinkList(Result[i],Temp->data);
}
}

Implement The Function CreateLinkList as simple LinkList Insertion Program.

- samrat August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can use breadth first search algorithm

- Anonymous August 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

BFS is kind of a iterative, in this case, I would suggest using recursive

Using recursive is much more convenient than iterative...

- Evan August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ya agreed. Even recursive will do. We can go for preorder traversal in depth first search. Moreover, both will be space efficient as both will provide O(N) complexity.

- Anonymous August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

follow the link

- https://github.com/san21886/C/blob/master/print_levelwise_bst_element.c August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<queue>
#include<algorithm>
#include<vector>


vector<vector<BTNode*> >& result level_wise_list_bst(BTNode* root) {
	if(NULL == root) return NULL;
	
	vector<vector<BTNode*> > result;
	queue<BTNode*> q;
	q.push(root);
	
	int curr_level_node_count = 1;
	int next_level_node_count = 0;
	int curr_level = 0;
	
	while(false == q.empty() )
	{
		BTNode* curr_node = q.pop();
		result[curr_level].push_back(curr_node);
		curr_level_node_count--;
		
		if(curr_node->left) {
			q.push_back(curr->left);
			next_level_node_count++;
		}
		if(curr_node->right) {
			q.push_back(curr->right);
			next_level_node_count++;
		}
		
		if( curr_level_node_count == 0 ) {
			curr_level++;
			swap(curr_level_node_count, next_level_node_count);
		}

	}
	
	return result;
}

- mr August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

struct BTNode {
  int data;
  BTNode* left;
  BTNode* right;
  BTNode():left(NULL), right(NULL){}
};

vector<vector<BTNode*> > level_wise_list_bst(struct BTNode* root) {

  vector<vector<BTNode*> > result;

  if(NULL == root) return result;
	
	queue<BTNode*> q;
	q.push(root);
	
	int curr_level_node_count = 1;
	int next_level_node_count = 0;
	int curr_level = 0;
	
	while(false == q.empty() ) {
    BTNode* curr_node = q.front();
    q.pop();
		curr_level_node_count--;

		result[curr_level].push_back(curr_node);
		
		if(curr_node->left) {
			q.push(curr_node->left);
			next_level_node_count++;
		}

    if(curr_node->right) {
			q.push(curr_node->right);
			next_level_node_count++;
		}
		
		if( curr_level_node_count == 0 ) {
			curr_level++;
			swap(curr_level_node_count, next_level_node_count);
		}

	}
	
	return result;
}

Correct Code without syntax\language error

- mr August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is the given Tree BST in the question? The Tree doesn't satisfy BST properties.
It's not clear. Plz., recheck guys before giving answers.

- Jessica August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is not a BST, i would have mentioned if it is.

- Naveen Reddy Mandadi August 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, my mistake, it is not BST, it is just a binary tree, i have mentioned it wrong in the question.

- Naveen Reddy Mandadi August 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static ArrayList<ArrayList<Integer>> createLevelArrays(BinaryTreeNode head){
if(head==null){
return null;
}
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
HashMap<BinaryTreeNode,Integer> map=new HashMap<BinaryTreeNode,Integer>();
map.put(head, 1);
Queue<BinaryTreeNode> path=new LinkedList<BinaryTreeNode>();
path.add(head);
while(!path.isEmpty()){
BinaryTreeNode current=path.poll();
int currentlevel=map.get(current);
if(result.size()<currentlevel){
result.add(new ArrayList<Integer>());
}
result.get(currentlevel-1).add(current.value);
if(current.left!=null){
map.put(current.left, currentlevel+1);
path.add(current.left);
}
if(current.right!=null){
map.put(current.right, currentlevel+1);
path.add(current.right);
}

}

return result;
}

- Chengyun Zuo August 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Iterative solution: (Recursion should be avoided cause usually it gives high time complexity)

public static ArrayList<LinkedList> convert(Node root){		
		ArrayList<LinkedList> result = new ArrayList<LinkedList>();
		ArrayList<Node> queue = new ArrayList<Node>();
		
		queue.add(root);
		
		while(!queue.isEmpty()){
			ArrayList<Node> tempQueue = new ArrayList<Node>();
			
			for(Node tmp: queue){
				tempQueue.add(tmp);
			}
			
			queue.removeAll(queue);
			
			LinkedList<Integer> list = new LinkedList<Integer>();
			
			for(Node n: tempQueue){
				if(n.hasLeft()){
					queue.add(n.left);
				}
				if(n.hasRight()){
					queue.add(n.right);
				}
				
				list.add(new Integer(n.value));				
			}
			result.add(list);
		}
		return result;		
	}

- pjane September 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hope this problem needs extra space to solve ... I mean you need a stack or queue in addition to the final set of linked lists. Please let me know in case I am wrong.

Solution - Do level order traversal and push all elements in the next level into the stack or queue. And build a linked list with the elements in the current level(these elements are got by poping the stack/queue). Initially, for the first level, the element is got from the pointer to the root of the tree. Do this till end of the final level of the tree.

- Anand_friendly January 12, 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