Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
I think first you need to find the distance of the left most node from the root, and then call the function comptute_vsums() by passing that number, rather than zero. Actually in above case array index would become negative in the next call.
sounds like you need to do asm's solution for each node of the tree. alternatively:
1. post order traversal add yourself to a stack with turn_coutn 0
2. your parent adds +1 to all elements in stack from left return
your parent adds -1 to all elements in stack from right return
3. now everyone who overlaps with parent must have 0 turn_count
sum these values, print and goto step 2
paper code:
// push a node with turn count
push(turn_count, node_value) {
temp = malloc(sizeof(stacknode));
temp->value = node_value;
temp->turn_count = turn_count;
stack[stack_top++] = temp;
}
// modify turn count, return ones that sum to 0
stack_op (int operator, int stack[], int stack_top) {
for (i=0; i<stack_top; i++) {
stack[stack_top]->turn_count =
stack[stack_top]->turn_count+operator;
if (stack[stack_top]->turn_count == 0)
sum += stack[stack_top]->value;
}
return sum;
}
walk(node* root, int stack[], int stack_top) {
if (root == NULL)
return;
walk(root->right, stack_top);
sum += stack_op(stack, +1, stack_top);
walk(root->left, stack_top);
sum += root->value + stack_op(stack, -1, stack_top);
print(sum);
push(root->value, 0, stack_top);
}
as my title reads =(
sounds like you need to do asm's solution for each node of the tree. alternatively:
1. post order traversal add yourself to a stack with turn_coutn 0
2. your parent adds +1 to all elements in stack from left return
your parent adds -1 to all elements in stack from right return
3. now everyone who overlaps with parent must have 0 turn_count
sum these values, print and goto step 2
paper code:
// push a node with turn count
push(turn_count, node_value) {
temp = malloc(sizeof(stacknode));
temp->value = node_value;
temp->turn_count = turn_count;
stack[stack_top++] = temp;
}
// modify turn count, return ones that sum to 0
stack_op (int operator, int stack[], int stack_top) {
for (i=0; i<stack_top; i++) {
stack[stack_top]->turn_count =
stack[stack_top]->turn_count+operator;
if (stack[stack_top]->turn_count == 0)
sum += stack[stack_top]->value;
}
return sum;
}
walk(node* root, int stack[], int stack_top) {
if (root == NULL)
return;
walk(root->right, stack_top);
sum += stack_op(stack, +1, stack_top);
walk(root->left, stack_top);
sum += root->value + stack_op(stack, -1, stack_top);
print(sum);
push(root->value, 0, stack_top);
}
void vertical_sum(Node n,int sum[],int column)
{
if(n==NULL) return ;
sum[column]+=n->v;
vertical_sum(n->l,sum,column+1);
vertical_sum(n->r,sum,column-1);
}
void vertical_init(Node root)
{
int h=height(root);
int *sum=new int[h+1];
h=pow(2,h-1)/2;
vertical_sum(root,h);
for(int i=0;i<=2*h;i++)
cout<<sum[i]<<" ";
return ;
}
void vertical_sum(TreeNode* root)
{
if(root == NULL)
return NULL;
stack<TreeNode*> s;
stack<int> s1;
int index = 0;
TreeNode* currentNode = root;
hash_map<int, int> sum_map;
while(true)
{
while(currentNode)
{
s.push(currentNode);
currentNode = currentNode->left;
s1.push(index--);
}
if(s.size() != 0)
{
currentNode = s.top();
index = s1.top();
if(sum_map.find(index) != sum_map.end())
sum_map[index] += currentNode->value;
else
sum_map[index] = 0;
s.pop();
s1.pop();
if(currentNode->right != NULL)
{
++index;
}
currentNode = currentNode->right;
}
else
break;
}
}
public abstract class AbstractTree {
private Integer value;
public AbstractTree(Integer value) {
this.setValue(value);
}
public List<Integer> verticalSums() {
LinkedList<Integer> result = new LinkedList<Integer>();
this.verticalSums(result, 0);
return result;
}
protected abstract int verticalSums(LinkedList<Integer> res, int nextIndex);
//getters and setters...
}
------------------------
public class Leaf extends AbstractTree {
public Leaf(Integer value) {
super(value);
}
protected int verticalSums(LinkedList<Integer> res, int index) {
if (index < 0) {
res.addFirst(this.getValue());
return 0;
} else {
if (index + 1 > res.size()) {
res.add(this.getValue());
} else {
res.set(index, this.getValue() + res.get(index));
}
return index;
}
}
}
------------------------
public class Tree extends AbstractTree {
private AbstractTree right;
private AbstractTree left;
public Tree(AbstractTree left, AbstractTree right, Integer value) {
super(value);
this.setRight(right);
this.setLeft(left);
}
protected int verticalSums(LinkedList<Integer> res, int index) {
int leftRes = this.getLeft().verticalSums(res, index - 1);
int result;
if (leftRes == 0) {
if (res.size() == 1) {
res.add(this.getValue());
} else {
res.set(1, this.getValue() + res.get(1));
}
result = 1;
} else {
if (leftRes + 1 == res.size()) {
res.add(this.getValue());
} else {
res.set(leftRes + 1, this.getValue() + res.get(leftRes + 1));
}
result = leftRes + 1;
}
this.getRight().verticalSums(res, leftRes + 2);
return result;
}
// getters and setters...
}
// Note: trees should be created with Leaf instances and not null values.
if I understand the problem correctly, we just need to count the number of turns (left / right) while traversing a binary tree. The solution with additional storage:
- pavel.em October 18, 2011std::hast_map< int, int > vsums; // the hash containing vertical sums void compute_vsums(node *t, int n) { if(t == 0) return; // one turn to the left corresponds to n-1 // turn to the right corresponds to n+1 vsums[n] += t->val; compute_vsums(t->left, n-1); compute_vsums(t->right, n+1); } call compute_vsums(root, 0);