Katkat
Back

Compute Theme Similarity

ShopifyData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to implement a set-based similarity metric, specifically the Jaccard index, to compare collections of theme-related features.

Problem Statement

At Shopify, merchants use themes to define the visual structure of their online stores. Each theme can be represented as a set of unique 'feature tags' (e.g., 'dark-mode', 'infinite-scroll', 'newsletter-popup').

Given two lists of feature tags representing two different themes, implement a function that calculates the Jaccard similarity coefficient. The Jaccard similarity between two sets A and B is defined as the size of their intersection divided by the size of their union:

J(A, B) = |A ∩ B| / |A ∪ B|

If both sets are empty, define the similarity as 1.0. If only one set is empty, define the similarity as 0.0.

Function Signature

def get_theme_similarity(theme1_tags, theme2_tags):
    # theme1_tags: list of strings
    # theme2_tags: list of strings
    # returns: float

Examples

Example 1:

  • Input: theme1 = ['cart', 'search', 'sale'], theme2 = ['search', 'sale', 'footer']
  • Intersection: {'search', 'sale'} (size 2)
  • Union: {'cart', 'search', 'sale', 'footer'} (size 4)
  • Output: 0.5

Example 2:

  • Input: theme1 = ['a', 'b'], theme2 = ['a', 'b', 'c']
  • Intersection: {'a', 'b'} (size 2)
  • Union: {'a', 'b', 'c'} (size 3)
  • Output: 0.666...

Constraints

  • Tag lists may contain duplicates, but these should be treated as a single set of unique tags.
  • The number of tags per theme is between 0 and 1,000.
  • Input lists are not guaranteed to be sorted.

Hints

Hint 1

Convert the input lists into sets to automatically handle uniqueness and enable efficient intersection and union operations.

Hint 2

Use the built-in set operations `&` for intersection and `|` for union to simplify your code logic.

Hint 3

Remember to handle the edge case where both sets are empty to avoid division by zero errors.

Follow-up questions

  • How would you optimize the computation if you had to compare one theme against a database of 10,000 existing themes?
  • If themes were represented as binary vectors (0 or 1 for each possible tag), how would you calculate the similarity using linear algebra instead of sets?
  • What are the limitations of the Jaccard similarity in this context, and when might you prefer a weighted similarity metric (like Cosine Similarity)?