Smallest Sufficient Team

Hard

Asked by:

5 views

Topics:

Dynamic ProgrammingBit Manipulation

In a project, you have a list of required skills req_skills, and a list of people. The i^th person people[i] contains a list of skills that the person has.

Consider a sufficient team: a set of people such that for every required skill in req_skills, there is at least one person in the team who has that skill. We can represent these teams by the index of each person.

For example, team = [0, 1, 3] represents the people with skills people[0], people[1], and people[3].

Return any sufficient team of the smallest possible size, represented by the index of each person. You may return the answer in any order.

It is guaranteed an answer exists.

Example 1:

Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
Output: [0,2]

Example 2:

Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
Output: [1,2]

Constraints:

1 <= req_skills.length <= 16
1 <= req_skills[i].length <= 16
req_skills[i] consists of lowercase English letters.
All the strings of req_skills are unique.
1 <= people.length <= 60
0 <= people[i].length <= 16
1 <= people[i][j].length <= 16
people[i][j] consists of lowercase English letters.
All the strings of people[i] are unique.
Every skill in people[i] is a skill in req_skills.
It is guaranteed a sufficient team exists.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can a skill be required by multiple people, and can a person possess multiple skills?
If there's no possible team that covers all the required skills, what should the function return? Can I return an empty list?
What is the maximum number of skills and people we should expect; are there constraints on their counts that I should be aware of?
If multiple smallest teams exist, is any one of them acceptable as the output, or is there a specific tie-breaking condition?
Can the list of required skills be empty? If so, what should the function return?

Brute Force Solution

Approach

The brute force approach to finding the smallest team that knows all required skills involves checking every possible combination of people. We start by trying small teams and gradually increase the team size, verifying if each team has all the necessary skills.

Here's how the algorithm would work step-by-step:

Begin by considering all possible teams of just one person.
Check if any of these single-person teams possesses all the required skills.
If not, move on to considering all possible teams of two people.
For each two-person team, verify if they collectively have all the required skills.
Continue this process, increasing the size of the team we are considering by one each time.
For each team size, examine every possible combination of people.
Once a team is found that possesses all the required skills, record the size of this team.
Continue examining larger team sizes to check if a smaller team that also meets the requirements exists.
Once we have exhausted all possibilities (or reached a reasonable limit), return the smallest team found that fulfills the requirements.

Code Implementation

def smallest_sufficient_team_brute_force(required_skills, people):
    number_of_required_skills = len(required_skills)
    number_of_people = len(people)

    skill_to_index = {skill: index for index, skill in enumerate(required_skills)}

    people_masks = []
    for person_skills in people:
        person_mask = 0
        for skill in person_skills:
            person_mask |= 1 << skill_to_index[skill]
        people_masks.append(person_mask)

    for team_size in range(1, number_of_people + 1):
        # Iterate through possible team sizes, starting from 1.
        for combination in get_combinations(number_of_people, team_size):
            team_mask = 0

            # Calculate the bitmask representing the skills of the current team.
            for person_index in combination:
                team_mask |= people_masks[person_index]

            # Check if the current team has all the required skills.
            if team_mask == (1 << number_of_required_skills) - 1:
                return list(combination)

    return list(range(number_of_people))

def get_combinations(number_of_people, team_size):
    if team_size == 0:
        yield ()
        return
    if team_size > number_of_people:
        return

    for index in range(number_of_people):
        remaining_number_of_people = number_of_people - (index + 1)
        for sub_combination in get_combinations(index + 1, team_size - 1):
            yield (index,) + sub_combination

Big(O) Analysis

Time Complexity

O(2^(n+m)) – The brute force approach iterates through all possible combinations of people to form teams. If there are 'n' people, the number of possible teams is 2^n (each person can be either in the team or not). For each team, we need to check if it possesses all the required 'm' skills, which takes O(m) time. Thus the total time complexity is O(m * 2^n) which we can simplify to O(2^(n+m)) where n is the number of people and m is the number of skills.

Space Complexity

O(1) – The described brute force approach iterates through different team sizes and combinations. The algorithm primarily uses a few variables to track the current team being considered and whether that team covers all skills. The space used by these variables is constant and does not depend on the number of people or required skills. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

This problem is about finding the smallest group of people who collectively know all the required skills. The most efficient way to solve it is by using a clever method that breaks the problem down into smaller, manageable pieces and remembers the best solutions found so far.

Here's how the algorithm would work step-by-step:

First, think of each skill as a bit in a binary number. This lets us represent sets of skills as simple numbers.
Next, we create a table where each entry represents a combination of required skills. The table stores the smallest team needed to cover that specific combination of skills.
Start by saying that to cover no skills (an empty set), we need no one.
Then, for each person, we figure out the set of skills they know. We then update our table: For each combination of skills, check if adding this person makes the team smaller than the current smallest team. If it does, we update the table.
We repeat this process for every person. At the end, the entry in our table that represents all the required skills will contain the smallest team needed.
To reconstruct the actual team members, we can trace back from the final skill set to see which people were added to improve the team size at each step.

Code Implementation

def smallest_sufficient_team(required_skills, people_skills):
    number_of_required_skills = len(required_skills)
    skill_to_index = {skill: i for i, skill in enumerate(required_skills)}
    number_of_people = len(people_skills)

    skill_sets = []
    for person_skills in people_skills:
        skill_set_mask = 0
        for skill in person_skills:
            if skill in skill_to_index:
                skill_set_mask |= 1 << skill_to_index[skill]
        skill_sets.append(skill_set_mask)

    # dp[skill_mask] is the smallest team that covers the skills in skill_mask
    dp = {0: []}

    # Iterate through each person to update the smallest team required.
    for person_index, skill_set_mask in enumerate(skill_sets):
        for current_skill_mask, current_team in list(dp.items()):
            combined_skill_mask = current_skill_mask | skill_set_mask

            # Only proceed if the combined skill set is new or smaller.
            if combined_skill_mask not in dp or len(dp[combined_skill_mask]) > len(current_team) + 1:

                # Update the smallest team with the current person included.
                dp[combined_skill_mask] = current_team + [person_index]

    # The smallest team to cover all skills is dp[(1 << number_of_required_skills) - 1]
    return dp[(1 << number_of_required_skills) - 1]

Big(O) Analysis

Time Complexity

O(2^m * n) – The algorithm iterates through each person (n). For each person, it iterates through all possible combinations of required skills. Since there are m required skills, there are 2^m possible combinations (skillsets). Inside the inner loop, it compares the current team size with the team size after adding the current person. Therefore, the dominant operations are iterating through each person and checking against all possible skillsets. This results in a time complexity of O(2^m * n).

Space Complexity

O(2^m) – The dominant space complexity arises from the table used to store the smallest team needed for each combination of skills, where 'm' is the number of required skills. This table has a size of 2^m because each of the 'm' skills can either be present or absent in a combination, leading to 2^m possible combinations. Additionally, space is used to store the actual team (a list of integers representing the people), however the size of this list will be bounded by the size of the optimal team, which can never exceed the number of people, and is less significant compared to the table. Therefore, the auxiliary space complexity is O(2^m).

Edge Cases

Case	How to Handle
Empty skills array	Return an empty team array if the required skills array is empty as no one is needed.
Empty people array	Return an empty team array if there are no people since no team can be formed.
No one has the required skills	Return null or an appropriate indicator that a valid team cannot be formed.
Single person has all required skills	Return an array containing only that person's index as the smallest sufficient team.
Large number of people and skills (scalability)	Optimize the bitmasking or dynamic programming approach to ensure efficient computation within time and memory limits.
Skills are duplicates within the required skills list	Deduplicate the skills to ensure correct bitmasking and prevent incorrect matching.
People have duplicate skills	The algorithm should handle duplicate skills without issue, as it checks for presence of all required skills overall, not skill uniqueness per person.
Multiple possible smallest sufficient teams	Return any one of the valid smallest sufficient teams, as the problem statement does not specify a preference.

Empty skills array

How to Handle:

Return an empty team array if the required skills array is empty as no one is needed.

Empty people array

How to Handle:

Return an empty team array if there are no people since no team can be formed.

No one has the required skills

How to Handle:

Return null or an appropriate indicator that a valid team cannot be formed.

Single person has all required skills

How to Handle:

Return an array containing only that person's index as the smallest sufficient team.

Large number of people and skills (scalability)

How to Handle:

Optimize the bitmasking or dynamic programming approach to ensure efficient computation within time and memory limits.

Skills are duplicates within the required skills list

How to Handle:

Deduplicate the skills to ensure correct bitmasking and prevent incorrect matching.

People have duplicate skills

How to Handle:

The algorithm should handle duplicate skills without issue, as it checks for presence of all required skills overall, not skill uniqueness per person.

Multiple possible smallest sufficient teams

How to Handle:

Return any one of the valid smallest sufficient teams, as the problem statement does not specify a preference.