Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Node
{
int data;
vector<Node*> children;
};
Node* _insert(Node *root, int n)
{
if( root==NULL )
{
root = new Node;
root->data = n;
for( int i=0; i<n; i++ )
children.push_back(NULL);
return root;
}
for( int i=0; i<root->children.size(); i++ )
{
Node *x = _insert(children[i], n);
if( x==NULL ) // Could not isert under children[i], try to insert as/under next child
continue;
if( x==children[i] ) // Inserted under children[i]
return root;
else
{
children[i] = x;
return root;
}
}
return NULL;
}
Node* insert(Node* root, int n)
{
Node* new_root = _insert(root, n);
return ( new_root == NULL )?root:new_root;
}
Added running code
#include<malloc.h>
#define N 4
struct node{
int data;
int number;
struct node* (child[N]);
};
struct node* construct(int arr[],int start, int end)
{
struct node* root=(struct node*)malloc(sizeof(struct node));
if(arr[start]==0)
{
root->data=0;
printf("build node %d\n",root->data);
return root;
}
int i;
static int index=0;
root->data=arr[start];
printf("build node %d\n",root->data);
for(i=0;i<arr[start];i++){
printf("called (arr,%d,%d)\n",index+1,end);
root->child[i]=construct(arr,++index,end);}
printf("finally returning root:%d\n",root->data);
return root;
}
class Node
{
public int Value;
public Node[] children;
public Node(int c)
{
Value = c;
children = new Node[c];
}
}
static void Main(string[] args)
{
Node node = FormTree( "3221001000");
}
static Node FormTree(string str)
{
int i = 0;
return FormTree(str, ref i);
}
static Node FormTree(string str, ref int i)
{
int c = str[i++] - '0';
Node node = new Node(c);
for (int a = 0; a < c && i < str.Length; ++a)
{
node.children[a] = FormTree(str, ref i);
}
return node;
}
- Anonymous October 20, 2011