{"id":"760ea5f4-2e3e-4197-ac3d-cbb5886d03bb","name":"Minimum Number Of Software Developers","description":"1. You are given N strings which represents N different skills related to I.T field.\r\n2. You are working on a project and you want to hire a team of software developers for that project.\r\n3. There are N applicants. Every applicant has mentioned his/her skills in resume.\r\n4. You have to select the minimum number of developers such that for every required skill, there is \r\n at least one person in the team who has that skill.\r\n5. It is guaranteed that you can form a team which covers all the required skills.\r\n\r\nNote -> Check out the question video for details.","inputFormat":"A number N representing number of required skills\r\nN space separated strings \r\nA number M representing number of applicants\r\nFor every applicant : A number T representing number of skills of an applicant and then T number of space separated strings.","outputFormat":"An arraylist containing the indices of selected applicants.\r\nCheck the sample ouput and question video.","constraints":"1 &lt;= N &lt;= 16\r\n1 &lt;= length of string &lt;= 16\r\n1 &lt;= M &lt;= 60","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nvector<int>sol;\n\nvoid soultion(vector<int>& people,int nskils,int cp,vector<int>& onesol,int smask){\n \n}\n\n\nint main(){\n int n;\n cin>>n;\n\n unordered_map<string ,int>smap;\n for(int i=0;i<n;i++){\n string x;cin>>x;\n smap[x]=i;\n }\n int np;\n cin>>np;\n\n vector<int>people(np);\n\n for(int i=0;i<np;i++){\n int personskills;\n cin>>personskills;\n\n for(int j=0;j<personskills;j++){\n string skill;\n cin>>skill;\n\n int snum=smap[skill];\n people[i]=people[i]|(1<<snum);\n }\n }\n\n vector<int>soln;\n soultion(people,n,0,soln,0);\n cout<<\"[\";\n for(int i=0;i<sol.size();i++){\n if(i==sol.size()-1){\n cout<<sol[i];\n }else{\n cout<<sol[i]<<\", \";\n }\n }\n cout<<\"]\";\n\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n\tstatic ArrayList<Integer> sol = new ArrayList<>();\r\n\r\n\tpublic static void solution(int[] people, int nskills, int cp, ArrayList<Integer> onesol, int skills) {\r\n\t\t// write your code here\r\n\t}\r\n\tpublic static void main(String[] args) {\r\n\t\tScanner scn = new Scanner(System.in);\r\n\t\tint n = scn.nextInt();\r\n\t\tHashMap<String, Integer> smap = new HashMap<>();\r\n\t\tfor (int i = 0; i < n; i++) {\r\n\t\t\tsmap.put(scn.next(), i);\r\n\t\t}\r\n\t\t\r\n\t\tint np = scn.nextInt();\r\n\t\tint[] people = new int[np];\r\n\t\tfor (int i = 0; i < np; i++) {\r\n\t\t\tint personSkills = scn.nextInt();\r\n\t\t\tfor (int j = 0; j < personSkills; j++) {\r\n\t\t\t\tString skill = scn.next();\r\n\t\t\t\tint snum = smap.get(skill);\r\n\t\t\t\tpeople[i] = people[i] | (1 << snum);\r\n\t\t\t}\r\n\t\t}\r\n\r\n\t\tsolution(people, n, 0, new ArrayList<>(), 0);\r\n\t\tSystem.out.println(sol);\r\n\t\t\r\n\t}\r\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3\r\njava nodejs reactjs\r\n3\r\n1\r\njava\r\n1\r\nnodejs\r\n2\r\nnodejs\r\nreactjs","sampleOutput":"[0, 2]\r\n","questionVideo":"https://www.youtube.com/embed/5gXNMGiqQbU?end=124","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"f3e3dbef-d2b7-4f6d-b357-2ef3738e6c91","name":"Bit Manipulation For Intermediate","slug":"bit-manipulation-for-intermediate-9995","type":0},{"id":"f2167311-8bbb-4cb6-9ad3-ad7405ade03c","name":"Minimum Number Of Software Developers","slug":"minimum-number-of-software-developers","type":1}],"next":{"id":"b80d3424-cf5b-43f7-b3f6-272551bff294","name":"Minimum Number Of Software Developers MCQ","type":0,"slug":"minimum-number-of-software-developers-mcq"},"prev":{"id":"311ef428-3d57-4cdb-ad32-3d832729e99a","name":"Gray Code","type":3,"slug":"gray-code"}}}

Minimum Number Of Software Developers

1. You are given N strings which represents N different skills related to I.T field. 2. You are working on a project and you want to hire a team of software developers for that project. 3. There are N applicants. Every applicant has mentioned his/her skills in resume. 4. You have to select the minimum number of developers such that for every required skill, there is at least one person in the team who has that skill. 5. It is guaranteed that you can form a team which covers all the required skills. Note -> Check out the question video for details.

{"id":"760ea5f4-2e3e-4197-ac3d-cbb5886d03bb","name":"Minimum Number Of Software Developers","description":"1. You are given N strings which represents N different skills related to I.T field.\r\n2. You are working on a project and you want to hire a team of software developers for that project.\r\n3. There are N applicants. Every applicant has mentioned his/her skills in resume.\r\n4. You have to select the minimum number of developers such that for every required skill, there is \r\n at least one person in the team who has that skill.\r\n5. It is guaranteed that you can form a team which covers all the required skills.\r\n\r\nNote -> Check out the question video for details.","inputFormat":"A number N representing number of required skills\r\nN space separated strings \r\nA number M representing number of applicants\r\nFor every applicant : A number T representing number of skills of an applicant and then T number of space separated strings.","outputFormat":"An arraylist containing the indices of selected applicants.\r\nCheck the sample ouput and question video.","constraints":"1 &lt;= N &lt;= 16\r\n1 &lt;= length of string &lt;= 16\r\n1 &lt;= M &lt;= 60","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nvector<int>sol;\n\nvoid soultion(vector<int>& people,int nskils,int cp,vector<int>& onesol,int smask){\n \n}\n\n\nint main(){\n int n;\n cin>>n;\n\n unordered_map<string ,int>smap;\n for(int i=0;i<n;i++){\n string x;cin>>x;\n smap[x]=i;\n }\n int np;\n cin>>np;\n\n vector<int>people(np);\n\n for(int i=0;i<np;i++){\n int personskills;\n cin>>personskills;\n\n for(int j=0;j<personskills;j++){\n string skill;\n cin>>skill;\n\n int snum=smap[skill];\n people[i]=people[i]|(1<<snum);\n }\n }\n\n vector<int>soln;\n soultion(people,n,0,soln,0);\n cout<<\"[\";\n for(int i=0;i<sol.size();i++){\n if(i==sol.size()-1){\n cout<<sol[i];\n }else{\n cout<<sol[i]<<\", \";\n }\n }\n cout<<\"]\";\n\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n\tstatic ArrayList<Integer> sol = new ArrayList<>();\r\n\r\n\tpublic static void solution(int[] people, int nskills, int cp, ArrayList<Integer> onesol, int skills) {\r\n\t\t// write your code here\r\n\t}\r\n\tpublic static void main(String[] args) {\r\n\t\tScanner scn = new Scanner(System.in);\r\n\t\tint n = scn.nextInt();\r\n\t\tHashMap<String, Integer> smap = new HashMap<>();\r\n\t\tfor (int i = 0; i < n; i++) {\r\n\t\t\tsmap.put(scn.next(), i);\r\n\t\t}\r\n\t\t\r\n\t\tint np = scn.nextInt();\r\n\t\tint[] people = new int[np];\r\n\t\tfor (int i = 0; i < np; i++) {\r\n\t\t\tint personSkills = scn.nextInt();\r\n\t\t\tfor (int j = 0; j < personSkills; j++) {\r\n\t\t\t\tString skill = scn.next();\r\n\t\t\t\tint snum = smap.get(skill);\r\n\t\t\t\tpeople[i] = people[i] | (1 << snum);\r\n\t\t\t}\r\n\t\t}\r\n\r\n\t\tsolution(people, n, 0, new ArrayList<>(), 0);\r\n\t\tSystem.out.println(sol);\r\n\t\t\r\n\t}\r\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3\r\njava nodejs reactjs\r\n3\r\n1\r\njava\r\n1\r\nnodejs\r\n2\r\nnodejs\r\nreactjs","sampleOutput":"[0, 2]\r\n","questionVideo":"https://www.youtube.com/embed/5gXNMGiqQbU?end=124","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"f3e3dbef-d2b7-4f6d-b357-2ef3738e6c91","name":"Bit Manipulation For Intermediate","slug":"bit-manipulation-for-intermediate-9995","type":0},{"id":"f2167311-8bbb-4cb6-9ad3-ad7405ade03c","name":"Minimum Number Of Software Developers","slug":"minimum-number-of-software-developers","type":1}],"next":{"id":"b80d3424-cf5b-43f7-b3f6-272551bff294","name":"Minimum Number Of Software Developers MCQ","type":0,"slug":"minimum-number-of-software-developers-mcq"},"prev":{"id":"311ef428-3d57-4cdb-ad32-3d832729e99a","name":"Gray Code","type":3,"slug":"gray-code"}}}
plane

Editor


Loading...

Minimum Number Of Software Developers

easy

1. You are given N strings which represents N different skills related to I.T field. 2. You are working on a project and you want to hire a team of software developers for that project. 3. There are N applicants. Every applicant has mentioned his/her skills in resume. 4. You have to select the minimum number of developers such that for every required skill, there is at least one person in the team who has that skill. 5. It is guaranteed that you can form a team which covers all the required skills. Note -> Check out the question video for details.

Constraints

1 <= N <= 16 1 <= length of string <= 16 1 <= M <= 60

Format

Input

A number N representing number of required skills N space separated strings A number M representing number of applicants For every applicant : A number T representing number of skills of an applicant and then T number of space separated strings.

Output

An arraylist containing the indices of selected applicants. Check the sample ouput and question video.

Example

Sample Input

3 java nodejs reactjs 3 1 java 1 nodejs 2 nodejs reactjs

Sample Output

[0, 2]

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode