## Amazon Interview Question for SDE1s

• 0
of 0 votes

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
5
of 7 vote

We can store each level in the form of a linked list,each node will have 2 pointers,next and child...next will point to the next sibling in the same level,child will point to the starting point of child linked list....

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

I think that extra pointer will take the same space as an extra collection.

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

Design the tree node as

``````public class Node {
int value;
LinkedList<Node> children = new LinkedList<Node>();
}``````

For the level order traversal, we do not have to store the nodes in a queue we just need to store the head of the children linked list.

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

We can do depth limited Depth First Search.
We iterate from 1-depth. And print all elements with that particular depth.

You might think that the complexity is going to be high. But no. When the tree isn't sparse, the number of children in nth level is equal to the number of elements from level 1-(n-1). So the complexity is just getting doubled. Not more.

Asymptotically it is still same as DFS/BFS.

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

Can we do DFS without using Extra space? I see we use stack for DFS and queue for BFS.

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

We can follow naive algorithm to print kth level using recursion...but this will increase complexity to n^2...any better approach??

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

We can use vector class

``````class Vector
{
public Node[] child = new Node[1];
public int count = 0;

public void add(string name)
{
if (count < child.Length)
{
child[count++] = new Node(name);
}
else
{
resize();
child[count++] = new Node(name);
}
}
public void delete(int index)
{
Node[] tmp = new Node[1];
count = 0;
for (int i = 0; i < child.Length; i++)
{
if (i != index)
{
tmp[count++] = child[i];
}
}
child = tmp;
}

public void resize()
{
Node[] tmp = new Node[child.Length * 2];
for (int i = 0; i < child.Length; i++)
{
tmp[i] = child[i];
}
child = tmp;
}
public void travers()
{
for (int i = 0; i < count; i++)
{
Console.Write(child[i].name + " ");
}
Console.WriteLine();
}
}

class Node
{
public string name;
public Node parent;

public Node() { }
public Node(string name) { this.name = name; }
}``````

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

we can't use extra storage, so how about this:

``````public class Node
{
Node levelFirst; //1st node of every level
Node next; //sibling of every node
Node parent;
int value;
}

Now just do a level order traversal. Lots of edge cases - how do you detect that the level is done. Keep track of 1st node of every level, as you'll need to come back to it, once every level is done, to start the next level.``````

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