Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
2,119 views
in Online Assessments by Expert (111,530 points) | 2,119 views

1 Answer

0 like 0 dislike
Best answer

MATCHMAKING - 1
 

Description

 

Intuit receives calls from it's customers regarding various topics and in various languages. Intuit wants to match these customers to experts who have knowledge on exactly the same topic and can speak in that language. Based on the predictions, Intuit had N experts ready to take the calls, each expert knows exactly one topic and can speak exactly one language proficiently. On a particular day, M customers end up calling for their problems. A customer is unhappy if it is not matched to the expert who know about the topic they wish to enquire about and know the language they talk in. Can you help the team at Intuit assign the customers to experts, such that the minimum number of customers return unhappy
 

 

Constraints

 

1<= N <= 10^5
1<= M <= 10^5

 

Input Format

 

The first line contains N, the count of experts at Intuit.

 

Next N line contains 2 space seperated strings, the first denoting the topic the expert knows, and the second denoting the language they know The next line contains M. the count of customers calling Intuit.

 

Next M line contains 2 space seperated strings, the first denoting the topic the customer wants to enquire about, and the second denoting the language they speak in

 

Output Format

 

Return an integer representing the number of
customer which went unhappy with Intuit

 

Sample Input

4 
Tax English 
Crypto Hindi 
Tax Spanish 
SF English 
4 Crypto Hindi 
Tax Spanish 
Crypto Spanish 
Tax Spanish 

Sample Output

2 

Explanation

Crypto Spanish - Intuit does not have a crypt o expert who can work in Spanish. Tax Spanish - Intuit only has a single expert who can do tax and work in Spanish 

Solution :

#include <bits/stdc++.h>
using namespace std;


int main()
{

    Solution s = Solution();
    int n;
    cin>>n;
    unordered_map<string,vector<pair<string,int>>> mp;

    for(int i=0;i<n;i++){
        string a,b;
        cin>>a>>b;
		//map of pair pushing a new pair with same key and default flag value 0
        mp[a].push_back({b,0});
    }

    int m;
    cin>>m;

    vector<pair<string,string>> v;
    for(int i=0;i<m;i++){
        string a,b;
        cin>>a>>b;
		//taking all the testcase inputs 
        v.push_back({a,b});
    }

    int ans=0;

//iterating over all the testcases
    for(auto &c:v){
        auto it =mp.find(c.first);
		//if entry is found in map then we will search that language in pair vector by iteration
        if(it!=mp.end()){
            int j=0;
            for(;j<it->second.size();j++){
				//if the desired lang is present 
                if(it->second[j].first==c.second and it->second[j]==0)
                {
					//mark it as visited and cannot traverse it again
					//since given in question one expert can be occupied with only one customer
                    it->second[j].second=1;
                    break;
                }
            }
			//if we traversed the whole map and cannot find the matching language from testcase
			//then also customer unsatisfied
            if(j==it->second.size())ans++;
        }
		else
		ans++;
		//in this case if the lang is not present in the map then the customer is unsatisfied 
		// add the ans
			
    }

   cout<<ans<<"/n";
    
   return 0;
}

 

by Expert (111,530 points)

Get best answers to any doubt/query/question related to programming , jobs, gate, internships and tech-companies. Feel free to ask a question and you will receive the best advice/suggestion related to anything you ask about software-engineering , development and programming problems .