## Amazon Interview Question for SDE1s

Country: India
Interview Type: In-Person

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

``````public static List<Node> toLists(Node root){
ArrayList<Node> result = new ArrayList<>();
if (root != null) {
}
while(previousLayer.size() != 0){
for (Node node : previousLayer){
if (node.left != null){
}
if (node.right != null){
}
}
previousLayer = currentLayer;
}
return result;
}

private static Node layerToList(List<Node> layer){
Node currentHead = null, current = null;
for (Node node : layer){
node.left = null;
node.right = null;
current = node;
}
else{
current.right = node;
current = current.right;
}
}
}``````

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

This is basically an application of BFS. We will keep 2 queues- one representing one level and the other representing another.

We start by putting the head in the first queue (Q1). Now, we BFS the head, and add all of its children to Q2 in order. We remove the contents of Q1 and make it a linked list. Now, we BFS Q2 and put all of the children of nodes in Q2 into Q1. Remove the contents of Q2 and make it a linked list. Continue this process of alternating BFS between queues until there are only null values in a queue.

Some Code:

``````ArrayList linkedListify(Node head) {

Queue q1, q2; //assume these are initialized or whatever

int counter = 0;
while (true) {

if (x == null) { break; }
counter++;
}

}

if (q1.size() == 0) { return null; }
Node current;

while (q1.size() != 0) {

current = current.next;
}

return list;
}``````

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

What is "current" used for?

Also, the logic before the while loop in convertQueueToLinkedList seems redundant. Doesn't the while loop handle that already?

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

Assuming that it is binary tree

``````LinkList*  createLinkList(Stact<LinkList* >& s)
{
while(!s.IsEmpty()){
}
}

void createLL(TreeNode * node)
{
Queue<TreeNode *> q;
int tree_enqueue_count = 0;
int tmp_counter = 0;

q.enqueue(node);
tree_enqueue_count++;

while (!q.IsEmpty()){
TreeNode * tmp = q.dequeue();

if (tmp.left != null){
q.enqueue(tmp.left);
tmp_counter++;
}

if (tmp.right != null){
q.enqueue(tmp.right);
tmp_counter++;
}

ll->content = tmp->content;

s.push(ll);
--tree_enqueue_count;

if (tree_enqueue_count == 0){
// Don't know what to do with the head pointer of the linklist. So I just do nothing
tree_enqueue_count = tmp_counter;
tmp_counter = 0;
}
}

}``````

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

``````void create_list(Node *rootNode)
{
q.push_back(rootNode->left);
q.push_back(rootNode->right);

rootNode->left = NULL;
rootNode->right = NULL;

while(q.size() > 0)
{
q = process_q(q);
}
}

deque<Node*> process_q(deque<Node*> q)
{
deque<Nodes*> qNextLevel;
Node *currentNode = q.front();
q.pop_front();
qNextLevel.push_back(currentNode->left);
qNextLevel.push_back(currentNode->right);

while(q.size() > 0)
{
Node *nextNode = q.front();
qNextLevel.push_back(nextNode->left);
qNextLevel.push_back(nextNode->right);
currentNode->left = NULL;
currentNode->right = nextNode;
currentNode = nextNode;
q.pop_front();
}
currentNode->right = NULL;
return qNextLevel;
}``````

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

``````class ListNode
{
public int Data { get; set; }
public ListNode Next { get; set; }
}

public class TreeNode
{
public int Data { get; set; }
public TreeNode Left { get; set; }
public TreeNode Right { get; set; }
}

public static List<ListNode> CreateLevelList(TreeNode root)
{

List<ListNode> result = new List<ListNode>();

if(root == null)
{
return result;
}

Queue<TreeNode> stack = new Queue<TreeNode>();

// Using null as the marker of a new level
queue.Enqueue(root);
queue.Enqueue(null);

while(queue.Count > 0)
{
TreeNode node = queue.Dequeue();

if(node == null)
{

queue.Enqueue(null);
}
else
{
tail.Next = new ListNode() { Data = node.Data };
tail = tail.Next;

if(node.Left != null)
queue.Enqueue(node.Left);

if(node.Rigth != null)
queue.Enqueue(node.Right);
}

}

return result;
}``````

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

