Skill set matching algorithm

Question

I was asked this in an interview.

I have been trying to find an elegant algorithm for this problem but haven't been able to do so.

Given a list of people(represented as numbers - id's) with their skill sets as follows:

C : 1, 8, 12, 14

C++ : 3, 7, 8, 12, 15

perl : 1, 2, 3, 8

Ruby : 14, 23

Given a list of skills, return the id that matches the required skill set:

[EG]

Skill set: C & C++ Answer is 8,12

Skill set : C, C++, Perl - matching atleast 2 skills Answer is 1, 3, 8, 12

The list of id's were originally unsorted but I started out by sorting them. Naive approach would be to take one list (say c++ for second example) and compare it with another list(say Java) making use of the sorted order.

Is there an algorithm or a better approach?

Answer 1

Depends on the number of skills. If it is small, I would use prime numbers. More preciesly: Create table skills[n] (where n is number of users). Fill it with 1s. Then, if the user knows first skill (in this case C) multiply by first prime number (2), if he knows second skill multiply by second prime number, etc.

Then, if you want to find if user i knows second skill (C++) , simply check if skills[i]%3==0

Example: Finding skill value: user 1 knows skill 1 (C) and skill 3 (Perl), what means his skill value is 1*2*5=10. User 2 knows skill 3, so his skill value is 1*5.

Finding all users that can use C,C++,Perl matching 2:

for(int i=0;i<n;i++){
    int howMany=0;
    if(skill[i]%2)==0)
        howMany++;
    if(skill[i]%5)==0)
        howMany++;
    if(skill[i]%7)==0)
        howMany++;
    if(howMany>=2)
        addToResult(i);
 }

---

Alternatively, you could create a 2d array, where column corresponds to person and row to skill. If value is set to 1 it means person knows how to use the skill, if it's set to 0, they don't. Then, simply add valus of all rows you need, and find proper user.

Example:

 C    1 | 0 | 0 |
 C++  0 | 0 | 1 |
 PERL 1 | 1 | 1 |

Lets find someone who knows C, Perl - We add all values from rows 1 and 3, we get

 SUM  2 | 1 | 1 | 

Only column 1 has value >=2, what means it's the only one that fulfills criteria. Now, let's try finding someone who uses C, C++ and PERL, matching 2

SUM  2 | 1 | 2

We know now that user 1 and user 3 have value of sum >=2, so they fulfill those criteria.

Answer 2

Here is efficient algorithm for doing it :-

1. Use HashSet of id's for each skill
2. To check if a id has a skill just check in HashSet

Note:

This algorithm is O(n*S) where n is number of person , S is number of skills wanted. I dont think there is faster algorithm.

Edit:

Instead of searching for all n persons you can also check with only people which are in atleast one of skills in required set. In many case this would save you lot of computation time.