Question

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

Answer 1

 

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

Answer 2

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