Stage 5: Interview Simulation·Timed Random Hards

Hard#112510 min readBitmask DPSet CoverBFSLeetCode

Smallest Sufficient Team

Bitmask DP over skill coverage

Set cover via bitmask DP. n ≤ 16 is the signal.

Published Apr 17, 2026

Problem

You have a list req_skills of n required skills and a list people where people[i] is the skills the i-th person knows. Return indices of the smallest team whose combined skills cover every required skill.

Key constraint: n ≤ 16 (signature of bitmask DP). m = |people| ≤ 60.

Input

req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]

Output

[0, 2]

Explanation

Person 0 covers java; person 2 covers nodejs and reactjs. Size 2 is optimal.

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] (any valid 2-sized team)

Explanation

Person 1 covers {algorithms, math, reactjs}; person 2 covers {java, csharp, aws}. Their union is all 6 required skills, so size 2 is optimal.

Intuition

This is the classical Set Cover problem. It's NP-hard in general, but n ≤ 16 means the skill set fits in a u32 bitmask, giving 2^n = 65 536 possible coverage states — the DP fits comfortably in memory.

Encode every person as a skill mask: person_mask[i] = OR of bits for the skills they know. Then dp[mask] = the smallest list of person indices whose union equals mask. Transition: extend dp[mask] by each person i, producing dp[mask | person_mask[i]].

The goal is dp[(1 << n) - 1]. Answer is the stored team vector.

Approach

Brute Subset Enumeration

TimeO(2^m · m)

SpaceO(m)

Try every subset of people; for each subset, OR the masks; keep the smallest subset whose OR equals full. m ≤ 60 makes 2^60 infeasible, so this is a reference sketch only (useful for tiny m).

impl Solution {
    pub fn smallest_sufficient_team(
        req_skills: Vec<String>,
        people: Vec<Vec<String>>,
    ) -> Vec<i32> {
        let idx: std::collections::HashMap<_, _> =
            req_skills.iter().enumerate().map(|(i, s)| (s.clone(), i)).collect();
        let n = req_skills.len();
        let masks: Vec<u64> = people
            .iter()
            .map(|p| p.iter().filter_map(|s| idx.get(s)).fold(0u64, |a, &b| a | (1 << b)))
            .collect();
        let full: u64= (1 << n) - 1;
        let m= masks.len();
        let mut best: Option<Vec<i32>> = None;
        for subset in 0u64..(1 << m) {
            let mut cover= 0u64;
            let mut team: Vec<i32> = Vec::new();
            for i in 0..m {
                if (subset >> i) & 1 == 1 {
                    cover |= masks[i];
                    team.push(i as i32);
                }
            }
            if cover == full && best.as_ref().map_or(true, |b| team.len() < b.len()) {
                best= Some(team);
            }
        }
        best.unwrap_or_default()
    }
}

Rust · runnable

function smallestSufficientTeam(reqSkills: string[], people: string[][]): number[] {
  const idx = new Map(reqSkills.map((s, i) => [s, i]));
  const n = reqSkills.length;
  const full = (1 << n) - 1;
  const masks = people.map((p) =>
    p.reduce((a, s) => (idx.has(s) ? a | (1 << idx.get(s)!) : a), 0)
  );
  let best: number[] | null = null;
  for (let subset = 0; subset < (1 << people.length); subset++) {
    let cover = 0;
    const team: number[] = [];
    for (let i = 0; i < people.length; i++) {
      if ((subset >> i) & 1) { cover |= masks[i]; team.push(i); }
    }
    if (cover === full && (best === null || team.length < best.length)) best = team;
  }
  return best ?? [];
}

TypeScript · runnable

Bitmask DP on Skill Coverage

TimeO(m · 2^n)

SpaceO(2^n)

Recommended

Encode skills. For each person compute person_mask[i] in O(|skills|).
DP state. dp[mask] = Some(team) where team is the smallest known list of indices whose union of skills equals mask. Base: dp[0] = Some(vec![]).
Transition. For every person i and every currently-known state mask, compute new_mask = mask | person_mask[i]. If new_mask == mask, skipping adds nothing. Otherwise, if dp[mask].team + [i] is shorter than dp[new_mask] (or dp[new_mask] is None), update.
Answer. dp[(1 << n) - 1].

