Question

Goldman Sachs OA 24th oct 2021 | Set - 37

Answer 1

Here i will only be posting the Coding questions.

 

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.

 

Q2. Given a data set of N students with their names and marks. Find and arrange the students in pairs such that a pairs marks add upto a given total d.

 

Note that a student can pair with only one other student, and when multiple pairs are possible the pairs are formed with students who come earlier in the order of input.At least one pair will always be possible.

 

Contraints
3<= N <500
1<= length of names <=20

 

Input Format
The first line of input consists of two integer n and d, where n is the number of students and d is the requires total.
Next n lines each consists of a string and a number,the student's name and marks.

 

Output Format
Print only names of all possible pairs , one pair in each line.
Pairs should be printed in the order of input.

 

Sample Input:
10 150
ron 50
harry 100
naruto 150
diego 0
tom 50
jerry 100
shika 90
tenten 60
sasuke 110
gara 114

 

Output:
ron harry
naruto diego
tom jerry
shika tenten

 

									 Thanks

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;
}

 

Q2

 

#include<bits/stdc++.h>

using namespace std;

int main() {
  int n, total;
  cin >> n >> total;

  unordered_map<int, unordered_set<string>> mp;

  vector<pair<string, string>> result;

  for (int i = 0; i < n; i++) {
    string name;
    int marks;
    cin >> name >> marks;

    int req = total - marks;
    if (mp[req].size()) {
      // already found a pair
      string other = *mp[req].begin();
      mp[req].erase(other);
      result.push_back({name, other});
    } else {
      mp[marks].insert(name);
    }
  }

  for (auto &p : result) {
    cout << p.first << " " << p.second << "\n";
  }
  return 0;
}