## Amazon Interview Question for Applications Developers

• 0

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

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

we can use breadth first search algorithm

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

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

Using recursive is much more convenient than iterative...

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

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.

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

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

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

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

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.

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

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

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

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

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

return null;
}
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
HashMap<BinaryTreeNode,Integer> map=new HashMap<BinaryTreeNode,Integer>();
while(!path.isEmpty()){
BinaryTreeNode current=path.poll();
int currentlevel=map.get(current);
if(result.size()<currentlevel){
}
if(current.left!=null){
map.put(current.left, currentlevel+1);
}
if(current.right!=null){
map.put(current.right, currentlevel+1);
}

}

return result;
}

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<Node> queue = new ArrayList<Node>();

while(!queue.isEmpty()){
ArrayList<Node> tempQueue = new ArrayList<Node>();

for(Node tmp: queue){
}

queue.removeAll(queue);

for(Node n: tempQueue){
if(n.hasLeft()){
}
if(n.hasRight()){
}

}
}
return result;
}``````

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.

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.

### 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.