We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Smallest Sufficient Team

Number: 1220

Difficulty: Hard

Paid? No

Companies: tcs, Google, Amazon

Problem Description

Given a list of required skills and a list of people where each person has a subset of these skills, the task is to select the smallest set of people (team) such that every required skill is possessed by at least one person in the team.

Key Insights

  • Use bitmasking to represent the set of skills since the number of skills is at most 16.
  • Map each required skill to a unique bit position.
  • Use dynamic programming (DP) where keys are bitmasks representing the set of covered skills and values are the list of indices forming the team that covers the skills defined by the bitmask.
  • Iteratively update the DP state by considering each person’s skills and merge them with existing states.
  • The answer is found in the DP state that represents all required skills (i.e., bitmask is all 1’s).

Space and Time Complexity

Time Complexity: O(m * 2^n) where m is the number of people (up to 60) and n is the number of required skills (up to 16). Space Complexity: O(2^n) for storing the DP states.

Solution

The solution works by first assigning a unique bit to each required skill. For every person, compute a bitmask indicating which required skills they possess. A dynamic programming dictionary (or map) is then used where the key is a bitmask representing the set of skills covered so far and the value is the team (list of indices) that achieves this coverage with the smallest size. Initialize the DP with the state 0 (no skills covered) and an empty team. For each person, for each existing DP state, compute a new state by combining the current state with the person’s skills. If this new state is either not in the DP dictionary or can be achieved with fewer people, update the DP state. The process continues until all persons are evaluated. The final answer is the team associated with the DP state where all required skills are covered.

Code Solutions

# Python solution for Smallest Sufficient Team

def smallestSufficientTeam(req_skills, people):
    # Map each skill to a unique bit
    skill_to_bit = {skill: i for i, skill in enumerate(req_skills)}
    n = len(req_skills)
    
    # Compute bitmask for each person based on their skills
    person_skills = []
    for skills in people:
        mask = 0
        for skill in skills:
            mask |= 1 << skill_to_bit[skill]
        person_skills.append(mask)
    
    # DP dictionary: key = bitmask of skills, value = list of team member indices
    dp = {0: []}
    
    # Iterate over each person index and their skills mask
    for i, p_skill in enumerate(person_skills):
        # Use a snapshot of current DP keys to avoid modifying during iteration
        for comb, team in list(dp.items()):
            new_comb = comb | p_skill
            if new_comb not in dp or len(dp[new_comb]) > len(team) + 1:
                dp[new_comb] = team + [i]
    
    # The full mask has all required skills (all n bits set)
    return dp[(1 << n) - 1]

# Example usage:
req_skills = ["java", "nodejs", "reactjs"]
people = [["java"], ["nodejs"], ["nodejs","reactjs"]]
print(smallestSufficientTeam(req_skills, people))
← Back to All Questions