Amazon Interview Question for SDE1s


Country: India
Interview Type: In-Person




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

public class Node 
{
	private int value;
	private ArrayList<Node> children;
       
}

public class CheckSumProperty
{
	
	public boolean hasSumProperty(Node n)
	{
		if(n==null)
		{
			return true;
		}
		Queue<Node> q=new Queue<Node>();
		q.enqueue(n);
		while(!q.isEmpty())
		{
			Node top=q.dequeue();
			ArrayList<Node> c=top.children();
			int sum=0;
			for(Node x: c)
			{
				sum+=x.value;
				q.enqueue(x);
			}
			if(sum!=top.value)
			{
				return false;
			}
		}
	return true;
	}
}

- divm01986 June 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Time complexity: O(n+m)

- divm01986 June 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please define Sum Property

- Coder June 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- naveenrai8 June 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wouldnt this just lead to trees of infinite depth?

- Anonymous June 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Does value for each node should be equal to sum of its immediate (direct) children or all children (whole sub-trees)?

- mike August 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- naveenrai8 June 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}

- SycophantEve June 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is correct

- amnesiac September 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- puneet.sohi June 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- puneet.sohi June 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Wouldn't the answer always be false given that there will always be leaf nodes which will not have any children and the sum will add up to 0?

- Kiran June 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- zortlord June 19, 2015 | 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