Identify Pirate-Themed Custom Themes Using Jaccard Similarity

Scenario

Engineering receives two lists and must identify custom themes that look like Pirate themes.

Question

a) Write a Python function that computes the Jaccard similarity len(intersection)/len(union) between any two lists.

b) Given pirate_themes (list[dict]) and custom_themes (list[dict]), return custom themes whose similarity to at least one pirate theme exceeds a chosen threshold.

c) Describe how you would handle edge cases and scale this computation to millions of themes.

Hints

Use set operations; handle empty lists; consider MinHash or locality-sensitive hashing for scale.

Detect Pirate-Like Themes via Jaccard

You are given two lists: pirate_themes and custom_themes. Each element is a dict with keys 'name' (string) and 'tags' (list of strings). Define the Jaccard similarity between two tag lists as |intersection| / |union| using set semantics (duplicates ignored). If both tag lists are empty, define similarity as 1.0. Return the list of names of custom themes whose similarity to at least one pirate theme is greater than or equal to threshold. Preserve the order of custom_themes in the output. Tag comparison is case-sensitive. If pirate_themes is empty, return an empty list.

Constraints

• 0 <= len(pirate_themes), len(custom_themes) <= 10^4
• Each theme dict contains keys: 'name' (unique string) and 'tags' (list of strings)
• 0 <= len(tags) <= 10^3 per theme; duplicates in 'tags' are ignored
• 0.0 <= threshold <= 1.0
• Tag comparison is case-sensitive
• Return names in the same order as they appear in custom_themes

Examples

Example 1

Input: pirate_themes = [{"name": "Black Pearl", "tags": ["skull", "black", "ship", "treasure"]}, {"name": "Jolly Roger", "tags": ["skull", "flag", "black"]}]
custom_themes = [{"name": "Dark Ship", "tags": ["black", "ship"]}, {"name": "Treasure Hunt", "tags": ["treasure", "map", "island"]}, {"name": "Sunset Beach", "tags": ["beach", "sunset"]}]
threshold = 0.5
Output: ["Dark Ship"]

Explanation: Dark Ship vs Black Pearl: intersection={black, ship} (2), union={skull, black, ship, treasure} (4) -> 2/4 = 0.5 >= 0.5, so included. Others do not meet the threshold with any pirate theme.

Example 2

Input: pirate_themes = [{"name": "Blank Pirate", "tags": []}, {"name": "Seadog", "tags": ["anchor"]}]
custom_themes = [{"name": "Empty Custom", "tags": []}, {"name": "Anchors Aweigh", "tags": ["anchor", "anchor"]}, {"name": "Rope", "tags": ["rope"]}]
threshold = 1.0
Output: ["Empty Custom", "Anchors Aweigh"]

Explanation: Empty Custom vs Blank Pirate: both empty => similarity=1.0. Anchors Aweigh duplicates are ignored -> {anchor} vs {anchor} -> 1/1=1.0. Rope has 0 overlap with any pirate theme.

Hints

1. Convert each theme's tags list to a set to ignore duplicates.
2. Jaccard similarity is len(A ∩ B) / len(A ∪ B); if the union is empty, treat similarity as 1.0.
3. Precompute sets for pirate themes to avoid repeated conversions.
4. Short-circuit once any pirate theme meets the threshold for a custom theme.
5. For large-scale data, consider MinHash/LSH or inverted-index filtering to reduce pairwise comparisons.

Approach

Convert each theme's tag list to a set to ignore duplicates. For each custom theme, compute the Jaccard similarity against each pirate theme: similarity = |A ∩ B| / |A ∪ B|. If the union is empty (both sets empty), define similarity as 1.0. Add the custom theme's name to the answer as soon as any pirate theme meets or exceeds the threshold. Preserve input order by iterating custom_themes in order and appending when qualified.

• Time complexity: O(P * C * T), where P is the number of pirate themes, C is the number of custom themes, and T is the average number of unique tags per theme (cost of set operations).
• Space complexity: O(P * T) for storing pirate tag sets; O(1) additional space aside from input and output.