Quick Overview

This question evaluates understanding of similarity scoring, set-based comparison of structured records, and practical data deduplication techniques commonly used in data science.

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.

Overview: 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

  1. Convert dictionary keys to sets and use set intersection/union sizes.
  2. Precompute sets for pirate themes to reuse across comparisons.
  3. Jaccard similarity is |A ∩ B| / |A ∪ B|; treat both-empty as 1.0 to avoid division by zero.
  4. For each custom theme, compare against all pirate themes and take the maximum similarity.

Loading coding console...

Show the approach

Approach

Convert each theme to a set of its keys. For each custom theme, compute the Jaccard similarity with every pirate theme: similarity = |intersection| / |union|, with a special case of 1.0 when both sets are empty. Track the maximum similarity for each custom theme and select indices where the maximum meets or exceeds the threshold. Precomputing pirate key-sets avoids repeated conversions.

Time complexity:
O(P * C * K), where P is the number of pirate themes, C is the number of custom themes, and K is the average number of unique keys per theme.
Space complexity:
O(P * K) to store pirate key-sets, plus O(K) for a single custom set during iteration.