Identify Pirate Themes Using Similarity Score Algorithm
Company: Shopify
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Scenario
Engineering wants an automated way to spot custom themes that are probably just pirate themes in disguise.
##### Question
Write Python that takes two lists (A and B) and returns their similarity score defined as len(intersection) / len(union). Given pirate_themes (list of dicts) and custom_themes (list of dicts), identify which custom themes are likely pirates using the similarity score and explain your threshold choice.
##### Hints
Implement a Jaccard similarity; iterate over dictionaries by a chosen key set; threshold of 0.5 is typical.
Quick Answer: This question evaluates understanding of similarity scoring, set-based comparison of structured records, and practical data deduplication techniques commonly used in data science.
You are given two lists of theme dictionaries: pirate_themes and custom_themes. Each theme is a dictionary mapping string feature names to any value. Define the feature set of a theme as the set of its dictionary keys. The Jaccard similarity between two themes A and B is |features(A) ∩ features(B)| / |features(A) ∪ features(B)|. If the union is empty (both themes have no keys), define the similarity as 1.0. For each custom theme, compute the maximum Jaccard similarity to any pirate theme. Return the list of indices of custom themes whose maximum similarity is at least threshold, in ascending order. If pirate_themes is empty, return an empty list.
Constraints
- 0 <= len(pirate_themes) <= 1000
- 0 <= len(custom_themes) <= 1000
- Sum of unique keys across all themes <= 1e5
- Each key is a non-empty string (case-sensitive)
- 0.0 <= threshold <= 1.0
- Return indices in ascending order
- If pirate_themes is empty, return []
Hints
- Convert dictionary keys to sets and use set intersection/union sizes.
- Precompute sets for pirate themes to reuse across comparisons.
- Jaccard similarity is |A ∩ B| / |A ∪ B|; treat both-empty as 1.0 to avoid division by zero.
- For each custom theme, compare against all pirate themes and take the maximum similarity.