``````#include <iostream>
#include <list>
using namespace std;

class Node {
public:
int val;
Node *left;
Node *right;
Node(int v, Node *l, Node *r) {
val = v;
left = l;
right = r;
}
};

int depth(Node *r) {
if(r==NULL) return 0;
return 1 + max(depth(r->left), depth(r->right));
}

void make_list(Node *r, int cur, int d, list<int>* &l) {

if(r==NULL) return;
if(cur==d) {
l[cur].push_back(r->val);
return;
}
make_list(r->left, cur+1, d, l);
make_list(r->right, cur+1, d, l);
return;
}

void print(list<int>* &l, int d) {
for(int i=0; i<d; i++) {
for(auto it: l[i]) {
cout<<(it)<<" ";
}
cout<<endl;
}
}

int main() {
Node *r = new Node(1, new Node(2, NULL, new Node(4, NULL, NULL)), new Node(3, NULL, new Node(5, NULL, NULL)));
int d = depth(r);
list<int>* l = new list<int>[d]();
for(int i=0; i<d; i++) {
make_list(r, 0, i, l);
}
print(l, d);
return 0;
}``````

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

private void connectSameLevelNode1(TreeNode tree){
try{
if(tree == null){
return;
}
if(tree.getLeft() != null){
if(tree.getRight() != null){
tree.getLeft().setNext(tree.getRight());
tree.getRight().setNext(getNextPointer(tree));
}else{
tree.getLeft().setNext(getNextPointer(tree));
}
}else if(tree.getRight() != null){
tree.getRight().setNext(getNextPointer(tree));
}
connectSameLevelNode(tree.getLeft());
connectSameLevelNode(tree.getRight());
}catch(Exception ex){
ex.printStackTrace();
}
}

private TreeNode getNextPointer(TreeNode tree){
try{
TreeNode nextPointer = tree.getNext();
while(nextPointer != null){
if(nextPointer.getLeft()!=null){
return nextPointer.getLeft();
}
if(nextPointer.getRight() != null){
return nextPointer.getRight();
}
nextPointer = nextPointer . getNext();
}
return null;
}catch(Exception ex){
ex.printStackTrace();
}
return null;
}

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

``````private void connectSameLevelNode1(TreeNode tree){
try{
if(tree == null){
return;
}
if(tree.getLeft() != null){
if(tree.getRight() != null){
tree.getLeft().setNext(tree.getRight());
tree.getRight().setNext(getNextPointer(tree));
}else{
tree.getLeft().setNext(getNextPointer(tree));
}
}else if(tree.getRight() != null){
tree.getRight().setNext(getNextPointer(tree));
}
connectSameLevelNode(tree.getLeft());
connectSameLevelNode(tree.getRight());
}catch(Exception ex){
ex.printStackTrace();
}
}

private TreeNode getNextPointer(TreeNode tree){
try{
TreeNode nextPointer = tree.getNext();
while(nextPointer != null){
if(nextPointer.getLeft()!=null){
return nextPointer.getLeft();
}
if(nextPointer.getRight() != null){
return nextPointer.getRight();
}
nextPointer = nextPointer . getNext();
}
return null;
}catch(Exception ex){
ex.printStackTrace();
}
return null;``````

}

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

``````#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<queue>
struct tree
{
int data;
struct tree * left;
struct tree *right;
};

struct tree * create(int num)
{
struct tree * temp = (struct tree *)malloc(sizeof(struct tree));
temp->data=num;
temp->left=NULL;
temp->right=NULL;
return temp;
}
void insert(struct tree **root,int num)
{
if(*root ==NULL)
{
*root=create(num);
}
else
{
if(num < (*root)->data)
insert(&(*root)->left,num);
else
insert(&(*root)->right,num);
}
}

struct node
{
int data;
struct node *next;
};

struct node * createNode(int num)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
if(temp)
{
temp->data = num;
temp->next = NULL;
return temp;
}
else
return NULL;
}

