Minimum Number Of Software Developers

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

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.
Input Format 
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 Format 
An arraylist containing the indices of selected applicants.
Check the sample ouput and question video.
Question Video
Constraints 
1 <= N <= 16
1 <= length of string <= 16
1 <= M <= 60
Sample Input 
3
java nodejs reactjs
3
1
java
1
nodejs
2
nodejs
reactjs
Sample Output 
[0, 2]


  • Editorial

    In this problem, we are provided with N skills and we are N employees with their respective skills, we need to tell how to select the employees so that they contain all N skills and their count is minimum.

    For this we need to generate all the combinations of employees which is the same as getting all the subsequences of N employees, hence total subsequences will be 2n. Now for every subsequence, we need to check that does this subsequence has relevant skills or not.

    We can optimize the search operation which checks that the given subsequence satisfies N skills with the help of bit manipulation. This can be achieved by assigning all N skills as specific bit positions, so our question now turns out to find the minimum number of employees for which all N bits are set.

    This can be achieved by finding all subsequences and then checking for all N set bits by comparing res == (1 << N) - 1.

    Time Complexity: O(2n)

    The time complexity for the function is exponential as generating subsequences is an exponential task.

    Space Complexity: O(n)

    The space complexity for the function is linear as we maintaining ArrayList for storing the result.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name