Romok007's blog

Help needed with a hard facebook interview problem
By Romok007, history, 4 years ago, In English

Given a binary tree, return the minimum number of edits to make the value of each node equal to the average of its direct children's. Note that you can only update the value of each tree node, and changing the tree structure is not allowed.

"average of its direct children's" means the average of left and right children.

1. If the left(right) children doesn't exist, then just let the root value equal to the value of its right(left) children.

2. If the root is leaf, then the criteria is always met for this node.

3. It doesn't matter if the value is int or float. We can use float.

Sample 1 :

        2
       / \
      0   2
         / \
        0   2
           / \ 
          0   1
             / \
            0   1
               / \
              0   1

Output : 5

Sample 2 :

         2
          \
           2
            \
             2
              \
               1
                \
                 1
                  \
                   1

Output : 3

  • Vote: I like it
  • +14
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Bound on the size of the tree?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am unable to figure out even a brute force solution. So a brute force solution can be helpful. On top of that as it was an interview I am unaware of the bounds.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Hey I have a gut feeling that it can be solved using rerouting technique with dp. Have you tried it yet?

      → Reply
»
4 years ago, # |
  Vote: I like it -15 Vote: I do not like it 
#include <algorithm>
struct Node {
  double val;
  Node* l;
  Node* r;
};
const double EPS = 1e-9;
bool isSame(double a, double b) { return std::abs(a - b) < EPS; }
double recurse(Node* v, int& count) {
  double avg;
  if (v->l == nullptr && v->r == nullptr) {
    return v->val;
  } else if (v->l == nullptr && v->r != nullptr) {
    avg = recurse(v->r, count);
  } else if (v->l != nullptr && v->r == nullptr) {
    avg = recurse(v->l, count);
  } else {
    avg = (recurse(v->l, count) + recurse(v->r, count)) / 2;
  }
  if (!isSame(v->val, avg)) {
    count++;
  }
  return avg;
}
int answer(Node* v) {
  int count;
  recurse(v, count);  // stack overflow
  return count;
}
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Consider a stick tree that goes 2->2->1. The answer should be 1 but your code returns 2.

    → Reply