Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
sum property is as follows:
For every node, value stored in it must be equal to sum of values in left and right child. Consider value as 0 for NULL children.
e.g. parent = 10, left child = 8 and right child = 2 then sum property satisfied. parent = left + right. in this case return true
e.g. parent = 10, left child = 7 and right child = 2 then sum property failed. parent != left + right. in this case return false
typedef struct NAryTree
{
int content;
int* children;
}tNAryTree, *tNArayTreePtr;
int sumProperty(tNArayPtr root)
{
if( root == NULL)
return 1;
int isSumPropertySatisfied = 1;
int i=0;
//iterate over all the children of this node
for(; i<n; i++)
{
//if any children is null, skip
if(root->children[i] == NULL)
continue;
isSumPropertySatisfied = isSumPropertySatisfied && sumProperty(root->children[i]);
}
return isSumPropertySatisfied;
}
please correct if i did anything wrong
I feel like it's close to correct, but am I wrong in thinking this function doesn't actually do anything as is? It doesn't seem to be able to return anything but one. I think you forgot to check the sum property.
Shouldn't it be something more like:
typedef struct NAryTree
{
int content;
int* children;
}tNAryTree, *tNArayTreePtr;
int sumProperty(tNArayTreePtr root)
{
int sum = 0;
if (root == NULL)
return 1;
for (int i = 0; i < n; ++i) {
sum += children[i].content;
}
int isSumPropertySatisfied = 0;
int i = 0;
//iterate over all the children of this node
if (sum == content) {
isSumPropertySatisfied = 1;
for (; i < n && isSumPropertySatisfied; i++)
{
//if any children is null, skip
if (root->children[i] == NULL)
continue;
isSumPropertySatisfied = isSumPropertySatisfied && sumProperty(root->children[i]);
}
}
return isSumPropertySatisfied;
}
For every node N, you will check if the sum of its children. If the sum matches the parent, this node follows the Sum Property. Apply a recursive solution on all its children. Where ever we find that the Sum Property is not followed, we checking and return false.
class node
{
//each node has 3 childers
//to indicate leaf node, its first child is NULL
public:
node();
node(int _data);
int data;
node * childern[3];
};
bool isSumProp(node * input_node)
{
node * parent = input_node;
//check if leaf node
if(parent->childern[0] == NULL)
{
cout << "tis but a leaf node" << endl;
}
int sum_P = parent->data;
cout << "Parent sum: " << sum_P << endl;
int sum_C = 0;
int i = 0;
node * child = parent->childern[i];
while( (i < 3) && (sum_P > sum_C) )
{
sum_C += child->data;
if(sum_P == sum_C)
{
cout << "This node follows Sum Property "<< endl;
return true;
}
i++;
child = parent->childern[i];
}
cout << "This node DOES NOT follows Sum Property "<< endl;
return false;
}
bool findSumProp(node *current)
{
if(current->childern[0] == NULL)
{
cout << "Leaf node" << endl;
return false;
}
node *curr = current;
if( !isSumProp(curr) )
{
cout << "array does not follow Sum Property" << endl;
return false;
}
findSumProp(curr->childern[0]);
findSumProp(curr->childern[1]);
findSumProp(curr->childern[2]);
return true;
}
How's about non-recursive... Still O(n) complexity but, unfortunately O(n) memory due to the N-ary-ness.
public static class NArayNode{
NArayNode[] children;
int value;
}
public static boolean isSumPropertyMet(NAryNode root){
if(root == null){
throw new NullPointerException("\"root\" may not be null");
}
Stack<NArayNode> nodesToExplore = new Stack<NAryNode>();
nodesToExplore.push(root);
while(!nodesToExplore.isEmpty()){
NAryNode node = nodesToExplore.pop();
int childSum = 0;
for(NArayNode child : node.children){
nodesToExplore.push(child);
childSum += child.value;
}
if(childSum != node.value){
return false;
}
}
return true;
}
- divm01986 June 18, 2015