Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
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;
}
}
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)
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.
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;
}
}
return totalWeight;
}
}
balanced max heap will be the answer
- gupta ji March 11, 2016