Object-oriented programming offers a sustainable way to write spaghetti code. It lets you accrete programs as a series of patches.
Minimum Number of Software Developers
Welcome back, dear reader. So, let's not waste any time and directly jump into the question as we are really excited about this question. Here, you will see how bit manipulation can be of a little use in our daily lives too. So, let us say that you are working on a project and you require a team to build something big. So, what will you do? Obviously, you will hire a team of software developers who will work on the project. Now, let us say that you require 5 skills and they are node.js, react.js, mongoDB, java and angular. You start the hiring procedure and there are 4 applicants (say). So, each applicant has a skill as shown in the image below:
So, being an employer in this case, you will want to hire less people (so that your revenue is less) but, you want all the skills in the people you hire. This is the question. In the above image, we can clearly see that if we hire the 0th and the 2nd applicant, we will get all the skills. So, the answer in this case will be [0,2] and we have hired the minimum candidates and fulfilled all the skills.
So, we hope that you have understood the question properly. We request you to watch the MINIMUM NUMBER OF SOFTWARE DEVELOPERS VIDEO to understand the question completely and clear your doubts if any. We request you try to solve this problem on your own and then refer to the solution.
Time Complexity: O(2n) where n is the number of developers that have applied for the job.
Space Complexity: O(h) where h is the height of the recursion stack.
Algorithm:
We will create a mapping for every skill with a bit. For instance, in the above image, let us take node.js as 0, react.js as 1, mongoDb as 2, java as 3 and angular as 4. This means that we will have a number of size 5 bits for each developer. As in the image, the first developer has only 2 skills i.e. java and angular which are 3rd and 4th bit. So, if the bits count start from right i.e. the MSB and move to the left i.e. the MSB then the 0th developer will have a mapping of 11000. (Have a look at the image below to understand this)
After creating such bitmaps for every developer, we actually have to select the minimum number of developers. So, we have to select the smallest subsequence of developers whose bitmaps when undergoing the OR operation, give all the set bits.
The obtaining of the minimum subsequence will be done using recursion. We will return from the recursion as soon as we get any subsequence for which the bitmap has all the bits as set bits.
Explanation :
Let us take the above example only and try to discuss the way to solve this problem. So, we will map each skill to a bit number as shown in the diagram below:
What does this mapping signify? This signifies the bit number in the skills bitmap of each developer. For instance, we know from img-1 that the first developer has the skills "java" and "angular". These skills are numbered 3 and 4 in the map. So, the skills bitmap for the 0th developer will be like:
So, in this way, we can have a skill bitmap for every developer. So let's try to build those skill bitmaps based on the skills a developer has:
You may refer to the solution video to understand the above explained section if you have any doubts about it.
So, we now have the skills bitmaps for every developer. Now the question is, how do we decide the minimum number of developers we wish to hire and also how do we decide who to hire?
So, let us think about this. If you consider two developers then how will you see what all skills have they covered? Say, we hire developer 0and developer 1 in this case.. So, the developer 0 has the skills java and angular and the developer 1 has the skills mongoDB, node.js and java. So, should these two be hired together or not? See, java is common in both of them, so we have covered the skill of java. Also, developer 0 knows angular and developer 1 knows node.js and mongoDb. So, we have covered those skills as well. But, none of them have react.js as their skill and this is the missing skill.
So, even if the skill is present with one developer or with both the developers, we have considered the skill as we just want the skills to be fulfilled. If all the developers lack the same skill, that skill will not be present in any one of them. What does this sound to you?
This sounds like the logical OR to us, right? If we see the skill bitmap for developer 0 (from img-5), it is 00011 and the skill bitmap of developer 1 is 10110. If we take OR of both of them we get:
Now, if you check the skills mapping, you will see that the skill corresponding to index 1 is react.js which is not present in both of these developers. So, these two developers cannot be hired. Now, this does not mean that developer 1 and developer 0 are out of the race and we will choose the minimum number of developers from the remaining applicants. This just means that we cannot select the developer 0 and the developer 1 together. Either we need another developer or it might happen that only one of them might get selected or it might even happen that none of them gets selected.
So, now we know that we have to take the logical OR of the skill bitmaps so that we can add up the skills of individual developers.
Can you think of anything that we can do? If you think carefully, we are selecting the combinations of developers like we tried one combination of 0th and 1st developer. So, we can say that we are trying the subsequences of developers and we have to select the subsequence of minimum length such that the bitmap for that subsequence has all the set bits.
So, let us try this out with the help of a recursion tree. Initially, we have not selected any developer and thus the skills bitmap will contain all zeroes. We will keep developers at the levels of the tree and when the skill bitmap becomes completely set, we will return from the recursion.
So, at the 0th level, we have developer 0. So, we have two options, either to choose him/her or not to choose him/her. If we choose him/her, the skill bitmap will be modified from all the unset boots to the skill bitmap which will be the logical OR of the previous bitmap (i.e. 00000 since we said all unset bits as no developer was selected) and the bitmap of the currently selected developer. This is shown in the image below:
So, at the next level, we will again have two options but this time for developer 1. If we choose him/her, we will take the logical OR of his//her skill bitmap with the skill bitmap that we got from the previous level.
Now let us do the same for the third level.
In the above image, you can see that we have got some answers where we have already got all the skills.Those combinations are if we select the 0th developer as well as the 1st developer as well as the 2nd developer. The other combination is selecting the 0th developer and the second developer. So, the minimum out of these two can be our potential answer i.e. [0,2] when we select the 0th and the 2nd developer is our potential answer. What potential answer? Why is it not our final answer?
This is because we can have a developer who might have all the skills. So, we will select only that one developer. So, it is only the potential answer. Now, let us do the procedure for the last and the fina developer as well.
So, we have shown all the answers that we are getting. Out of these answers, the minimum developers answer is when we select the 0th developer and the 2nd developer.
So, we hope that you have understood the complete procedure. To summarize, we make the mappings for every skill and then the bitmaps for every developer and then we are selecting the minimum length subsequence when the bitmap becomes completely set.
You may refer to the solution video to understand the above procedure completely. Now that we have understood the complete procedure, let us write the code for it.
import java.io.*;
import java.util.*;
public class Main {
static ArrayList< Integer> sol = new ArrayList< >();
public static void solution(int[] people, int nskills, int cp, ArrayList< Integer> onesol, int skills) {
if(cp == people.length){
if(skills == ((1 << nskills) - 1)){
if(onesol.size() < sol.size() || sol.size() == 0){
sol = new ArrayList< >(onesol);
}
}
return;
}
solution(people, nskills, cp + 1, onesol, skills);
onesol.add(cp);
solution(people, nskills, cp + 1, onesol, (skills | people[cp]));
onesol.remove(onesol.size() - 1);
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
HashMap< String, Integer> smap = new HashMap< >();
for (int i = 0; i < n; i++) {
smap.put(scn.next(), i);
}
int np = scn.nextInt();
int[] people = new int[np];
for (int i = 0; i < np; i++) {
int personSkills = scn.nextInt();
for (int j = 0; j < personSkills; j++) {
String skill = scn.next();
int snum = smap.get(skill);
people[i] = people[i] | (1 << snum);
}
}
solution(people, n, 0, new ArrayList< >(), 0);
System.out.println(sol);
}
}
java;
true";
The above code is written and explained in the solution video (10:22 onwards). You may refer to it if you have any doubts about the code above. Now let us analyze the time and space complexity of the above procedure.
Analysis
Time Complexity:
The time complexity of the above procedure will be O(2n) where n is the number of developers. This is because we are making the subsequences of developers and we select the minimum length subsequence for which the skill bitmap is completely set. Since there are 2n subsequences of the developers, so the time complexity is also O(2n)
Space Complexity:
The space complexity is O(h) when we consider the recursion space where h is the height of the recursion stack. It will be O(n) where n is the number of developers. Since the height of the recursion tree is also the max height of the recursion stack, the space complexity will be O(n) when we consider recursion space.
So, dear reader, we hope that you have understood the above problem completely. If you have any doubts regarding the procedure or the code, refer to the complete solution video to clear all your doubts. With this, we have completed this problem.
Suggestions:
Here are some suggestions from our side that you do not want to miss:
We suggest you refer to the PRINT SUBSEQUENCE problem once. You can revise that problem too and also solving that problem once more will strengthen your core for this problem.
Can you think of some other solution for this problem? Try to find out some other method too. Till then, Happy Coding!!!
