Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
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.
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; }
}
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.
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....
- Monj June 27, 2013