People Whose List of Favorite Companies Is Not a Subset of Another List

People Whose List of Favorite Companies Is Not a Subset of Another List

What is this problem about?

The People Whose List of Favorite Companies Is Not a Subset of Another List problem gives you lists of company names for each person. Return the indices of people whose list is not a subset of any other person's list. This coding problem uses set operations to check subset relationships. The array, hash table, and string interview pattern is demonstrated.

Why is this asked in interviews?

Datadog and Google ask this to test set-based reasoning and efficient subset checking. With n up to 500 and lists up to 500 companies, an O(n² * list_size) brute force is acceptable, but using frozensets for O(1) lookup optimization is preferred.

Algorithmic pattern used

Convert to frozensets + subset check. Convert each person's list to a frozenset. For each person i, check if their set is a subset of any other person j's set (set_i.issubset(set_j)). If not a subset of any other, include in result. Time: O(n² * average_list_size).

Example explanation

lists=[["amazon","apple"],["apple"],["google","facebook"],["amazon","apple","google"]].

• Person 0 {amazon,apple}: subset of person 3? {amazon,apple} ⊆ {amazon,apple,google} ✓. Exclude.
• Person 1 {apple}: subset of person 0? {apple} ⊆ {amazon,apple} ✓. Exclude.
• Person 2 {google,facebook}: subset of anyone? Person 3 has {amazon,apple,google}, no facebook. Not subset. Include.
• Person 3: is subset of anyone? No. Include. Result: [2, 3].

Common mistakes candidates make

• Using list comparison instead of set subset check (order matters for lists, not sets).
• Comparing a person's set with itself (must check i != j).
• Not converting to frozenset for hashable set operations.
• Quadratic time with string comparison instead of set operations.

Interview preparation tip

Subset checking problems on collections always use sets. Converting each list to a frozenset enables issubset() in O(min(|A|,|B|)) time. The pattern: build all frozensets, then for each, check against all others. This generalizes to "find minimal/maximal elements under set inclusion ordering" — important in database query optimization and feature selection.