Compute and Rank by Jaccard Similarity

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Yelp.

Q: What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Yelp during technical interviews.

Question

Implement two functions: (1) jaccard_similarity(s1, s2) that tokenizes by splitting on any non-alphanumeric character, lowercases, treats tokens as sets (duplicates ignored), and returns |A ∩ B| / |A ∪ B| with 0.0 when the union is empty; (2) rank_by_jaccard(reviews, target) that returns the reviews sorted descending by similarity to target, stable on ties by original index. Discuss how you would handle very long inputs (streaming/iterators), Unicode and punctuation edge cases, and how to achieve O(T) expected time where T is total tokens. Finally, extend rank_by_jaccard to return the top-k efficiently for k ≪ n without computing full similarities for all n reviews; justify your data structures and complexity.

PracHub · Accepted Answer

The prompt evaluates set-based similarity metrics (Jaccard), robust tokenization and normalization for text data including Unicode and punctuation edge cases, streaming/iterator processing for very long inputs, and algorithmic efficiency for top-k retrieval and stable ranking.

Quick Overview

Compute and Rank by Jaccard Similarity

Constraints

Examples

Hints