{
{
}
else
{
while(temp->next!=NULL)
temp = temp->next;
temp->next = createNode(num);
}
}

{
{
else
}
}

{
struct node *nxt = NULL;
while(cur !=NULL)
{
nxt = cur->next;
free(cur);
cur=nxt;
}
}

int MAXM(int a, int b)
{
return a >b ? a : b;
}
int heightOfTree(struct tree *root)
{
if(!root)
return 0;
else
return (1 + MAXM(heightOfTree(root->left), heightOfTree(root->right)));
}

void printEachLevel(struct tree * root, int level, struct node **head)
{
if(root==NULL)
return;
if(level == 1)
{
}
else
{
}
}

void printLevelWise(struct tree * root)
{
int height = heightOfTree(root);
for(int i = 1; i<=height; i++)
{
printf("\n");
}
}
int main()
{
struct tree *root = NULL;
insert(&root,10);
insert(&root,6);
insert(&root,17);
insert(&root,4);
insert(&root,14);
insert(&root,19);
printLevelWise(root);
getch();
return 0;``````

}

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

This is just traversing each level and if you encounter the last element in the level, add that corresponding linkedlist to an arrayList. To know if the end of each level has been reached, we can simply add a null in the queue in beginning and if you enounter null while pop, add another.

``````public static ArrayList<LinkedList<Tree>> linkNodes(Tree root) {
Tree current = root;
if(current != null) {
}
while(!queue.isEmpty()) {
current = queue.remove();
if(current == null) {
}
else {
if(current.left != null) {
}
if(current.right != null) {
}
}
}
return arrayList;
}``````

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

sounds about right in your english explanation, except you aren't adding a new null to the end of the queue, so this code will never be able to determine the end of the level after the root level :P
The loop is adding the left and right to the queue only if it is not null, which will reiterate in a recursive fashion to repeat adding non-null lefts and rights, which means you are never adding an extra null.

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

BFS + create new tree

``````class ListNode:
def __init__(self,x):
self.val = x
self.next = None

class Solution:
def levelList(self,root):
output = []
outputMid = []
level = [root]
nextLevel = []
while (level):
for item in level:
outputMid.append(item.val)
if item.left:
nextLevel.append(item.left)
if item.right:
nextLevel.append(item.right)
i = 0
level = nextLevel
while (i<=len(outputMid)-2):
item = ListNode(outputMid[i+1])
i +=1
return output``````

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

``````#include <iostream>
using namespace std;

struct node{
int data;
struct node *left;
struct node *right;
struct node *nextRight;
}
void connectRightUtil(struct node * root){
if(root==NULL)// if there is Node is NULL
return;
if(root->left==NULL && root->right==NULL){// if there is only one Node
root->nextRight=NULL;
return;
}
connectRight(root);
}
void connectRight(struct node root){

if(root==null)
return;
if(root->left!=NULL){
if(root->right!=NULL){// if right child is not NULL then just put "root->left->nextRight=root->right;"
root->left->nextRight=root->right;
} else{
struct node * result=getRight(root);// get rightmost nextRight Node
if(root->nextRight!=NULL){
root->left->nextRight=right->left? result->left:(result->right?result->right:NULL);
}
else{
root->left->nextRigh=NULL;
}
}
}
if(root->right!=NULL){
root->right->nextRight=right->left? result->left:(result->right?result->right:NULL);
}
connectRight(root->left);
connectRight(root->right);
}
struct node * getRight(struct Node * root){
while(root->left==NULL && root->right==NULL root->nextRight!=NULL)
root=root->nextRight;
return root;``````

}

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

Iterative method using Queue:
Aux storage:
Queue traverseQueue
int levelIndex

Psuedo code:

``````traverseQueue.add(root);
levelIndex = 0;
while (traverseQueue.Size() > 0) {
for (int temp = traverseQueue.size(); temp > 0; temp--) {
TreeNode temp = traverseQueue.remove();
current.value = temp.value;
for (TreeNode child : temp.childs) {
}
if (temp > 1) {
// if not the last node of current level
current = current.next;
}
}
levelIndex++;
}

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

