Question

Goldman Sachs | OA | SDE -1 | 2022 | INDIA | Set-11

Answer 1

Q1. Consider a binary tree of N nodes ( 1 Root and N-1 descendants). Each node X is related to root node by a relation such as L,R,LL,LR ... and so on. where X is left (L) to Root, or right to Root (R), or left-left (LL) or left-rigth (LR) to root and so on. Write a program to find the sum of all magic parents in the tree.

 

Magic parents are those nodes whose one child is a factor of the other child. The nodes having only one child can never be Magic parents.

 

Constraints:- 3<=N<=100

 

Input format:
The first line of input contains an Integer, N,The number of nodes in the tree.
The second line of input contains an integer , Root, which is the root of the tree.
The next N-1 lines of input contains a String ,and an integer X , separeted by a single white space, where X is a node in tree and S is the relation between Root and X.

 

Sample Input
6
11
L 14
R 28
LL 7
LR 8
RR 14

 

Sample Output
11

 

Based on the input , the tree can be constructed as follows :-

 

In the above tree only Magic parent is 11 as its children are 14 and 28,where 14 is factor of 28.
Hence output is 11.

Answer 2

Q1
O(n) Time and Space

 

#include<bits/stdc++.h>

using namespace std;

class Node {
 public:
  int value;
  Node* left;
  Node* right;

  Node(int v = -1, Node* l = nullptr, Node* r = nullptr)
      : value(v), left(l), right(r) {}
};

class BinaryTree {
 public:
  Node* root;

  BinaryTree(int rv) { root = new Node(rv); }

  void addNode(string relation, int val) {
    Node* ptr = root;
    int rl = relation.size();
    for (int i = 0; i < rl - 1; i++) {
      if (relation[i] == 'L')
        ptr = ptr->left;
      else
        ptr = ptr->right;
    }

    if (relation.back() == 'L')
      ptr->left = new Node(val);
    else
      ptr->right = new Node(val);
  }
};

int sumOfMagicParents(Node* root) {
  if (root == nullptr) return 0;

  int sum = 0;
  queue<Node*> q;
  q.push(root);

  while (!q.empty()) {
    Node* curr = q.front();
    q.pop();

    if (curr->left != nullptr && curr->right != nullptr) {
      // check if curr is magic parent
      int leftVal = curr->left->value;
      int rightVal = curr->right->value;

      if (max(leftVal, rightVal) % min(leftVal, rightVal) == 0) {
        sum += curr->value;
      }
    }

    if (curr->left != nullptr) q.push(curr->left);
    if (curr->right != nullptr) q.push(curr->right);
  }

  return sum;
}

int main() {
  int n;  // number of nodes
  cin >> n;
  int rootVal;
  cin >> rootVal;

  BinaryTree bt(rootVal);

  for (int i = 0; i < n - 1; i++) {
    string rel;
    int val;
    cin >> rel >> val;
    bt.addNode(rel, val);
  }

  cout << sumOfMagicParents(bt.root);

  return 0;
}