Amazon Interview Question SDE1s
Country: India
Interview Type: Written Test
DFS is good. just elaborate if it's a graph. we probably don't have a root.
...O...O
../..\../..\
O...O...O
in the above graph, we'll need to check every node for its children. and you can meet the same node more than once like in the example and it may not be a cycle. so only visited flag is not enough.
we can add one more flag for detecting cycles in the recursion phase.
so just add the stack flag in the code.
boolean isLoop(Node root,HashMap hash)
{if(!root.isVisited){
root.isVisited=true;
bool isloop=false;
hash.put(root,true);
for(int i=0;i<root.Childs.Count();i++)
{
if(hash.get(root.Childs[i])==true)
return true;
else if( !root.childs[i].isVisited&&isLoop(root.childs[i],hash))
return true;
}
hash.put(root,false);}
return false;
}
int main(){
HashMap hash=new ....;
for(Node x:all nodes){
if(isLoop(x,hash)) return true;}
return false;}
I would say its best to use data structure like this
struct t {
int n;
struct t *kids;
struct t *siblings;
}
Using above structure, while constructing the tree assume kids are always on left of a node and siblings on the right side of a node. This would look like a binary tree.
Hence at the end you can use DFS to check whether cycle is there or not.
Correct me if I am wrong.
struct NTreeNode
{
vector<NTreeNode<T>*>* chlildren; // max length of vector = N
T data;
};
@Gupt Except binary tree, to traverse any other tree we need to visit more than once. So it seems it may not possible to say there is a loop/cycle using that logic.
template<class T>
void NTree<T>::Preorder(NTreeNode<T>* node)
{
if (!node) return;
cout << node->m_data;
vector<NTreeNode<T>*>::iterator iter;
iter = node->m_listChildren.begin();
for (; it != node->m_listChildren.end() ;it++)
{
Preorder(*it);
}
}
@Dinesh, I dont think so, a node will be visited only once. Anything to support your argument?
class node
{
int vals[N-1];
node children[N];
node parent;
}
Add one extra member for node structure "Node *Parent"
Write a function which takes node and it's parent as args.
Find_Loop(Node *root, Node *Par) //par=NULL for root node
{
if ( root->parent != par )
{
print "Loop found";
exit;
}
//visit the node
for(int i=0;i<N && root[i+1]!=NULL ;i++)
Find_Loop( root->children[i], root);
}
For every recursive call we will pass child node and current node(as parent) as args.
Please correct me if anything is wrong.
#include<conio.h>
#include<stdio.h>
void MergesortedArray(int a[],int b[],int n,int m)
{
int i=n-1,j=m-1,k=m+n,temp;
//int ar1[4]={5,15,30,50}; int ar2[7]={25,35,45};
while(i != -1 && j!=-1)
{
if(b[j]>a[i])
{
b[(--k)]=b[j];
j--;
}
else
{
b[(--k)]=a[i];
i--;
}
}
if(n>m)
{
while(i!=-1)
{
b[--k]=a[i];
i--;
}
}
for(i=0;i<7;i++)
{
printf("%d ",b[i]);
}
}
int main()
{
int ar1[4]={5,15,30,50};
int ar2[7]={25,35,45};
MergesortedArray(ar1,ar2,4,3);
}
For those who(including myself) don't know what is N-ary Tree, its a simple tree where each node can have N child nodes.
Data Structure I use is
Class Node { int value; bool isVisited; ArrayList<Node> childs; }Function to find if it has loop or not, I think it should work i havent tested it though.
- billu March 11, 2013boolean isLoop(Node root) { root.isVisited=true; bool isloop=false; for(int i=0;i<root.Childs.Count();i++) { if(root.Childs[i].isVisited==true) return true; else isloop=isLoop(root.childs[i]); if(isloop==true) return true; } return isloop; }