// MakeTreeToLinkedList.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <memory>
#include <unordered_map>

using namespace std;

struct Node
{
int value;
shared_ptr<Node> left;
shared_ptr<Node> right;
};

{
int value;
};

{
};

{
if (root == nullptr)
{
return;
}

currLevel++;
tempLLNode->value = root->value;
tempLLNode->next = nullptr;
{
// Didn't find the node so add
}
else
{
}
currLevel--;
}

int _tmain(int argc, _TCHAR* argv[])
{
shared_ptr<Node> root = make_shared<Node>();
root->value = 10;

shared_ptr<Node> n6 = make_shared<Node>();
n6->value = 6;

shared_ptr<Node> n17 = make_shared<Node>();
n17->value = 17;

shared_ptr<Node> n4 = make_shared<Node>();
n4->value = 4;

shared_ptr<Node> n14 = make_shared<Node>();
n14->value = 14;

shared_ptr<Node> n19 = make_shared<Node>();
n19->value = 19;

root->left = n6;
root->right = n17;

n6->left = n4;

n17->left = n14;
n17->right = n19;

int currLevel = -1;

{
printf("\n");

for (auto currNode = currMapEntry.second->front; currNode != nullptr; currNode = currNode->next)
{
printf(" %d", currNode->value);
}

}
return 0;
}

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

// MakeTreeToLinkedList.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <memory>
#include <unordered_map>

using namespace std;

struct Node
{
int value;
shared_ptr<Node> left;
shared_ptr<Node> right;
};

{
int value;
};

{
};

{
if (root == nullptr)
{
return;
}

currLevel++;
tempLLNode->value = root->value;
tempLLNode->next = nullptr;
{
// Didn't find the node so add
}
else
{
}
currLevel--;
}

int _tmain(int argc, _TCHAR* argv[])
{
shared_ptr<Node> root = make_shared<Node>();
root->value = 10;

shared_ptr<Node> n6 = make_shared<Node>();
n6->value = 6;

shared_ptr<Node> n17 = make_shared<Node>();
n17->value = 17;

shared_ptr<Node> n4 = make_shared<Node>();
n4->value = 4;

shared_ptr<Node> n14 = make_shared<Node>();
n14->value = 14;

shared_ptr<Node> n19 = make_shared<Node>();
n19->value = 19;

root->left = n6;
root->right = n17;

n6->left = n4;

n17->left = n14;
n17->right = n19;

int currLevel = -1;

{
printf("\n");

for (auto currNode = currMapEntry.second->front; currNode != nullptr; currNode = currNode->next)
{
printf(" %d", currNode->value);
}

}
return 0;
}

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

``````// MakeTreeToLinkedList.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <memory>
#include <unordered_map>

using namespace std;

struct Node
{
int value;
shared_ptr<Node> left;
shared_ptr<Node> right;
};

{
int value;
};

{
};

{
if (root == nullptr)
{
return;
}

currLevel++;
tempLLNode->value = root->value;
tempLLNode->next = nullptr;
{
// Didn't find the node so add
}
else
{
}
currLevel--;
}

int _tmain(int argc, _TCHAR* argv[])
{
shared_ptr<Node> root = make_shared<Node>();
root->value = 10;

shared_ptr<Node> n6 = make_shared<Node>();
n6->value = 6;

shared_ptr<Node> n17 = make_shared<Node>();
n17->value = 17;

shared_ptr<Node> n4 = make_shared<Node>();
n4->value = 4;

shared_ptr<Node> n14 = make_shared<Node>();
n14->value = 14;

shared_ptr<Node> n19 = make_shared<Node>();
n19->value = 19;

root->left = n6;
root->right = n17;

n6->left = n4;

n17->left = n14;
n17->right = n19;

int currLevel = -1;

{
printf("\n");

for (auto currNode = currMapEntry.second->front; currNode != nullptr; currNode = currNode->next)
{
printf(" %d", currNode->value);
}

}
return 0;
}``````

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.