Store vectors directly in dp. Alternative memory-tighter form: store (parent_mask, person) and reconstruct.

use std::collections::HashMap;

impl Solution {
    pub fn smallest_sufficient_team(
        req_skills: Vec<String>,
        people: Vec<Vec<String>>,
    ) -> Vec<i32> {
        let idx: HashMap<String, usize> =
            req_skills.iter().enumerate().map(|(i, s)| (s.clone(), i)).collect();
        let n = req_skills.len();
        let full = 1usize << n;
        let m= people.len();

        let person_mask: Vec<usize> = people
            .iter()
            .map(|p| p.iter().filter_map(|s| idx.get(s)).fold(0usize, |a, &b| a | (1 << b)))
            .collect();

        let mut dp: Vec<Option<Vec<i32>>> = vec![None; full];
        dp[0] = Some(Vec::new());

        for i in 0..m {
            let pm = person_mask[i];
            if pm == 0 { continue; }
            for mask in 0..full {
                if let Some(team) = dp[mask].clone() {
                    let nm = mask | pm;
                    if nm == mask { continue; }
                    let mut extended = team;
                    extended.push(i as i32);
                    if dp[nm].as_ref().map_or(true, |t| extended.len() < t.len()) {
                        dp[nm]= Some(extended);
                    }
                }
            }
        }

        dp[full - 1].clone().unwrap_or_default()
    }
}

Rust · runnable

function smallestSufficientTeam(reqSkills: string[], people: string[][]): number[] {
  const idx = new Map(reqSkills.map((s, i) => [s, i]));
  const n = reqSkills.length;
  const full = 1 << n;
  const personMask = people.map((p) =>
    p.reduce((a, s) => (idx.has(s) ? a | (1 << idx.get(s)!) : a), 0)
  );

  const dp: (number[] | null)[] = new Array(full).fill(null);
  dp[0] = [];

  for (let i = 0; i < people.length; i++) {
    const pm = personMask[i];
    if (pm === 0) continue;
    for (let mask = 0; mask < full; mask++) {
      const team = dp[mask];
      if (team === null) continue;
      const nm = mask | pm;
      if (nm === mask) continue;
      const extended = [...team, i];
      if (dp[nm] === null || extended.length < dp[nm]!.length) dp[nm] = extended;
    }
  }

  return dp[full - 1] ?? [];
}

TypeScript · runnable

Trace

On req = [a, b, c], people = [[a,b], [b,c], [a,c]], person masks = [0b011, 0b110, 0b101], full = 0b111.

person	iterating mask	new mask	update
0 (011)	000	011	dp[011] = [0]
1 (110)	000	110	dp[110] = [1]
1 (110)	011	111	dp[111] = [0, 1]
2 (101)	000	101	dp[101] = [2]
2 (101)	110	111	[1, 2] same length — no update

Final dp[111] = [0, 1] (any size-2 team wins).

Edge cases

Person with no matching skills — person_mask == 0; skip them entirely. Adding i with mask 0 would produce new_mask == mask and be pruned anyway, but the early-skip avoids wasted loop work.
Already-covering person — a single person whose mask equals full produces dp[full] with team size 1; optimal immediately.
No valid cover — problem guarantees coverage exists, but defensive code returns [] when dp[full] is still None.
Tie-break — any minimum-size team is accepted; different update orders produce different winning teams.

Takeaway

Set Cover with small n = bitmask DP on coverage state. The same template solves the Knight's Tour variants, "minimum moves to turn all lights on", and interview favorites like 943 (Shortest Superstring).

The 3-minute recognition cue for an interview: a small count of "categories" (skills, positions, keys) you need to cover, plus a large pool of candidates each covering a subset. When n ≤ 20, state the DP in one sentence aloud before coding — that alone banks most of the credit.

Hard#943

Find the Shortest Superstring

Bitmask DP (TSP variant). Can you identify it within 3 minutes?

Medium#78

Subsets

The canonical backtracking template. Include or exclude each element.

Medium#300

Longest Increasing Subsequence

O(n²) DP first, then learn the O(n log n) patience sorting approach.