Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
O(n) queue implementation:
public static void printLevelOrder(TreeNode* root)
{
if(!root) return;
Queue* q = new Queue();
TreeNode* node;
int count = 0;
int level = 0;
q->push(root);
count++;
print(“Level 0: ”);
while(!q.isEmpty())
{
node = q->pop();
print(node->data+” ”);
if(node->left) q->push(node->left);
if(node->right) q->push(node->right);
if(--count == 0)
{
count = q->size();
level ++;
print(“\nLevel ”+level+”: ”);
}
}
}
public class PrintNaryTreeWithLevels {
private static Queue<Vertex> queue = new LinkedList<Vertex>();
public static void bfs(Graph graph) {
Vertex vertex = graph.getVertexesAsArray()[0];
vertex.setVisited(true);
int counter = 0;
System.out.println(vertex + "level " + counter);
counter++;
queue.add(vertex);
//null acts as a pointer/marker when new level should begin.
queue.add(null);
while (!queue.isEmpty()) {
Vertex currentVertex = queue.remove();
if (currentVertex == null) {
counter++;
if (queue.isEmpty()) {
break;
}
currentVertex = queue.remove();
queue.add(null);
}
Vertex unvisitedVertex;
while ((unvisitedVertex = getUnvisitedVertex(currentVertex)) != null) {
unvisitedVertex.setVisited(true);
queue.add(unvisitedVertex);
System.out.println(unvisitedVertex + "level " + counter);
}
}
}
public static Vertex getUnvisitedVertex(Vertex vertex) {
for (Vertex temp : vertex.getDependsOn()) {
if (!temp.isVisited()) {
return temp;
}
}
return null;
}
public static void main(String[] args) {
Graph graph = new UnDirectedGraph(11);
graph.addEdge("V1", "V2");
graph.addEdge("V1", "V3");
graph.addEdge("V1", "V6");
graph.addEdge("V2", "V4");
graph.addEdge("V3", "V5");
graph.addEdge("V3", "V10");
graph.addEdge("V4", "V7");
graph.addEdge("V4", "V8");
graph.addEdge("V6", "V9");
graph.addEdge("V9", "V11");
graph.displayVertexList();
graph.displayGraphDependency();
bfs(graph);
}
}
{
// sudo code
void printLevels(TreeNode root)
{
Queue queue;
queue.push(root);
queue.push("LEVEL_DELIM");
int level = 0;
while (!queue.front != "LEVEL_DELIM")
{
print "Level-" + level;
while(queue.front != "LEVEL_DELIM")
{
TreeNode node = queue.front;
print node
TreeNode[] childNodes= getChildren(node);
queue.push_all(childNodes);
queue.pop();
}
queue.pop();
queue.push("LEVEL_DELIM");
level++;
}
}
var values = [];
var solution = function(num, node) {
values[num] = (values[num]||"") + node.value + " "
if(node.left) solution(num+1, node.left)
if(node.right) solution(num+1, node.right)
}
var printValues = function() {
for(var i=0; i<values.length; i++) {
console.debug("Level " + i + ": " + values[i]);
}
}
You could store the level with each node in your traversal.
#!/usr/bin/python
import Queue
class Node(object):
def __init__(self,data):
self.data = data
self.childs = []
class NodeWithLevel(object):
def __init__(self, node, level):
self.node = node
self.level = level
def populate(tree):
tree.childs = [Node(3), Node(10), Node(4)]
for chld in tree.childs:
chld.childs = [Node(1), Node(31), Node(11), Node(5), Node(9)]
def dump(tree):
q = Queue.Queue()
q.put(tree)
while not q.empty():
node = q.get_nowait()
print "%d" % node.data
for chld in node.childs:
q.put(chld)
def dump_with_level(tree):
q = Queue.Queue()
q.put(NodeWithLevel(tree,1))
pl = -1
while not q.empty():
nodex = q.get_nowait()
if nodex.level > pl:
print
print "Level %d" % nodex.level,
pl = nodex.level
print "%d" % nodex.node.data,
for chld in nodex.node.childs:
q.put(NodeWithLevel(chld, nodex.level+1))
tree = Node(12)
populate(tree)
dump(tree)
dump_with_level(tree)
Java implementation:
1. TreeLevelPrint class
package com.sateesh;
import java.util.ArrayList;
import java.util.List;
/**
* Created with IntelliJ IDEA.
* User: sateesh
* Date: 12/11/13
* Time: 11:45 AM
*/
public class TreeLevelPrint {
public static void main(String[] args) {
printNodeElements(buildTree());
}
private static TreeNode buildTree() {
TreeNode node2 = new TreeNode("bar");
TreeNode node4 = new TreeNode("foobar");
node2.addChild(node4);
TreeNode node3 = new TreeNode("baz");
TreeNode node5 = new TreeNode("barfoo");
node3.addChild(node5);
TreeNode node1 = new TreeNode("foo");
node1.addChild(node2);
node1.addChild(node3);
return node1;
}
private static void printNodeElements(TreeNode tree) {
if (tree == null)
System.out.println(" tree is null ");
System.out.println("Level 0: " + tree.getName());
printNodeElements(tree.getChildren(), 1);
}
private static void printNodeElements(List<TreeNode> nodes, int level) {
if (nodes == null || nodes.size()==0)
return;
StringBuilder builder = new StringBuilder();
List<TreeNode> nextLevelNodes = new ArrayList<TreeNode>();
for(TreeNode node : nodes) {
builder.append(node.getName()).append(" ");
if (node.getChildren() != null)
nextLevelNodes.addAll(node.getChildren());
}
System.out.println("Level " + level + ": " + builder.toString());
printNodeElements(nextLevelNodes, level+1);
}
}
2. TreeNode class
package com.sateesh;
import java.util.ArrayList;
import java.util.List;
/**
* Created with IntelliJ IDEA.
* User: sateesh
* Date: 12/11/13
* Time: 11:44 AM
*/
public class TreeNode {
private String name;
private List<TreeNode> children;
public TreeNode(String name) {
this.name = name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public List<TreeNode> getChildren() {
return children;
}
public void setChildren(List<TreeNode> children) {
this.children = children;
}
public void addChild(TreeNode child) {
if (children == null) {
children = new ArrayList<TreeNode>();
}
children.add(child);
}
}
3. Output
Level 0: foo
Level 1: bar baz
Level 2: foobar barfoo
Uses one queue
public static void PrintLevel(TreeNode root)
{
if (root == null)
Console.WriteLine("Tree is empty! Nothing to do here!");
Queue<TreeNode> q = new Queue<TreeNode>();
q.Enqueue(root);
// Current Level Node Count
int c = 1;
// Next Level Node Count;
int n = 0;
// Level Count;
int l = 0;
Console.Write("Level " + l.ToString() + ":");
while (q.Count > 0)
{
TreeNode p = q.Dequeue();
if (p.Children != null)
{
foreach (TreeNode child in p.Children)
{
//Enqueue the next level node and add 1 to the next level node count n
q.Enqueue(child);
n += 1;
}
}
Console.Write(" " + p.Name);
// Done processing the current node. Subtract 1 from current level node count c
c -= 1;
if (c == 0) // Current level is empty. A new level starts
{
c = n; // Assign next level count to current level
n = 0; // Zero out the next level node count
l += 1; // Add 1 to the level count
if (c > 0) // If there is nodes in the new level print the new level number in a new line
{
Console.WriteLine();
Console.Write("Level " + l.ToString() + ":");
}
}
}
}
void printLevels(TreeNode root)
{
// -- CODE--
int level = 0;
List<TreeNode> currentLevelNodes = new LinkedList();
List<TreeNode> nextLevelNodes = new LinkedList();
currentLevelNodes.add(root);
while(currentLevelNodes.size() > 0) {
System.out.print("Level " + level + " " );
for(TreeNode node : currentLevelNodes) {
System.out.print( node.name + " " );
nextLevelNodes.addAll(node.getChildren());
}
System.out.println();
currentLevelNodes.clear();
currentLevelNodes.addAll(nextLevelNodes);
nextLevelNodes.clear();
level++;
}
}
public static void printLevelOrder(TreeNode* root)
{
if(!root)
return;
int level = 0;
int c1 = 0;
int c2 = 0;
TreeNode *node;
List<TreeNode> nodes = new List<TreeNode>();
Queue *q = new Queue();
q.EnQueue(root);
while(! q.isEmpty())
{
nodes.clear();
System.out.println("level "+level);
node = q.DeQueue();
System.out.println("node->name");
nodes.addAll(node->getChildren());
for( TreeNode n: nodes)
{
q.EnQueue(n);
}
c2 = q.length();
if(--c1 == 0)
{
++level;
c1 = c2;
}else
--c1;
}
}
public static void printLevels(TreeNode root){
List<TreeNode> la=new ArrayList<TreeNode>();
List<TreeNode> lb=new ArrayList<TreeNode>();
int level=0;
la.add(root);
while(true){
if(la.isEmpty()) break;
System.out.print("Level "+level+": ");level++;
for(TreeNode node:la){
System.out.print(node.getName()+" ");
lb.addAll(node.getChildren());
}
System.out.println();
la.clear();la.addAll(lb);
lb.clear();
}
}
O(n) queue implementation:
- zahidbuet106 December 12, 2013public static void printLevelOrder(TreeNode* root) { if(!root) return; Queue* q = new Queue(); TreeNode* node; int count = 0; int level = 0; q->push(root); count++; print(“Level 0: ”); while(!q.isEmpty()) { node = q->pop(); print(node->data+” ”); if(node->left) q->push(node->left); if(node->right) q->push(node->right); if(--count == 0) { count = q->size(); level ++; print(“\nLevel ”+level+”: ”); } } }