CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Amazon Interview Question for Software Engineer / Developers


Team: Kindle
Country: India



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

Here is the solution, however I need to refine the traversal to DFS or BFS

import java.util.*;
import java.io.*;
import java.util.List;

//The node for the n-ary tree


public class NaryTree 
{
    //The display funtion traverses the tree

    void display(NaryTreeNode t)
    {
        Iterator<NaryTreeNode> IT = t.nary_list.iterator();
        if(!(IT.hasNext()))   //If the node does not  have any children, enter.
        {
        //    System.out.println("No more childs of this node");
            System.out.print( t.data + " ");
            return;
        }

        while(IT.hasNext()){
            display(IT.next()) ;            //Recursive Call
        }

        System.out.println();
        System.out.println("Jumping One Level up");
        System.out.print(t.data + " ");
    }

    public static void main(String args[]){

        NaryTree t1 = new NaryTree();

        NaryTreeNode root = new NaryTreeNode();

        root.data = 100;

        NaryTreeNode lev_11 = new NaryTreeNode();   lev_11.data=90;
        NaryTreeNode lev_12 = new NaryTreeNode();   lev_12.data=50;
        NaryTreeNode lev_13 = new NaryTreeNode();   lev_13.data=70;
        NaryTreeNode lev_21 = new NaryTreeNode();   lev_21.data=20;
        NaryTreeNode lev_22 = new NaryTreeNode();   lev_22.data=30;

        //Add all the nodes to a list.
        List<NaryTreeNode> temp = new ArrayList<NaryTreeNode>();

        temp.add(lev_11);
        temp.add(lev_12);
        temp.add(lev_13);
        List<NaryTreeNode> temp2 = new ArrayList<NaryTreeNode>();
        temp2.add(lev_21);
        temp2.add(lev_22);
        lev_11.nary_list.addAll(temp2);
        //Add Temp to root  to form a leaf of the root

        root.nary_list.addAll(temp);
        //Call the display function.
        t1.display(root);
   }
}

- chaos October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this was not east it was hidden bug. the answer to the question lies in the fact that the call t.nary_list.iterator() creates NEW iterator, so each recursive call creates new iterator meaning you start again from the start of the list and the recursion never stop.
The solution is to define an Iterator veriable before the recursive call:

void display(NaryTreeNode t)
{
Iterator itr = t.nary_list.iterator();
if(!(itr.hasNext())) //If the node does not have any children, enter.
{
System.out.println("No more childs of this node");
System.out.println("Value is: " + t.data);
return;
}

while(itr.hasNext())
{
display((NaryTreeNode )itr.next()) ; //Recursive Call
}

System.out.println("Jumping One Level up");
System.out.println(t.data);
}

- dlev October 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

if i correctly understand your question this is nothing but traversal of the tree

u can use either BFS or DFS

lets say its n- ary tree

the structure will be something like

{struct tree {
int data ;

struct tree *children[n];          //array of pointers to n children (they may be nulls also )
}


now use a queue for BFS 


while dequeuing a node in the queue 
traverse all the nodes like 


for(i=0;i<n;i++)
if(!current ->children[i])
enqueue(current ->children[i])

}
hope its clear ...

- sreeram October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

package com.narray;

public class NaryTree {

	NaryTreeNode root;
	
	public NaryTree(NaryTreeNode root) {
		this.root = root;
	}
	
	public static void main(String[] args) {
		NaryTreeNode root = new NaryTreeNode(100);
		NaryTree tree = new NaryTree(root);
		NaryTreeNode childroot1 = new NaryTreeNode(20);
		NaryTreeNode childroot2 = new NaryTreeNode(30);
		NaryTreeNode childroot3 = new NaryTreeNode(40);
		NaryTreeNode childroot4 = new NaryTreeNode(50);
		root.add(childroot1);
		root.add(childroot2);
		root.add(childroot3);
		root.add(childroot4);

		NaryTreeNode child1ChildRoot1 = new NaryTreeNode(80);
		NaryTreeNode child2ChildRoot1 = new NaryTreeNode(90);
		childroot1.add(child1ChildRoot1);
		childroot1.add(child2ChildRoot1);

		NaryTreeNode child1ChildRoot2 = new NaryTreeNode(110);
		childroot2.add(child1ChildRoot2);
		
		NaryTreeNode child1ChildRoot3 = new NaryTreeNode(120);
		NaryTreeNode child2ChildRoot3 = new NaryTreeNode(130);
		childroot3.add(child1ChildRoot3);
		childroot3.add(child2ChildRoot3);
		
		tree.display(root);
	}

