Katkat
Back

Compute Jaccard Similarity for Lists

ShopifyData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of Jaccard similarity and set-based operations, assessing competency in deduplicating lists, precise string comparisons (case-sensitivity and whitespace), and handling edge cases.

Implement a Python function to compute the Jaccard similarity between two lists of strings.

def jaccard_similarity(a: list[str], b: list[str]) -> float:
 pass

Requirements

  • Treat each input list as a set of unique strings; duplicate strings within the same list should not affect the result.
  • Jaccard similarity is defined as:

size(intersection of unique strings) / size(union of unique strings)

  • String comparison is case-sensitive, and whitespace is significant.
  • If both lists are empty, return 1.0.
  • If exactly one list is empty, return 0.0.
  • Do not use third-party libraries.
  • Aim for O(n + m) time complexity, where n and m are the lengths of the two input lists.

Examples

jaccard_similarity(["red", "blue", "blue"], ["blue", "green"]) == 1 / 3
jaccard_similarity(["a", "b"], ["a", "b"]) == 1.0
jaccard_similarity([], ["a"]) == 0.0
jaccard_similarity([], []) == 1.0