Блог пользователя Romok007

Help needed with a hard facebook interview problem
Автор Romok007, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Bound on the size of the tree?

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится

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

      → Ответить
»
4 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится 
#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;
}
→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    → Ответить