	private void display(NaryTreeNode node) {
		if(node.getChildren().size() > 0) {
			for(int i = 0 ; i < node.getChildren().size() ; i++) {
				display((NaryTreeNode)node.get(i));
			}
			System.out.println(node.getData());
		} else {
			System.out.println(node.getData());
		}
			
	}
}

package com.narray;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

public class NaryTreeNode implements List{
	
	int data;
	List<NaryTreeNode> children;
	
	public NaryTreeNode(int data) {
		this.data = data;
		children = new ArrayList<NaryTreeNode>();
	}
	public int getData() {
		return data;
	}
	public void setData(int data) {
		this.data = data;
	}
	public List<NaryTreeNode> getChildren() {
		return children;
	}
	public void setChildren(List<NaryTreeNode> children) {
		this.children = children;
	}
	@Override
	public boolean add(Object narayTreeNode) {
		children.add((NaryTreeNode) narayTreeNode);
		return true;
	}
	@Override
	public void add(int arg0, Object arg1) {
		// TODO Auto-generated method stub
		
	}
	@Override
	public boolean addAll(Collection arg0) {
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public boolean addAll(int arg0, Collection arg1) {
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public void clear() {
		// TODO Auto-generated method stub
		
	}
	@Override
	public boolean contains(Object arg0) {
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public boolean containsAll(Collection arg0) {
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public Object get(int index) {
		// TODO Auto-generated method stub
		return children.get(index);
	}
	@Override
	public int indexOf(Object arg0) {
		// TODO Auto-generated method stub
		return 0;
	}
	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public Iterator iterator() {
		// TODO Auto-generated method stub
		return null;
	}
	@Override
	public int lastIndexOf(Object arg0) {
		// TODO Auto-generated method stub
		return 0;
	}
	@Override
	public ListIterator listIterator() {
		// TODO Auto-generated method stub
		return null;
	}
	@Override
	public ListIterator listIterator(int arg0) {
		// TODO Auto-generated method stub
		return null;
	}
	@Override
	public boolean remove(Object arg0) {
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public Object remove(int arg0) {
		// TODO Auto-generated method stub
		return null;
	}
	@Override
	public boolean removeAll(Collection arg0) {
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public boolean retainAll(Collection arg0) {
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public Object set(int arg0, Object arg1) {
		// TODO Auto-generated method stub
		return null;
	}
	@Override
	public int size() {
		// TODO Auto-generated method stub
		return 0;
	}
	@Override
	public List subList(int arg0, int arg1) {
		// TODO Auto-generated method stub
		return null;
	}
	@Override
	public Object[] toArray() {
		// TODO Auto-generated method stub
		return null;
	}
	@Override
	public Object[] toArray(Object[] arg0) {
		// TODO Auto-generated method stub
		return null;
	}

}

I hav'nt implements all the method for NarayTreeNode.

- Anonymous October 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can someone help.
For the start i have just used a tree with root node having only three children.
Here is the code in java:
Looks like the iterator is not functioning properly so i get stuct in the while loop in the display function. :(

import java.util.*;
import java.io.*;
import java.util.List;


public class NaryTreeNode {
        int data;
	List <NaryTreeNode> nary_list = new ArrayList<NaryTreeNode>();
}



public class NaryTree 
{
    	void display(NaryTreeNode t)
    {
	if(!(t.nary_list.iterator().hasNext()))   //If the node does not  have any children, enter.
        {
     		System.out.println("No more childs of this node");
     		System.out.println("Value is: " + t.data);
     		return;
    		}
     	
     	while(t.nary_list.iterator().hasNext())
                {
     		display(t.nary_list.iterator().next()) ;    		//Recursive Call
              	}
    	
     	System.out.println("Jumping One Level up");
    	System.out.println(t.data);
    }


 public static void main(String args[]){
       	NaryTree t1 = new NaryTree();
	NaryTreeNode root = new NaryTreeNode();
       	root.data = 100;
    	
    	NaryTreeNode lev_11 = new NaryTreeNode();    	lev_11.data=90;
    	NaryTreeNode lev_12 = new NaryTreeNode();    	lev_12.data=50;
    	NaryTreeNode lev_13 = new NaryTreeNode();    	lev_13.data=70;
      //Adding all the child nodes to a list	
    	List<NaryTreeNode> temp = new ArrayList<NaryTreeNode>();
   
    	temp.add(lev_11);
    	temp.add(lev_12);
    	temp.add(lev_13);
    	//Adding the list as a node to root so that we now have root with three children

    	root.nary_list.addAll(temp);
        //Call the display function to traverse
        t1.display(root);
   }
}

Output:

No more childs of this node
Value is: 90
No more childs of this node
Value is: 90
No more childs of this node
Value is: 90
.
.
.
.

- chaos October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
The data structure for n-ary tree would be something like this: {{{struct node { int a; // assuming integer data struct node *nextsibling; // sibling on the same depth from same parent struct node *firstchild; // first child } typedef struct node *nary_node; traversal(nary_node node) { while (nary_node) { printf("data %d", nary_node->data); traversal(nary_node->nextsibling); traversal(nary_node->firstchild); } return; } } - freeninza October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<Node*> get_all_nodes(Node* root) {
  queue<Node*> q;
  q.push(root);
  vector<Node*> visited;
  while (!q.empty()) {
    Node* node = q.pop();
    visited.push_back(node);
    for (int i = 0; i < node->children.size(); i++) q.push(node->children[i]);
  }
  return visited;
}

- Martin October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

BFS.

public class NaryTreeNode{
char content;
boolean marker;
Collection<NaryTreeNode> child;
......
}

- zhouzhou October 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
change NUM to any value or store no of children in node itself {{{ #define NUM 2 struct node { int val; int childcount; char attrval; struct node* children[NUM]; }; typedef struct node tree; struct node* newnode(){ struct node* node = malloc (sizeof(struct node)); //node->attrval=tribute; node->childcount=NUM; int i; for (i=0; i<NUM ; i++){ node->children[i]=NULL; } return(node); } struct node* insert (struct node* node, char* data){ int i; for (i=0; i< strlen(data); i++){ if(!node) { node= newnode(); } else{ node->children[i]=newnode(); node->children[i]->attrval=i; node = node->children[i]; } } return node; } void printnode(struct node* node){ int i; for (i=0;i<NUM;i++){ //if(node->children[i]) printnode(node->children[i]); printf("%c\n",node->attrval); } } void main(){ char data[3]={0,1,1}; struct node* node1; insert( node1,data); printnode(node1); return; } }} - coder October 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Guys check out my solution.. any input is welcome.

class Node
{
  int data;
  ArrayList<Node> children;

  Public Node(int value)
  {
      data = value;
      children = new Arraylist<Node>();
  }
}

Public void traverse(Node root)
{
  if(root ==  NULL)
      return;
  
  for(Node child:root.children)
  {
      traverse(child);
  }
  System.out.Println(root.data + " ");
}

- Anonymous October 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use preorder traversal for n array tree. similar to tree.

- dontulakapil November 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// this is a recursive question 

typedef struct Node {
	T data;
	Node *left, *right;
}


// assuming the Nary operates like any Tree then the following would be used to output values
// in C++

template <typename T>
void Nary<T>::displayAll(Node *leaf)
{
	if(leaf != 0) 		// i.e., NULL
	{
		displayAll(leaf->left);
		std::cout << leaf->data << std::endl;
		displayAll(leaf->right);
	}
}

- Chris Sullivan March 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is old, but it might be of help to few people.

public class NaryTree {

	public static void printChildren(FolderFile root){
		
		if(root==null)return;
		
		System.out.println(root.name);
		for(Iterator newfile=root.children.iterator();newfile.hasNext();){	
		FolderFile child = (FolderFile)newfile.next();
		printChildren(child);
		}
	}
	
	
	public static void main(String args []){
		
		NaryTree obj = new NaryTree();
		FolderFile root = new FolderFile("folder1");
		Set<FolderFile> children = root.children;
		FolderFile child1 = new FolderFile("child1");
		FolderFile child2 = new FolderFile("child2");
		FolderFile child3 = new FolderFile("child3");
		children.add(child1);
		children.add(child2);
		children.add(child3);
		Set<FolderFile> subchild = child1.children;
		FolderFile subchild1 = new FolderFile("subchild1");
		FolderFile subchild2 = new FolderFile("subchild2");
		FolderFile subchild3 = new FolderFile("subchild3");
		subchild.add(subchild1);
		subchild.add(subchild2);
		subchild.add(subchild3);
		
		
		printChildren(root);
		
	}

}


class FolderFile{
	String name;
	Set<FolderFile> children;

	
	public FolderFile(String name){
		this.name = name;
		this.children = new HashSet<FolderFile>();
		
	}
	
}

- nagireddy.gatla March 16, 2016 | Flag Reply


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