## Amazon Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

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

balanced max heap will be the answer

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

sort all the numbers and construct the tree level by level in decreasing order.

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

Create a binary heap using max heapify, that way all the higher elements will appear in the top levels, causing the tree weight to minimum.

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

balanced max heap created by those values should be the answer. the heigher value should be at least depth.

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

Post Order Traversal and calculate the min Weight

``````public int? GetMinWeight(TreeNode root)
{
if (root == null)
return null;

int minWeight = int.MaxValue;
GetMinWeight(root, 1, ref minWeight);
return minWeight;
}

private int GetMinWeight(TreeNode node, int deep, ref int minWeight)
{
if (node.Left == null)
return 0;

int leftWeight = GetMinWeight(node.Left, deep + 1, ref minWeight);
int rightWeight = GetMinWeight(node.Right, deep + 1, ref minWeight);
int weight = node.Value * deep + leftWeight + rightWeight;

minWeight = Math.Min(minWeight, weight);
if (node.Left != null)
minWeight = Math.Min(minWeight, leftWeight);
if (node.Right != null)
minWeight = Math.Min(minWeight, rightWeight);

return weight;
}
}``````

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

I had the same thought that a max heap would provide the minimum answer. After testing it out I realized that there are some heap arrangements that are better than others: e.g. for this list : [1,2,3,8,10,20,43] both these arrangements are heaps:
1. [43, 20, 8, 2, 10, 3, 1] with weight 60
2. [43, 20, 10, 2, 3, 1, 8] with weight 58

So I think the solution is to sort the array in reverse order and treat that as a binary tree (children on node i are 2*i+1 and 2*i+2) .

In Python:

``````def compute_weight(tree,root,depth):
if root > len(tree) - 1:
return 0
l = compute_weight(tree, 2*root+1, depth+1)
r = compute_weight(tree,2*root+2, depth+1)
return tree[root]*depth + l + r

if __name__ == "__main__":
nums = [60, 10, 43, 8, 5, 20, 3, 2, 2, 1, 1]
nums.sort() #sort the array
nums = nums[::-1] #reverse so that that it is sorted max->min
print compute_weight(nums,0,0)``````

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

inki I agree and here is the reason from math stand point of view:
lets take the lets take the "lowest branch of the tree node a and two children b and c. lets say a has depth n then b and c have depth (n + 1) then the weight of this branch is a*n + (b + c)*(n + 1). where a > b and a > c. Now lets swap a and b then
weight of the tree will be b*n + (a + c)*(n + 1) so now lets compare the weights
a * n + (b+c)*(n + 1) and b*n + (a + c)*(n + 1)
opening the brakets from both sides and making all the nessesary manipulations will see that from the left side only b will be left and from the right only a

b > a this means that if highest values need to be at the lowest possible level this can be achieved by constructing max heap from array which is sorted in in descending order.

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

I don't know much about balanced max heap (I am studying about it now) but here is my attempt at it. I assume that min weight will always be at a node which has 2 leafs under it. If you go any higher - the weight will only increase.

``````public class SmallestWeightTree {
private static int height = 0, weight = Integer.MAX_VALUE;
private static Node nodeMinWeight = null;
public static int weigh(Node node, int level) {
int leftWeight = 0, rightWeight = 0, selfWeight = 0, totalWeight = 0;
if(node.hasLeft()) {
leftWeight = weigh(node.getLeft(), level + 1);
}
if(node.hasRight()) {
rightWeight = weigh(node.getRight(), level + 1);
}
if(node.isLeaf()) {
height = height < level ? level : height;
}
selfWeight = level * node.getValue();
totalWeight = leftWeight + rightWeight + selfWeight;

if(level == height - 1) { // At the level right above a leaf, time to compare weights
if(totalWeight < weight) {
weight = totalWeight;
nodeMinWeight = node;
}
}
}
}``````

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

Can someone please explain what a balanced max heap is? Please note I know what a max heap is.

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.

### 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.