## Problem You are building a data deduplication pipeline. Given a list of text records, identify and remove near-duplicates. Two records are near-duplicates if their normalized Jaccard similarity on character 3-grams exceeds a threshold `t`. Return the deduplicated list, keeping the first occurrence of each cluster. ```python def deduplicate( records: list[str], threshold: float = 0.8 ) -> list[str]: pass def jaccard_3gram(a: str, b: str) -> float: """Return Jaccard similarity of 3-gram sets.""" pass ``` ``` Input: records = ["hello world", "Hello World!", "foo bar", "hello world "] threshold = 0.7 Output: ["hello world", "foo bar"] # After normalization, records 0,1,3 cluster together -> keep first. Input: records = ["abc", "xyz"] Output: ["abc", "xyz"] ``` ## Follow-ups 1. Naive O(n^2) comparison is too slow for large datasets. How does MinHash + LSH reduce this to near-linear? 2. How do you choose the 3-gram size? What are the tradeoffs of 2-grams vs 4-grams? 3. If records are structured (e.g., JSON objects), how would you define similarity across fields? 4. How would you implement this as an incremental pipeline where new records stream in daily?

InterviewDB Question · Paris

Deduplication Pipeline: Remove Near-Duplicate Records Using Hashing

phone

Question Details

Problem You are building a data deduplication pipeline. Given a list of text records, identify and remove near-duplicates. Two records are near-duplicates if their normalized Jaccard similarity on character 3-grams exceeds a threshold t. Return the deduplicated list, keeping the first occurrence of each cluster. Follow-ups Naive O(n^2) comparison is too slow for large datasets. How does MinHash + LSH reduce this to near-linear? How do you choose the 3-gram size? What are the tradeoffs of 2-grams…

Full Details

🔒

Unlock all Perplexity questions

Full insider details, leaked discussions, and candidate experiences.

Get full access — $100 a year, unlimited access

About This Question

This is a reported interview question from a perplexity interview during the phone round.

It covers the following topics: Coding, Mle, Phone .

Topics

Coding Mle Phone

Deduplication Pipeline: Remove Near-Duplicate Records Using Hashing

Question Details

Full Details

About This Question

Topics

More Perplexity Interview Questions