Smallest Sufficient Team
Asked at Airbnb
Problem
Smallest Sufficient Team gives you a list of required skills (at most 16) and people with subsets of those skills, and asks for the smallest team that covers every required skill. The small skill count is the hint: represent skill sets as bitmasks and run a DP over all 2^16 masks.
Asked At
| Company | Difficulty | |
|---|---|---|
| Airbnb | Hard | View all Airbnb questions → |
How to Think About It
Trying all subsets of people is 2^60 — impossible. But there are only 2^16 = 65536 possible skill sets, so DP over skill sets instead.
Encode each person's skills as a bitmask using an index map from skill name to bit.
Key insight: dp[mask] = size of the smallest team whose combined skills are exactly mask. From each reachable mask, adding person i reaches mask | skills[i] with one more member.
Store how you reached each mask (the person added and the previous mask) so you can reconstruct the team at the end.
Iterating masks in increasing order works because mask | skills[i] >= mask, so every state is final before it is expanded.
Optimal Approach
Step 1: Map skills to bits; compute pm[i] for each person.
Step 2: dp[0] = 0, all other dp = inf; arrays parent and who.
Step 3: For mask from 0 to 2^m - 1 (skip if dp[mask] is inf):
For each person i: nm = mask | pm[i]; if dp[mask] + 1 < dp[nm]: set dp[nm], parent[nm] = mask, who[nm] = i.
Step 4: Walk back from the full mask via parent, collecting who.
Time: O(2^m * n). Space: O(2^m).
What Trips People Up in Real Interviews
Enumerating subsets of people. The constraint to exploit is the tiny number of skills.
Storing whole team lists in every DP cell. It works but copies lists constantly; parent pointers are leaner.
Forgetting that a person with no required skills never helps — they are naturally skipped because mask | 0 == mask.
Not explaining why increasing mask order is valid.
Solution Code
def smallestSufficientTeam(req_skills, people):
m = len(req_skills)
bit = {s: i for i, s in enumerate(req_skills)}
pm = []
for p in people:
mask = 0
for s in p:
mask |= 1 << bit[s]
pm.append(mask)
full = (1 << m) - 1
INF = float('inf')
dp = [INF] * (1 << m)
parent = [-1] * (1 << m)
who = [-1] * (1 << m)
dp[0] = 0
for mask in range(1 << m):
if dp[mask] == INF:
continue
for i, p in enumerate(pm):
nm = mask | p
if dp[mask] + 1 < dp[nm]:
dp[nm] = dp[mask] + 1
parent[nm] = mask
who[nm] = i
team = []
mask = full
while mask:
team.append(who[mask])
mask = parent[mask]
return teamFrequently Asked Questions
What is the Smallest Sufficient Team problem?
Smallest Sufficient Team gives you a list of required skills (at most 16) and people with subsets of those skills, and asks for the smallest team that covers every required skill. The small skill count is the hint: represent skill sets as bitmasks and run a DP over all `2^16` masks.
How do you solve Smallest Sufficient Team?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Smallest Sufficient Team?
Smallest Sufficient Team is asked at Airbnb. It is a hard difficulty problem.
What are common mistakes on Smallest Sufficient Team?
- Enumerating subsets of people. The constraint to exploit is the tiny number of skills.
- Storing whole team lists in every DP cell. It works but copies lists constantly; parent pointers are leaner.
- Forgetting that a person with no required skills never helps — they are naturally skipped because `mask | 0 == mask`.
- Not explaining why increasing mask order is valid.